Document Open Access Logo

Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols

Authors Yuichi Sudo , Ryota Eguchi, Taisuke Izumi, Toshimitsu Masuzawa

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.40.pdf
  • Filesize: 0.85 MB
  • 17 pages

Document Identifiers

Author Details

Yuichi Sudo
  • Hosei University, Tokyo, Japan
Ryota Eguchi
  • Nagoya Institute of Technology, Japan
Taisuke Izumi
  • Osaka University, Japan
Toshimitsu Masuzawa
  • Osaka University, Japan

Funding

This work was supported by JSPS KAKENHI Grant Numbers 19H04085 and 20H04140.

Acknowledgements

We truly thank anonymous reviewers for their constructive and helpful comments. We also thank Przemyslaw Uznanski and Eric Severson: The first author of this paper got one of the key ideas of this paper after the discussion with them at PODC 2019.

Cite AsGet BibTex

Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa. Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.40

Abstract

We consider the leader election problem in the population protocol model. In pragmatic settings of population protocols, self-stabilization is a highly desired feature owing to its fault resilience and the benefit of initialization freedom. However, the design of self-stabilizing leader election is possible only under a strong assumption (i.e., the knowledge of the exact size of a network) and rich computational resource (i.e., the number of states). Loose-stabilization is a promising relaxed concept of self-stabilization to address the aforementioned issue. Loose-stabilization guarantees that starting from any configuration, the network will reach a safe configuration where a single leader exists within a short time, and thereafter it will maintain the single leader for a long time, but not necessarily forever. The main contribution of this paper is giving a time-optimal loosely-stabilizing leader election protocol. The proposed protocol with design parameter τ ≥ 1 attains O(τ log n) parallel convergence time and Ω(n^τ) parallel holding time (i.e., the length of the period keeping the unique leader), both in expectation. This protocol is time-optimal in the sense of both the convergence and holding times in expectation because any loosely-stabilizing leader election protocol with the same length of the holding time is known to require Ω(τ log n) parallel time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • population protocols
  • leader election
  • loose-stabilization
  • self-stabilization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2560-2579. SIAM, 2017. Google Scholar
  2. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2221-2239. SIAM, 2018. Google Scholar
  3. Dan Alistarh, Bartłomiej Dudek, Adrian Kosowski, David Soloveichik, and Przemysław Uznański. Robust detection in leak-prone population protocols. In International Conference on DNA-Based Computers, pages 155-171. Springer, 2017. Google Scholar
  4. Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, pages 479-491, 2015. Google Scholar
  5. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. Google Scholar
  6. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. Google Scholar
  7. Dana Angluin, James. Aspnes, Michael J Fischer, and Hong Jiang. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems, 3(4):13, 2008. Google Scholar
  8. Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Proceedings of 52nd Annual ACM Symposium on Theory of Computing, 2020. Google Scholar
  9. Janna Burman, Ho-Lin Chen, Hsueh-Ping Chen, David Doty, Thomas Nowak, Eric Severson, and Chuan Xu. Time-optimal self-stabilizing leader election in population protocols. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 33-44, 2021. Google Scholar
  10. Shukai Cai, Taisuke Izumi, and Koichi Wada. How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory of Computing Systems, 50(3):433-445, 2012. Google Scholar
  11. Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 53-59, 2019. Google Scholar
  12. Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election in regular graphs. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 210-217, 2020. Google Scholar
  13. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing, 31(4):257-271, 2018. Google Scholar
  14. Leszek Gąsieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2653-2667. SIAM, 2018. Google Scholar
  15. Leszek Gąsieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. In The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, pages 93-102. ACM, 2019. Google Scholar
  16. Taisuke Izumi. On space and time complexity of loosely-stabilizing leader election. In International Colloquium on Structural Information and Communication Complexity, pages 299-312, 2015. Google Scholar
  17. Yuichi Sudo and Toshimitsu Masuzawa. Leader election requires logarithmic time in population protocols. Parallel Processing Letters, 30(01):2050005, 2020. Google Scholar
  18. Yuichi Sudo, Junya Nakamura, Yukiko Yamauchi, Fukuhito Ooshita, Hirotsugu. Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science, 444:100-112, 2012. Google Scholar
  19. Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Time-optimal leader election in population protocols. IEEE Transactions on Parallel and Distributed Systems, 2020. Google Scholar
  20. Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election on arbitrary graphs in population protocols without identifiers nor random numbers. In International Conference on Principles of Distributed Systems, 2015. Google Scholar
  21. Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. Loosely-stabilizing leader election for arbitrary graphs in population protocol model. IEEE Transactions on Parallel and Distributed Systems, 30(6):1359-1373, 2018. Google Scholar
  22. Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. Loosely-stabilizing leader election with polylogarithmic convergence time. Theoretical Computer Science, 806:617-631, 2020. Google Scholar
  23. Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Self-stabilizing population protocols with global knowledge. IEEE Transactions on Parallel and Distributed Systems, 32(12):3011-3023, 2021. Google Scholar
  24. Daisuke Yokota, Yuichi Sudo, and Toshimitsu Masuzawa. Time-optimal self-stabilizing leader election on rings in population protocols. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, (to appear), 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact