DROPS

Document

DOI: 10.4230/OASIcs.SOSA.2018.9

Simple and Efficient Leader Election

Authors: Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:OASIcs.SOSA.2018.9,
  author =	{Berenbrink, Petra and Kaaser, Dominik and Kling, Peter and Otterbach, Lena},
  title =	{{Simple and Efficient Leader Election}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{9:1--9:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9},
  URN =		{urn:nbn:de:0030-drops-83029},
  doi =		{10.4230/OASIcs.SOSA.2018.9},
  annote =	{Keywords: population protocols, leader election, distributed, randomized}
}

Search Results

Documents authored by Otterbach, Lena

Simple and Efficient Leader Election

Abstract

Cite as

Thanks for your feedback!

Could not send message