Simple and Efficient Leader Election Article Swipe

View

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

YOU? · · 2018 · Open Access · · DOI: https://doi.org/10.4230/oasics.sosa.2018.9

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.

Related Topics

Theoretical Computer Science

Concepts

Simple (philosophy) Tournament Leader election Protocol (science) Population Combinatorics Mathematics Computer science Discrete mathematics Theoretical computer science Sociology Pathology Philosophy Demography Alternative medicine Epistemology Medicine

Metadata

Type: article
Language: en
Landing Page: https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9
OA Status: green
Cited By: 24
Related Works: 20
OpenAlex ID: https://openalex.org/W2784304773

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2784304773

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.4230/oasics.sosa.2018.9

Digital Object Identifier
Title: Simple and Efficient Leader Election

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2018

Year of publication
Publication date: 2018-01-01

Full publication date if available
Authors: Petra Berenbrink, Dominik Kaaser, Peter Kling, Lena Otterbach

List of authors in order
Landing page: https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9

Direct OA link when available
Concepts: Simple (philosophy), Tournament, Leader election, Protocol (science), Population, Combinatorics, Mathematics, Computer science, Discrete mathematics, Theoretical computer science, Sociology, Pathology, Philosophy, Demography, Alternative medicine, Epistemology, Medicine

Top concepts (fields/topics) attached by OpenAlex
Cited by: 24

Total citation count in OpenAlex
Citations by year (recent): 2025: 2, 2024: 1, 2022: 2, 2021: 8, 2020: 6

Per-year citation counts (last 5 years)
Related works (count): 20

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2784304773
doi	https://doi.org/10.4230/oasics.sosa.2018.9
ids.doi	https://doi.org/10.4230/oasics.sosa.2018.9
ids.mag	2784304773
ids.openalex	https://openalex.org/W2784304773
fwci	4.0329808
type	article
title	Simple and Efficient Leader Election
biblio.issue
biblio.volume	61
biblio.last_page
biblio.first_page	11
topics[0].id	https://openalex.org/T10772
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.991100013256073
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1705
topics[0].subfield.display_name	Computer Networks and Communications
topics[0].display_name	Distributed systems and fault tolerance
topics[1].id	https://openalex.org/T10317
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9767000079154968
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Advanced Database Systems and Queries
topics[2].id	https://openalex.org/T11719
topics[2].field.id	https://openalex.org/fields/18
topics[2].field.display_name	Decision Sciences
topics[2].score	0.9706000089645386
topics[2].domain.id	https://openalex.org/domains/2
topics[2].domain.display_name	Social Sciences
topics[2].subfield.id	https://openalex.org/subfields/1803
topics[2].subfield.display_name	Management Science and Operations Research
topics[2].display_name	Data Quality and Management
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C2780586882
concepts[0].level	2
concepts[0].score	0.8074432611465454
concepts[0].wikidata	https://www.wikidata.org/wiki/Q7520643
concepts[0].display_name	Simple (philosophy)
concepts[1].id	https://openalex.org/C136975688
concepts[1].level	2
concepts[1].score	0.7819374799728394
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1320634
concepts[1].display_name	Tournament
concepts[2].id	https://openalex.org/C53480672
concepts[2].level	2
concepts[2].score	0.7534497976303101
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1424189
concepts[2].display_name	Leader election
concepts[3].id	https://openalex.org/C2780385302
concepts[3].level	3
concepts[3].score	0.5927292108535767
concepts[3].wikidata	https://www.wikidata.org/wiki/Q367158
concepts[3].display_name	Protocol (science)
concepts[4].id	https://openalex.org/C2908647359
concepts[4].level	2
concepts[4].score	0.486272931098938
concepts[4].wikidata	https://www.wikidata.org/wiki/Q2625603
concepts[4].display_name	Population
concepts[5].id	https://openalex.org/C114614502
concepts[5].level	1
concepts[5].score	0.45277079939842224
concepts[5].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[5].display_name	Combinatorics
concepts[6].id	https://openalex.org/C33923547
concepts[6].level	0
concepts[6].score	0.4372675120830536
concepts[6].wikidata	https://www.wikidata.org/wiki/Q395
concepts[6].display_name	Mathematics
concepts[7].id	https://openalex.org/C41008148
concepts[7].level	0
concepts[7].score	0.4080265760421753
concepts[7].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[7].display_name	Computer science
concepts[8].id	https://openalex.org/C118615104
concepts[8].level	1
concepts[8].score	0.40303122997283936
concepts[8].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[8].display_name	Discrete mathematics
concepts[9].id	https://openalex.org/C80444323
concepts[9].level	1
concepts[9].score	0.25272825360298157
concepts[9].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[9].display_name	Theoretical computer science
concepts[10].id	https://openalex.org/C144024400
concepts[10].level	0
concepts[10].score	0.0
concepts[10].wikidata	https://www.wikidata.org/wiki/Q21201
concepts[10].display_name	Sociology
concepts[11].id	https://openalex.org/C142724271
concepts[11].level	1
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q7208
concepts[11].display_name	Pathology
concepts[12].id	https://openalex.org/C138885662
concepts[12].level	0
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q5891
concepts[12].display_name	Philosophy
concepts[13].id	https://openalex.org/C149923435
concepts[13].level	1
concepts[13].score	0.0
concepts[13].wikidata	https://www.wikidata.org/wiki/Q37732
concepts[13].display_name	Demography
concepts[14].id	https://openalex.org/C204787440
concepts[14].level	2
concepts[14].score	0.0
concepts[14].wikidata	https://www.wikidata.org/wiki/Q188504
concepts[14].display_name	Alternative medicine
concepts[15].id	https://openalex.org/C111472728
concepts[15].level	1
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q9471
concepts[15].display_name	Epistemology
concepts[16].id	https://openalex.org/C71924100
concepts[16].level	0
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q11190
concepts[16].display_name	Medicine
keywords[0].id	https://openalex.org/keywords/simple
keywords[0].score	0.8074432611465454
keywords[0].display_name	Simple (philosophy)
keywords[1].id	https://openalex.org/keywords/tournament
keywords[1].score	0.7819374799728394
keywords[1].display_name	Tournament
keywords[2].id	https://openalex.org/keywords/leader-election
keywords[2].score	0.7534497976303101
keywords[2].display_name	Leader election
keywords[3].id	https://openalex.org/keywords/protocol
keywords[3].score	0.5927292108535767
keywords[3].display_name	Protocol (science)
keywords[4].id	https://openalex.org/keywords/population
keywords[4].score	0.486272931098938
keywords[4].display_name	Population
keywords[5].id	https://openalex.org/keywords/combinatorics
keywords[5].score	0.45277079939842224
keywords[5].display_name	Combinatorics
keywords[6].id	https://openalex.org/keywords/mathematics
keywords[6].score	0.4372675120830536
keywords[6].display_name	Mathematics
keywords[7].id	https://openalex.org/keywords/computer-science
keywords[7].score	0.4080265760421753
keywords[7].display_name	Computer science
keywords[8].id	https://openalex.org/keywords/discrete-mathematics
keywords[8].score	0.40303122997283936
keywords[8].display_name	Discrete mathematics
keywords[9].id	https://openalex.org/keywords/theoretical-computer-science
keywords[9].score	0.25272825360298157
keywords[9].display_name	Theoretical computer science
language	en
locations[0].id	pmh:oai:drops-oai.dagstuhl.de:8302
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306402524
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	False
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
locations[0].source.host_organization	https://openalex.org/I2799853480
locations[0].source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
locations[0].source.host_organization_lineage	https://openalex.org/I2799853480
locations[0].license	cc-by
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	InProceedings
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name
locations[0].landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9
locations[1].id	doi:10.4230/oasics.sosa.2018.9
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S7407052059
locations[1].source.type	repository
locations[1].source.is_oa	False
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	Dagstuhl Research Online Publication Server
locations[1].source.host_organization
locations[1].source.host_organization_name
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.4230/oasics.sosa.2018.9
locations[2].id	mag:2784304773
locations[2].is_oa	False
locations[2].source
locations[2].license
locations[2].pdf_url
locations[2].version
locations[2].raw_type
locations[2].license_id
locations[2].is_accepted	False
locations[2].is_published
locations[2].raw_source_name
locations[2].landing_page_url	https://drops.dagstuhl.de/opus/volltexte/2018/8302/pdf/OASIcs-SOSA-2018-9.pdf/
indexed_in	datacite
authorships[0].author.id	https://openalex.org/A5072910141
authorships[0].author.orcid	https://orcid.org/0000-0002-6930-3259
authorships[0].author.display_name	Petra Berenbrink
authorships[0].author_position	first
authorships[0].raw_author_name	Petra Berenbrink
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5085356058
authorships[1].author.orcid	https://orcid.org/0000-0002-2083-7145
authorships[1].author.display_name	Dominik Kaaser
authorships[1].author_position	middle
authorships[1].raw_author_name	Dominik Kaaser
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5007675663
authorships[2].author.orcid	https://orcid.org/0000-0003-0000-8689
authorships[2].author.display_name	Peter Kling
authorships[2].author_position	middle
authorships[2].raw_author_name	Peter Kling
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5089138768
authorships[3].author.orcid
authorships[3].author.display_name	Lena Otterbach
authorships[3].author_position	last
authorships[3].raw_author_name	Lena Otterbach
authorships[3].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Simple and Efficient Leader Election
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10772
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.991100013256073
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1705
primary_topic.subfield.display_name	Computer Networks and Communications
primary_topic.display_name	Distributed systems and fault tolerance
related_works	https://openalex.org/W2706788079, https://openalex.org/W2963943319, https://openalex.org/W3106250499, https://openalex.org/W2743261842, https://openalex.org/W2006072889, https://openalex.org/W2738922137, https://openalex.org/W2399651233, https://openalex.org/W2026030032, https://openalex.org/W3016416987, https://openalex.org/W2963844133, https://openalex.org/W2059505795, https://openalex.org/W2907311168, https://openalex.org/W2275408670, https://openalex.org/W2091275311, https://openalex.org/W2898165178, https://openalex.org/W2008591003, https://openalex.org/W1990476699, https://openalex.org/W2401955682, https://openalex.org/W2122466171, https://openalex.org/W1991095994
cited_by_count	24
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	2
counts_by_year[1].year	2024
counts_by_year[1].cited_by_count	1
counts_by_year[2].year	2022
counts_by_year[2].cited_by_count	2
counts_by_year[3].year	2021
counts_by_year[3].cited_by_count	8
counts_by_year[4].year	2020
counts_by_year[4].cited_by_count	6
counts_by_year[5].year	2019
counts_by_year[5].cited_by_count	4
counts_by_year[6].year	2018
counts_by_year[6].cited_by_count	1
locations_count	3
best_oa_location.id	pmh:oai:drops-oai.dagstuhl.de:8302
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306402524
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
best_oa_location.source.host_organization	https://openalex.org/I2799853480
best_oa_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
best_oa_location.source.host_organization_lineage	https://openalex.org/I2799853480
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version	publishedVersion
best_oa_location.raw_type	InProceedings
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9
primary_location.id	pmh:oai:drops-oai.dagstuhl.de:8302
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306402524
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	False
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
primary_location.source.host_organization	https://openalex.org/I2799853480
primary_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
primary_location.source.host_organization_lineage	https://openalex.org/I2799853480
primary_location.license	cc-by
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	InProceedings
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name
primary_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9
publication_date	2018-01-01
publication_year	2018
referenced_works_count	0
abstract_inverted_index.a	2
abstract_inverted_index.We	0
abstract_inverted_index.by	50, 60
abstract_inverted_index.et	62
abstract_inverted_index.in	21, 30
abstract_inverted_index.is	34
abstract_inverted_index.n)	14
abstract_inverted_index.on	38
abstract_inverted_index.O(n	22
abstract_inverted_index.Our	32, 42
abstract_inverted_index.and	4, 16, 29, 36, 52
abstract_inverted_index.for	8
abstract_inverted_index.one	19
abstract_inverted_index.the	45, 56
abstract_inverted_index.(log	23
abstract_inverted_index.al.,	63
abstract_inverted_index.coin	58
abstract_inverted_index.high	27
abstract_inverted_index.that	11
abstract_inverted_index.uses	12
abstract_inverted_index.with	26, 55
abstract_inverted_index.O(log	13
abstract_inverted_index.based	37, 47
abstract_inverted_index.n)^2)	24
abstract_inverted_index.elects	17
abstract_inverted_index.leader	9, 20, 48
abstract_inverted_index.simple	3, 35
abstract_inverted_index.states	15
abstract_inverted_index.exactly	18
abstract_inverted_index.provide	1
abstract_inverted_index.Alistarh	51, 61
abstract_inverted_index.SODA'17.	64
abstract_inverted_index.analysis	33
abstract_inverted_index.combines	44
abstract_inverted_index.election	10
abstract_inverted_index.protocol	7, 43
abstract_inverted_index.ICALP'15,	54
abstract_inverted_index.efficient	5
abstract_inverted_index.synthetic	57
abstract_inverted_index.arguments.	41
abstract_inverted_index.introduced	59
abstract_inverted_index.population	6
abstract_inverted_index.stochastic	40
abstract_inverted_index.tournament	46
abstract_inverted_index.Gelashvili,	53
abstract_inverted_index.elimination	49
abstract_inverted_index.fundamental	39
abstract_inverted_index.probability	28
abstract_inverted_index.expectation.	31
abstract_inverted_index.interactions	25
cited_by_percentile_year.max	99
cited_by_percentile_year.min	90
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile.value	0.93290249
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True