Oberseminar
Felix Biermeier, University of Hamburg
Mai 21, 2021, 12:00, zoom: https://uni-hamburg.zoom.us/j/94889228942
Title: Time-Optimal Self-Stabilizing Leader Election in Population Protocols
This work by Burman et al. has been recently accepted at PODC'21.
We consider the standard population protocol model, where (a priori) indistinguishable
and anonymous agents interact in pairs according to uniformly random scheduling. The
selfstabilizing leader election problem requires the protocol to converge on a single
leader agent
from any possible initial configuration. We initiate the study of time complexity of
population protocols solving this problem in its original setting: with probability 1, in
a complete
communication graph. The only previously known protocol by Cai, Izumi, and Wada
[Theor.Comput. Syst. 50] runs in expected parallel time $O(n^2)$ and has the optimal
number of n states
in a population of n agents. The existing protocol has the additional property that it
becomes silent, i.e., the agents? states eventually stop changing.
Observing that any silent protocol solving self-stabilizing leader election requires
$\Omega(n)$ expected parallel time, we introduce a silent protocol that uses optimal
$O(n)$ parallel time and
states. Without any silence constraints, we show that it is possible to solve
self-stabilizing leader election in asymptotically optimal expected parallel time of
$O(log n)$, but using at least exponential states (a quasipolynomial number of bits). All
of our protocols (and also that of Cai et al.) work by solving the more difficult ranking
problem: assigning agents the ranks $1, . . . , n$.