OASIcs.SOSA.2018.9.pdf
- Filesize: 0.55 MB
- 11 pages
Document
Simple and Efficient Leader Election
Authors
-
Part of:
Volume:
1st Symposium on Simplicity in Algorithms (SOSA 2018)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-01-05
Cite As Get BibTex
Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.SOSA.2018.9
Abstract
We provide a simple and efficient population protocol for leader election that uses O(log n) states and elects exactly one leader in O(n (log n)^2) interactions with high probability and in expectation. Our analysis is simple and based on fundamental stochastic arguments. Our protocol combines the tournament based leader elimination by Alistarh and Gelashvili, ICALP'15, with the synthetic coin introduced by Alistarh et al., SODA'17.
Subject Classification
Keywords
- population protocols
- leader election
- distributed
- randomized
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-Space Trade-offs in Population Protocols. In Proc. SODA, pages 2560-2579, 2017.
-
Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. CoRR, abs/1704.04947, 2017.
-
Dan Alistarh and Rati Gelashvili. Polylogarithmic-Time Leader Election in Population Protocols. In Proc. ICALP, pages 479-491, 2015.
-
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.
-
Dana Angluin, James Aspnes, and David Eisenstat. Stably Computable Predicates Are Semilinear. In Proc. PODC, pages 292-299, New York, NY, USA, 2006.
-
Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007.
-
Andreas Bilke, Colin Cooper, Robert Elsässer, and Tomasz Radzik. Population protocols for leader election and exact majority with O(log² n) states and O(log² n) convergence time. CoRR, abs/1705.01146, 2017.
-
David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. CoRR, abs/1502.04246, 2015.
-
Leszek Gasieniec and Grzegorz Stachowiak. Fast Space Optimal Leader Election in Population Protocols. CoRR, abs/1704.07649, 2017.
-
Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vöcking. Randomized Rumor Spreading. In Proc. FOCS, pages 565-574, 2000.
-
Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.