2019/07/31 by Janna Burman, Ho-Lin Chen, Hsueh-Ping Chen +4 · 1 citation
Computer Science · #cs.DC
paper · pdf · doi:10.1007/s00446-026-00509-y
published as PODC 2021: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, July 2021, pages 33-44 · fixed typo in Figure 2
arxiv created 2021/11/29 · arxiv updated 2021/11/30 · crossref issued 2026/08/03 · crossref published 2026/08/03 · crossref published-online 2026/08/03 · crossref created 2026/08/03 · crossref deposited 2026/08/03 · crossref indexed 2026/08/03 · crossref published-print 2026/09/01
We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing 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 Θ(n2) 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 Ω(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 quasi-polynomial 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.