Technical Report No. 269 - Abstract

Sebastian Daum, Seth Gilbert, Fabian Kuhn and Calvin Newport
Leader Election in Shared Spectrum Radio Networks

In this paper, 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²N )/( (F −t)loglogN)] + [( F t )/( F − t)] ·logN) rounds, through reduction to an existing result in this model. We then set out to prove this bound tight (within loglogN factors). For the case where t=0, we present a novel randomized algorithm, based on a strategy of recruiting herald nodes, that works in O([(log²N)/(F)]+logN) 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²N)/(F)] + tlogN) time. Finally, for t > F/6 we show how to improve the trapdoor protocol, 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), t=o(logN) and t ≤ (1−ϵ)F for a constant ϵ > 0, our protocols beat the classic Ω(log²N) 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.