Please use this identifier to cite or link to this item:
|Title:||Leader election in shared spectrum radio networks|
|Source:||Daum, S.,Gilbert, S.,Kuhn, F.,Newport, C. (2012). Leader election in shared spectrum radio networks. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing : 215-224. ScholarBank@NUS Repository. https://doi.org/10.1145/2332432.2332470|
|Abstract:||We study the leader election problem in the context of a congested single-hop radio network. We assume a collection of N synchronous devices with access to a shared band of the radio spectrum, divided into F frequencies. To model unpredictable congestion, we assume an abstract interference adversary that can choose up to t < F frequencies in each round to disrupt, preventing communication. The devices are individually activated in arbitrary rounds by an adversary. On activation, a device does not know how many other devices (if any) are also active. The goal of the leader election problem is for each active device to output the id of a leader as soon as possible after activation, while preserving the safety constraint that all devices output the same leader, with high probability. We begin by establishing a lower bound of Ω(log 2N / F-t)log logN + / Ft/F-t·logN) rounds, through reduction to an existing result in this model . We then set out to prove this bound tight (within log log N factors). For the case where t=0, we present a novel randomized algorithm, based on a strategy of recruiting herald no-des, that works in O(/log 2NF+log N) time. For 1 ≤ t ≤ F/6, we present a variant of our herald algorithm in which multiple real (potentially disrupted) frequencies are used to simulate each non-disrupted frequency from the t=0 case. This algorithm works in O(/log 2NF+tlog N) time. Finally, for t > F/6 we show how to improve the trapdoor protocol of , used to solve a similar problem in a non-optimal manner, to solve leader election in optimal O(/ logN + F t/F-t · logN ) time, for (only) these large values of t. We also observe that if F = ω(1) and t ≤ (1-ε)F for a constant ε > 0, our protocols beat the classic Ω(log 2N) bound on wake-up in a single frequency radio network, underscoring the observation that more frequencies in a radio network allows for more algorithmic efficiency - even if devices can each only participate on a single frequency at a time, and a significant fraction of these frequencies are disrupted adversarially. © 2012 ACM.|
|Source Title:||Proceedings of the Annual ACM Symposium on Principles of Distributed Computing|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 11, 2017
checked on Dec 16, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.