### 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^{2}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^{2}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^{2}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^{2}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.

Report No. 269 (PDF)