2026-07-21T23:33:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8302 2024-03-06T10:30:16Z ddc:004 open_access

Simple and Efficient Leader Election Berenbrink, Petra Kaaser, Dominik Kling, Peter Otterbach, Lena population protocols leader election distributed randomized 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petra Berenbrink and Dominik Kaaser and Peter Kling and Lena Otterbach 2018 Is Part Of OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2018.9 urn:nbn:de:0030-drops-83029 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9 eng https://creativecommons.org/licenses/by/3.0/legalcode