TY - JOUR

T1 - Beeping a maximal independent set

AU - Afek, Yehuda

AU - Alon, Noga

AU - Bar-Joseph, Ziv

AU - Cornejo, Alejandro

AU - Haeupler, Bernhard

AU - Kuhn, Fabian

N1 - Funding Information:
We thank the anonymous reviewers for their feedback to improve the quality of this paper. Research supported in part by AFOSR Award FA9550-08-1-0159, NSF Award CNS-1035199, NSF Award CCF-0937274, NSF Award CCF-0726514, ERC advanced grant, USA-Israeli BSF grant, and the Israeli I-Core program.

PY - 2013/8

Y1 - 2013/8

N2 - We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in O (log3n) time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in O (log3n) time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in O (log3n) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in O (log3n) time.

AB - We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in O (log3n) time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in O (log3n) time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in O (log3n) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in O (log3n) time.

KW - Asynchronous wakeup

KW - Beeps

KW - Distributed

KW - Maximal independent set

KW - Radio networks

UR - http://www.scopus.com/inward/record.url?scp=84880919898&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880919898&partnerID=8YFLogxK

U2 - 10.1007/s00446-012-0175-7

DO - 10.1007/s00446-012-0175-7

M3 - Article

AN - SCOPUS:84880919898

VL - 26

SP - 195

EP - 208

JO - Distributed Computing

JF - Distributed Computing

SN - 0178-2770

IS - 4

ER -