Leader Election Requires Logarithmic Time in Population Protocols
Abstract
This paper shows that every leader election protocol requires logarithmic stabilization time both in expectation and with high probability in the population protocol model. This lower bound holds even if each agent has knowledge of the exact size of a population and is allowed to use an arbitrarily large number of agent states. This lower bound concludes that the protocol given in [Sudo et al., SSS 2019] is time-optimal in expectation.
References
- 1. , Computation in networks of passively mobile finite-state sensors, Distributed Computing 18(4) (2006) 235–253. Crossref, ISI, Google Scholar
- 2. , Polylogarithmic-time leader election in population protocols, in Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming,
Springer (2015 ), pp. 479–491. Google Scholar - 3. , Time-space trade-offs in population protocols, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM (
2017 ), pp. 2560–2579. Google Scholar - 4. , Space-optimal majority in population protocols, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM (
2018 ), pp. 2221–2239. Google Scholar - 5. , Fast space optimal leader election in population protocols, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM (
2018 ), pp. 2653–2667. Google Scholar - 6. , Almost logarithmic-time space optimal leader election in population protocols, in The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, ACM (
2019 ), pp. 93–102. Google Scholar - 7. , Simple and fast approximate counting and leader election in populations, in Proceedings of the 20th International Symposium on Stabilizing, Safety, and Security of Distributed Systems,
Springer (2018 ), pp. 154–169. Google Scholar - 8. , Stable leader election in population protocols requires linear time, Distributed Computing 31(4) (2018) 257–271. Crossref, ISI, Google Scholar
- 9. , Loosely-stabilizing leader election in a population protocol model, Theoretical Computer Science 444 (2012) 100–112. Crossref, ISI, Google Scholar
- 10. , Loosely-stabilizing leader election with polylogarithmic convergence time, in 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) (
2018 ), pp. 30:1–30:16. Google Scholar - 11. , Brief announcement: Population protocols for leader election and exact majority with states and convergence time, in Proceedings of the 38th ACM Symposium on Principles of Distributed Computing,
Springer (2017 ), pp. 451–453. Google Scholar - 12. Y. Sudo et al., Logarithmic expected-time leader election in population protocol model, in Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (2019), to appear. Google Scholar
- 13. , Recent algorithmic advances in population protocols, ACM SIGACT News 49(03) (2018) 63–73. Crossref, Google Scholar
- 14. R. Elsässer and T. Radzik, Recent results in population protocols for exact majority and leader election, Bulletin of EATCS 3(126) (2018). Google Scholar
- 15. , Fast computation by population protocols with a leader, Distributed Computing 21(3) (2008) 183–199. Crossref, ISI, Google Scholar
- 16. , Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, 2005). Crossref, Google Scholar


