Leader election in shared spectrum radio networks

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 [5]. 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 [5], 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.