An O(sqrt n) Space Bound for Obstruction-Free Leader Election

George Giakkoupis, Maryam Helmi, Lisa Higham and Philipp Woelfel.

Abstract:

We present a deterministic obstruction-free implementation
of leader election from O(n^{1/2}) atomic O(log n)-bit registers in the stan-
dard asynchronous shared memory system with n processes. We provide
also a technique to transform any deterministic obstruction-free algo-
rithm, in which any process can finish if it runs for b steps without
interference, into a randomized wait-free algorithm for the oblivious ad-
versary, in which the expected step complexity is polynomial in n and
b. This transformation allows us to combine our obstruction-free algo-
rithm with the leader election algorithm by Giakkoupis and Woelfel [21],
to obtain a fast randomized leader election (and thus test-and-set) im-
plementation from O(n^{1/2}) O(log n)-bit registers, that has expected step
complexity O(log n) against the oblivious adversary.
Our algorithm provides the first sub-linear space upper bound for obstru-
ction-free leader election. A lower bound of $\Omega(log n)$ has been known
since 1989 [29]. Our research is also motivated by the long-standing open
problem whether there is an obstruction-free consensus algorithm which
uses fewer than n registers.

Distributed Protocols for Leader Election: a Game-Theoretic Perspective

Ittai Abraham, Danny Dolev, and Joseph Y. Halpern

Abstract. We do a game-theoretic analysis of leader election, under the assumption
that each agent prefers to have some leader than to have no leader at all. We
show that it is possible to obtain a fair Nash equilibrium, where each agent has
an equal probability of being elected leader, in a completely connected network,
in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In
the asynchronous setting, Nash equilibrium is not quite the right solution concept.
Rather, we must consider ex post Nash equilibrium; this means that we
have a Nash equilibrium no matter what a scheduling adversary does. We show
that ex post Nash equilibrium is attainable in the asynchronous setting in all the
networks we consider, using a protocol with bounded running time. However,
in the asynchronous setting, we require that n > 2. We can get a fair e-Nash
equilibrium if n = 2 in the asynchronous setting, under some cryptographic assumptions
(specifically, the existence of a pseudo-random number generator and
polynomially-bounded agents), using ideas from bit-commitment protocols. We
then generalize these results to a setting where we can have deviations by a coalition
of size k. In this case, we can get what we call a fair k-resilient equilibrium
if n > 2k; under the same cryptographic assumptions, we can a get a k-resilient
equilibrium if n = 2k. Finally, we show that, under minimal assumptions, not
only do our protocols give a Nash equilibrium, they also give a sequential equilibrium
[23], so players even play optimally off the equilibrium path.

Guests: Danny Dolev and Joseph Y. Halpern

Host: Stefan Schmid

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.