LIPIcs.DISC.2018.52.pdf
- Filesize: 304 kB
- 3 pages
Document
Brief Announcement: Loosely-stabilizing Leader Election with Polylogarithmic Convergence Time
Authors
-
Part of:
Volume:
32nd International Symposium on Distributed Computing (DISC 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-10-04
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
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.
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)
0PDF Downloads
References
-
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.
-
T. Izumi. On space and time complexity of loosely-stabilizing leader election. In SIROCCO, pages 299-312, 2015.
-
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.
-
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.