World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Leader Election Requires Logarithmic Time in Population Protocols

    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. D. Angluin et al., Computation in networks of passively mobile finite-state sensors, Distributed Computing 18(4) (2006) 235–253. Crossref, ISIGoogle Scholar
    • 2. D. Alistarh and R. Gelashvili, 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. D. Alistarh et al., 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. D. Alistarh, J. Aspnes and R. Gelashvili, 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. L. Gasieniec and G. Stachowiak, 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. L. Gasieniec, G. Stachowiak and P. Uznanski, 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. O. Michail, P. G. Spirakis and M. Theofilatos, 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. D. Doty and D. Soloveichik, Stable leader election in population protocols requires linear time, Distributed Computing 31(4) (2018) 257–271. Crossref, ISIGoogle Scholar
    • 9. Y. Sudo et al., Loosely-stabilizing leader election in a population protocol model, Theoretical Computer Science 444 (2012) 100–112. Crossref, ISIGoogle Scholar
    • 10. Y. Sudo et al., 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. A. Bilke et al., Brief announcement: Population protocols for leader election and exact majority with o(log2n) states and o(log2n) 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. D. Alistarh and R. Gelashvili, Recent algorithmic advances in population protocols, ACM SIGACT News 49(03) (2018) 63–73. CrossrefGoogle 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. D. Angluin, J. Aspnes and D. Eisenstat, Fast computation by population protocols with a leader, Distributed Computing 21(3) (2008) 183–199. Crossref, ISIGoogle Scholar
    • 16. M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, 2005). CrossrefGoogle Scholar