2011/08/09 by Alejandro Cornejo, Alejandro Donohué-Cornejo, Bernhard Haeupler +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1108.1926
arxiv created 2011/08/09 · openalex publication_date 2011/08/09 · arxiv updated 2011/08/10 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We consider the problem of finding a maximal independent set (MIS) in the discrete beeping model. At each time, a node in the network can either beep (i.e., emit a signal) or be silent. Silent nodes can only differentiate between no neighbor beeping, or at least one neighbor beeping. This basic communication model relies only on carrier-sensing. Furthermore, we assume nothing about the underlying communication graph and allow nodes to wake up (and crash) arbitrarily. We show that if a polynomial upper bound on the size of the network n is known, then with high probability every node becomes stable in O(log3 n) time after it is woken up. To contrast this, we establish a polynomial lower bound when no a priori upper bound on the network size is known. This holds even in the much stronger model of local message broadcast with collision detection. Finally, if we assume nodes have access to synchronized clocks or we consider a somewhat restricted wake up, we can solve the MIS problem in O(log2 n) time without requiring an upper bound on the size of the network, thereby achieving the same bit complexity as Luby's MIS algorithm.