**Abstract:** In this paper, we study the {\em 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 $\freq$ frequencies. To model unpredictable congestion, we assume an abstract {\em interference adversary} that can choose up to $t < \freq$ 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 {\em same} leader, with high probability.

We begin by establishing a lower bound of $\Omega\big( \frac{ \log^2{N} }{ (\freq -t)\log{\log{N}}} + \frac{ \freq t }{ \freq – t} \cdot \log{N}\big)$ 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 {\em herald nodes}, that works in $O\big(\frac{\log^2{N}}{\freq}+\log N\big)$ time. For $1 \leq t \leq \freq/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\big(\frac{\log^2{N}}{\freq} + t\log{N}\big)$ time. Finally, for $t > \freq/6$ we show how to improve the {\em trapdoor protocol} of~\cite{podc09}, used to solve a similar problem in a non-optimal manner, to solve leader election in optimal $O\big( \frac{\log{N} + \freq t}{\freq-t} \cdot \log{N} \big)$ time, for (only) these large values of $t$. We also observe that if $\freq=\omega(1)$ and $t \leq (1-\eps)\freq$ for a constant $\eps>0$, our protocols beat the classic $\Omega(\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.

Guest: Sebastian Daum

Host: Yvonne-Anne Pignolet

Podcast: Play in new window
| Download