Document Open Access Logo

Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time

Authors Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, Lawrence L. Larmore

PDF

File

Thumbnail PDF
PDF
LIPIcs.OPODIS.2018.30.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Self-organization
Keywords
  • Loose-stabilization
  • Population protocols
  • and Leader election

Metrics

Abstract

A loosely-stabilizing leader election protocol with polylogarithmic convergence time in the population protocol model is presented in this paper. In the population protocol model, which is a common abstract model of mobile sensor networks, it is known to be impossible to design a self-stabilizing leader election protocol. Thus, in our prior work, we introduced the concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage as self-stabilization in practice. Following this work, several loosely-stabilizing leader election protocols are presented. The loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a relatively short time, and keeps the unique leader for an sufficiently long time thereafter. The convergence times of all the existing loosely-stabilizing protocols, i.e., the expected time to reach a safe configuration, are polynomial in n where n is the number of nodes (while the holding times to keep the unique leader are exponential in n). In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, but arbitrarily large polynomial in n.

Cite As Get BibTex

Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, and Lawrence L. Larmore. Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.OPODIS.2018.30

Author Details

Yuichi Sudo
  • Graduate School of Information Science and Technology, Osaka University, Japan
Fukuhito Ooshita
  • Graduate School of Science and Technology, Nara Institute of Science and Technology, Japan
Hirotsugu Kakugawa
  • Graduate School of Information Science and Technology, Osaka University, Japan
Toshimitsu Masuzawa
  • Graduate School of Information Science and Technology, Osaka University, Japan
Ajoy K. Datta
  • Department of Computer Science, University of Nevada, Las Vegas, USA
Lawrence L. Larmore
  • Department of Computer Science, University of Nevada, Las Vegas, USA

References

  1. 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. Springer, 2015. Google Scholar
  2. Dan Alistarh, Rati Gelashvili, and Milan Vojnović. Fast and exact majority in population protocols. In the 34th ACM Symposium on Principles of Distributed Computing, pages 47-56, 2015. Google Scholar
  3. D. Angluin, J Aspnes, Z. Diamadi, M.J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. Google Scholar
  4. D. Angluin, J. Aspnes, M. J Fischer, and H. Jiang. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems, 3(4):13, 2008. Google Scholar
  5. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. Google Scholar
  6. J. Beauquier, P. Blanchard, and J. Burman. Self-stabilizing leader election in population protocols over arbitrary communication graphs. In International Conference on Principles of Distributed Systems, pages 38-52, 2013. Google Scholar
  7. S. Cai, T. Izumi, and K. 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
  8. D. Canepa and M. G. Potop-Butucaru. Stabilizing leader election in population protocols, 2007. http://hal.inria.fr/inria-00166632. Google Scholar
  9. M. J. Fischer and H. Jiang. Self-stabilizing Leader Election in Networks of Finite-State Anonymous Agents. In International Conference on Principles of Distributed Systems, pages 395-409, 2006. URL: http://dx.doi.org/10.1007/11945529_28.
  10. Leszek Gąsieniec and Grzegorz Staehowiak. 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
  11. T. 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
  12. M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. Google Scholar
  13. R. Mizoguchi, H. Ono, S. Kijima, and M. Yamashita. On space complexity of self-stabilizing leader election in mediated population protocol. Distributed Computing, 25(6):451-460, 2012. Google Scholar
  14. Y. Sudo, J. Nakamura, Y. Yamauchi, F. Ooshita, H. Kakugawa, and T. Masuzawa. Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science, 444:100-112, 2012. Google Scholar
  15. Y. Sudo, F. Ooshita, H. Kakugawa, and T. Masuzawa. Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols. In International Conference on Principles of Distributed Systems, pages 339-354, 2014. Google Scholar
  16. Y. Sudo, F. Ooshita, H. Kakugawa, and T. 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
  17. Yuichi Sudo, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. The Same Speed Timer in Population Protocols. In the 36th IEEE International Conference on Distributed Computing Systems, pages 252-261, 2016. Google Scholar
  18. X. Xu, Y. Yamauchi, S. Kijima, and M. Yamashita. Space Complexity of Self-Stabilizing Leader Election in Population Protocol Based on k-Interaction. In Symposium on Self-Stabilizing Systems, pages 86-97, 2013. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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