License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2018.9
URN: urn:nbn:de:0030-drops-83029
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8302/
Go to the corresponding OASIcs Volume Portal

Berenbrink, Petra ; Kaaser, Dominik ; Kling, Peter ; Otterbach, Lena

Simple and Efficient Leader Election

pdf-format:
OASIcs-SOSA-2018-9.pdf (0.6 MB)

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.

BibTeX - Entry

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

Keywords: population protocols, leader election, distributed, randomized
Collection: 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Issue Date: 2018
Date of publication: 05.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI