Document Open Access Logo

Brief Announcement: Loosely-stabilizing Leader Election with Polylogarithmic Convergence Time

Authors Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2018.52.pdf
  • Filesize: 304 kB
  • 3 pages

Document Identifiers

Subject Classification

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

Metrics

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

Abstract

We present a fast loosely-stabilizing leader election protocol in the population protocol model. It elects a unique leader in a poly-logarithmic time and holds the leader for a polynomial time with arbitrarily large degree in terms of parallel time, i.e, the number of steps per the population size.

Cite As Get BibTex

Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Brief Announcement: Loosely-stabilizing Leader Election with Polylogarithmic Convergence Time. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.52

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

References

  1. 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
  2. T. Izumi. On space and time complexity of loosely-stabilizing leader election. In SIROCCO, pages 299-312, 2015. Google Scholar
  3. Y. Sudo, J. Nakamura, Y. Yamauchi, F. Ooshita, et al. Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science, 444:100-112, 2012. Google Scholar
  4. Y. Sudo, F. Ooshita, H. Kakugawa, and T. Masuzawa. Loosely-stabilizing leader election on arbitrary graphs in population protocols. In OPODIS, pages 339-354, 2014. 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