TY - GEN

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

PY - 2011/11/2

Y1 - 2011/11/2

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 nodes wake up asynchronously. At each time slot a node can either beep (i.e., 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 neighbor 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 compute 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 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 beeping nodes to receive feedback to identify if at least one neighboring node is beeping concurrently (i.e., sender-side collision detection) we can find an MIS in O(log2n) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to compute an MIS in O(log2n) 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 nodes wake up asynchronously. At each time slot a node can either beep (i.e., 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 neighbor 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 compute 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 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 beeping nodes to receive feedback to identify if at least one neighboring node is beeping concurrently (i.e., sender-side collision detection) we can find an MIS in O(log2n) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to compute an MIS in O(log2n) time.

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

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

U2 - 10.1007/978-3-642-24100-0_3

DO - 10.1007/978-3-642-24100-0_3

M3 - Conference contribution

AN - SCOPUS:80055052840

SN - 9783642240997

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 32

EP - 50

BT - Distributed Computing - 25th International Symposium, DISC 2011, Proceedings

T2 - 25th International Symposium on Distributed Computing, DISC 2011

Y2 - 20 September 2011 through 22 September 2011

ER -