Optimal time and space leader election in population protocols Article Swipe

View

Petra Berenbrink , George Giakkoupis , Peter Kling ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.1145/3357713.3384312

Full verions, including all proofs

Related Topics

Computer Science

Combinatorics

Theoretical Computer Science

Mathematics

Discrete Mathematics

Algorithm

Artificial Intelligence

Demography

Alternative Medicine

Mathematical Analysis

Medicine

Histopathology

Concepts

Leader election Pairwise comparison Computer science Protocol (science) Upper and lower bounds Population State (computer science) Computational complexity theory Binary logarithm Combinatorics Time complexity Theoretical computer science Mathematics Discrete mathematics Algorithm Artificial intelligence Demography Alternative medicine Mathematical analysis Medicine Sociology Pathology

Metadata

Type: preprint
Language: en
Landing Page: https://doi.org/10.1145/3357713.3384312
OA Status: green
Cited By: 45
References: 24
Related Works: 10
OpenAlex ID: https://openalex.org/W3016416987

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1145/3357713.3384312

Digital Object Identifier
Title: Optimal time and space leader election in population protocols

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2020

Year of publication
Publication date: 2020-06-22

Full publication date if available
Authors: Petra Berenbrink, George Giakkoupis, Peter Kling

List of authors in order
Landing page: https://doi.org/10.1145/3357713.3384312

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://inria.hal.science/hal-02545348

Direct OA link when available
Concepts: Leader election, Pairwise comparison, Computer science, Protocol (science), Upper and lower bounds, Population, State (computer science), Computational complexity theory, Binary logarithm, Combinatorics, Time complexity, Theoretical computer science, Mathematics, Discrete mathematics, Algorithm, Artificial intelligence, Demography, Alternative medicine, Mathematical analysis, Medicine, Sociology, Pathology

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

Total citation count in OpenAlex
Citations by year (recent): 2025: 6, 2024: 6, 2022: 5, 2021: 19, 2020: 7

Per-year citation counts (last 5 years)
References (count): 24

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W3016416987
doi	https://doi.org/10.1145/3357713.3384312
ids.doi	https://doi.org/10.1145/3357713.3384312
ids.mag	3016416987
ids.openalex	https://openalex.org/W3016416987
fwci	5.25550566
type	preprint
title	Optimal time and space leader election in population protocols
biblio.issue
biblio.volume
biblio.last_page	129
biblio.first_page	119
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.9991999864578247
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/T11010
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9933000206947327
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	Logic, Reasoning, and Knowledge
topics[2].id	https://openalex.org/T12029
topics[2].field.id	https://openalex.org/fields/13
topics[2].field.display_name	Biochemistry, Genetics and Molecular Biology
topics[2].score	0.9848999977111816
topics[2].domain.id	https://openalex.org/domains/1
topics[2].domain.display_name	Life Sciences
topics[2].subfield.id	https://openalex.org/subfields/1312
topics[2].subfield.display_name	Molecular Biology
topics[2].display_name	DNA and Biological Computing
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C53480672
concepts[0].level	2
concepts[0].score	0.8477292060852051
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1424189
concepts[0].display_name	Leader election
concepts[1].id	https://openalex.org/C184898388
concepts[1].level	2
concepts[1].score	0.6855984330177307
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1435712
concepts[1].display_name	Pairwise comparison
concepts[2].id	https://openalex.org/C41008148
concepts[2].level	0
concepts[2].score	0.5993992686271667
concepts[2].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[2].display_name	Computer science
concepts[3].id	https://openalex.org/C2780385302
concepts[3].level	3
concepts[3].score	0.5908781290054321
concepts[3].wikidata	https://www.wikidata.org/wiki/Q367158
concepts[3].display_name	Protocol (science)
concepts[4].id	https://openalex.org/C77553402
concepts[4].level	2
concepts[4].score	0.581408679485321
concepts[4].wikidata	https://www.wikidata.org/wiki/Q13222579
concepts[4].display_name	Upper and lower bounds
concepts[5].id	https://openalex.org/C2908647359
concepts[5].level	2
concepts[5].score	0.5700111389160156
concepts[5].wikidata	https://www.wikidata.org/wiki/Q2625603
concepts[5].display_name	Population
concepts[6].id	https://openalex.org/C48103436
concepts[6].level	2
concepts[6].score	0.5635102391242981
concepts[6].wikidata	https://www.wikidata.org/wiki/Q599031
concepts[6].display_name	State (computer science)
concepts[7].id	https://openalex.org/C179799912
concepts[7].level	2
concepts[7].score	0.5235664248466492
concepts[7].wikidata	https://www.wikidata.org/wiki/Q205084
concepts[7].display_name	Computational complexity theory
concepts[8].id	https://openalex.org/C63553672
concepts[8].level	2
concepts[8].score	0.46020007133483887
concepts[8].wikidata	https://www.wikidata.org/wiki/Q581168
concepts[8].display_name	Binary logarithm
concepts[9].id	https://openalex.org/C114614502
concepts[9].level	1
concepts[9].score	0.4559810757637024
concepts[9].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[9].display_name	Combinatorics
concepts[10].id	https://openalex.org/C311688
concepts[10].level	2
concepts[10].score	0.44716745615005493
concepts[10].wikidata	https://www.wikidata.org/wiki/Q2393193
concepts[10].display_name	Time complexity
concepts[11].id	https://openalex.org/C80444323
concepts[11].level	1
concepts[11].score	0.4129830002784729
concepts[11].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[11].display_name	Theoretical computer science
concepts[12].id	https://openalex.org/C33923547
concepts[12].level	0
concepts[12].score	0.4121285080909729
concepts[12].wikidata	https://www.wikidata.org/wiki/Q395
concepts[12].display_name	Mathematics
concepts[13].id	https://openalex.org/C118615104
concepts[13].level	1
concepts[13].score	0.3621801733970642
concepts[13].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[13].display_name	Discrete mathematics
concepts[14].id	https://openalex.org/C11413529
concepts[14].level	1
concepts[14].score	0.25520822405815125
concepts[14].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[14].display_name	Algorithm
concepts[15].id	https://openalex.org/C154945302
concepts[15].level	1
concepts[15].score	0.12554621696472168
concepts[15].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[15].display_name	Artificial intelligence
concepts[16].id	https://openalex.org/C149923435
concepts[16].level	1
concepts[16].score	0.06704902648925781
concepts[16].wikidata	https://www.wikidata.org/wiki/Q37732
concepts[16].display_name	Demography
concepts[17].id	https://openalex.org/C204787440
concepts[17].level	2
concepts[17].score	0.0
concepts[17].wikidata	https://www.wikidata.org/wiki/Q188504
concepts[17].display_name	Alternative medicine
concepts[18].id	https://openalex.org/C134306372
concepts[18].level	1
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[18].display_name	Mathematical analysis
concepts[19].id	https://openalex.org/C71924100
concepts[19].level	0
concepts[19].score	0.0
concepts[19].wikidata	https://www.wikidata.org/wiki/Q11190
concepts[19].display_name	Medicine
concepts[20].id	https://openalex.org/C144024400
concepts[20].level	0
concepts[20].score	0.0
concepts[20].wikidata	https://www.wikidata.org/wiki/Q21201
concepts[20].display_name	Sociology
concepts[21].id	https://openalex.org/C142724271
concepts[21].level	1
concepts[21].score	0.0
concepts[21].wikidata	https://www.wikidata.org/wiki/Q7208
concepts[21].display_name	Pathology
keywords[0].id	https://openalex.org/keywords/leader-election
keywords[0].score	0.8477292060852051
keywords[0].display_name	Leader election
keywords[1].id	https://openalex.org/keywords/pairwise-comparison
keywords[1].score	0.6855984330177307
keywords[1].display_name	Pairwise comparison
keywords[2].id	https://openalex.org/keywords/computer-science
keywords[2].score	0.5993992686271667
keywords[2].display_name	Computer science
keywords[3].id	https://openalex.org/keywords/protocol
keywords[3].score	0.5908781290054321
keywords[3].display_name	Protocol (science)
keywords[4].id	https://openalex.org/keywords/upper-and-lower-bounds
keywords[4].score	0.581408679485321
keywords[4].display_name	Upper and lower bounds
keywords[5].id	https://openalex.org/keywords/population
keywords[5].score	0.5700111389160156
keywords[5].display_name	Population
keywords[6].id	https://openalex.org/keywords/state
keywords[6].score	0.5635102391242981
keywords[6].display_name	State (computer science)
keywords[7].id	https://openalex.org/keywords/computational-complexity-theory
keywords[7].score	0.5235664248466492
keywords[7].display_name	Computational complexity theory
keywords[8].id	https://openalex.org/keywords/binary-logarithm
keywords[8].score	0.46020007133483887
keywords[8].display_name	Binary logarithm
keywords[9].id	https://openalex.org/keywords/combinatorics
keywords[9].score	0.4559810757637024
keywords[9].display_name	Combinatorics
keywords[10].id	https://openalex.org/keywords/time-complexity
keywords[10].score	0.44716745615005493
keywords[10].display_name	Time complexity
keywords[11].id	https://openalex.org/keywords/theoretical-computer-science
keywords[11].score	0.4129830002784729
keywords[11].display_name	Theoretical computer science
keywords[12].id	https://openalex.org/keywords/mathematics
keywords[12].score	0.4121285080909729
keywords[12].display_name	Mathematics
keywords[13].id	https://openalex.org/keywords/discrete-mathematics
keywords[13].score	0.3621801733970642
keywords[13].display_name	Discrete mathematics
keywords[14].id	https://openalex.org/keywords/algorithm
keywords[14].score	0.25520822405815125
keywords[14].display_name	Algorithm
keywords[15].id	https://openalex.org/keywords/artificial-intelligence
keywords[15].score	0.12554621696472168
keywords[15].display_name	Artificial intelligence
keywords[16].id	https://openalex.org/keywords/demography
keywords[16].score	0.06704902648925781
keywords[16].display_name	Demography
language	en
locations[0].id	doi:10.1145/3357713.3384312
locations[0].is_oa	False
locations[0].source
locations[0].license
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	proceedings-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
locations[0].landing_page_url	https://doi.org/10.1145/3357713.3384312
locations[1].id	pmh:oai:HAL:hal-02545348v1
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306402512
locations[1].source.issn
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	HAL (Le Centre pour la Communication Scientifique Directe)
locations[1].source.host_organization	https://openalex.org/I1294671590
locations[1].source.host_organization_name	Centre National de la Recherche Scientifique
locations[1].source.host_organization_lineage	https://openalex.org/I1294671590
locations[1].license	other-oa
locations[1].pdf_url
locations[1].version	submittedVersion
locations[1].raw_type	Conference papers
locations[1].license_id	https://openalex.org/licenses/other-oa
locations[1].is_accepted	False
locations[1].is_published	False
locations[1].raw_source_name	STOC 2020 - 52nd Annual ACM Symposium on Theory of Computing, Jun 2020, Chicago, United States. pp.1-29, ⟨10.1145/3357713.3384312⟩
locations[1].landing_page_url	https://inria.hal.science/hal-02545348
indexed_in	crossref
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].countries	DE
authorships[0].affiliations[0].institution_ids	https://openalex.org/I159176309
authorships[0].affiliations[0].raw_affiliation_string	University of Hamburg, Germany
authorships[0].institutions[0].id	https://openalex.org/I159176309
authorships[0].institutions[0].ror	https://ror.org/00g30e956
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I159176309
authorships[0].institutions[0].country_code	DE
authorships[0].institutions[0].display_name	Universität Hamburg
authorships[0].author_position	first
authorships[0].raw_author_name	Petra Berenbrink
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	University of Hamburg, Germany
authorships[1].author.id	https://openalex.org/A5006944198
authorships[1].author.orcid	https://orcid.org/0000-0002-8023-4485
authorships[1].author.display_name	George Giakkoupis
authorships[1].countries	FR
authorships[1].affiliations[0].institution_ids	https://openalex.org/I1294671590, https://openalex.org/I2802519937, https://openalex.org/I56067802
authorships[1].affiliations[0].raw_affiliation_string	Inria, France / University of Rennes, France / CNRS, France / IRISA, France
authorships[1].affiliations[1].raw_affiliation_string	the World Is Distributed Exploring the tension between scale and coordination
authorships[1].institutions[0].id	https://openalex.org/I1294671590
authorships[1].institutions[0].ror	https://ror.org/02feahw73
authorships[1].institutions[0].type	government
authorships[1].institutions[0].lineage	https://openalex.org/I1294671590
authorships[1].institutions[0].country_code	FR
authorships[1].institutions[0].display_name	Centre National de la Recherche Scientifique
authorships[1].institutions[1].id	https://openalex.org/I2802519937
authorships[1].institutions[1].ror	https://ror.org/00myn0z94
authorships[1].institutions[1].type	facility
authorships[1].institutions[1].lineage	https://openalex.org/I1294671590, https://openalex.org/I1294671590, https://openalex.org/I1326498283, https://openalex.org/I205703379, https://openalex.org/I2802204017, https://openalex.org/I2802519937, https://openalex.org/I28221208, https://openalex.org/I4210127572, https://openalex.org/I4210145102, https://openalex.org/I4210159245, https://openalex.org/I56067802
authorships[1].institutions[1].country_code	FR
authorships[1].institutions[1].display_name	Institut de Recherche en Informatique et Systèmes Aléatoires
authorships[1].institutions[2].id	https://openalex.org/I56067802
authorships[1].institutions[2].ror	https://ror.org/015m7wh34
authorships[1].institutions[2].type	education
authorships[1].institutions[2].lineage	https://openalex.org/I56067802
authorships[1].institutions[2].country_code	FR
authorships[1].institutions[2].display_name	Université de Rennes
authorships[1].author_position	middle
authorships[1].raw_author_name	George Giakkoupis
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Inria, France / University of Rennes, France / CNRS, France / IRISA, France, the World Is Distributed Exploring the tension between scale and coordination
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].countries	DE
authorships[2].affiliations[0].institution_ids	https://openalex.org/I159176309
authorships[2].affiliations[0].raw_affiliation_string	University of Hamburg, Germany
authorships[2].institutions[0].id	https://openalex.org/I159176309
authorships[2].institutions[0].ror	https://ror.org/00g30e956
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I159176309
authorships[2].institutions[0].country_code	DE
authorships[2].institutions[0].display_name	Universität Hamburg
authorships[2].author_position	last
authorships[2].raw_author_name	Peter Kling
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	University of Hamburg, Germany
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://inria.hal.science/hal-02545348
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Optimal time and space leader election in population protocols
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
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.9991999864578247
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/W4394667721, https://openalex.org/W2789179878, https://openalex.org/W2601062540, https://openalex.org/W3097369619, https://openalex.org/W3209455166, https://openalex.org/W1973013791, https://openalex.org/W2952144494, https://openalex.org/W4287691960, https://openalex.org/W3046990805, https://openalex.org/W3210762197
cited_by_count	45
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	6
counts_by_year[1].year	2024
counts_by_year[1].cited_by_count	6
counts_by_year[2].year	2022
counts_by_year[2].cited_by_count	5
counts_by_year[3].year	2021
counts_by_year[3].cited_by_count	19
counts_by_year[4].year	2020
counts_by_year[4].cited_by_count	7
counts_by_year[5].year	2019
counts_by_year[5].cited_by_count	2
locations_count	2
best_oa_location.id	pmh:oai:HAL:hal-02545348v1
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306402512
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	HAL (Le Centre pour la Communication Scientifique Directe)
best_oa_location.source.host_organization	https://openalex.org/I1294671590
best_oa_location.source.host_organization_name	Centre National de la Recherche Scientifique
best_oa_location.source.host_organization_lineage	https://openalex.org/I1294671590
best_oa_location.license	other-oa
best_oa_location.pdf_url
best_oa_location.version	submittedVersion
best_oa_location.raw_type	Conference papers
best_oa_location.license_id	https://openalex.org/licenses/other-oa
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name	STOC 2020 - 52nd Annual ACM Symposium on Theory of Computing, Jun 2020, Chicago, United States. pp.1-29, ⟨10.1145/3357713.3384312⟩
best_oa_location.landing_page_url	https://inria.hal.science/hal-02545348
primary_location.id	doi:10.1145/3357713.3384312
primary_location.is_oa	False
primary_location.source
primary_location.license
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	proceedings-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
primary_location.landing_page_url	https://doi.org/10.1145/3357713.3384312
publication_date	2020-06-22
publication_year	2020
referenced_works	https://openalex.org/W2952048613, https://openalex.org/W2963943319, https://openalex.org/W2399651233, https://openalex.org/W2898165178, https://openalex.org/W2026030032, https://openalex.org/W2706788079, https://openalex.org/W2006072889, https://openalex.org/W2059505795, https://openalex.org/W2899320093, https://openalex.org/W3016416987, https://openalex.org/W2784304773, https://openalex.org/W2963477229, https://openalex.org/W2240903249, https://openalex.org/W858254743, https://openalex.org/W1676436804, https://openalex.org/W2962724086, https://openalex.org/W2743261842, https://openalex.org/W2768998600, https://openalex.org/W2609887493, https://openalex.org/W2963844133, https://openalex.org/W2962922536, https://openalex.org/W2907311168, https://openalex.org/W3106250499, https://openalex.org/W3046827924
referenced_works_count	24
abstract_inverted_index.all	3
abstract_inverted_index.Full	0
abstract_inverted_index.proofs	4
abstract_inverted_index.verions,	1
abstract_inverted_index.including	2
cited_by_percentile_year.max	100
cited_by_percentile_year.min	94
countries_distinct_count	2
institutions_distinct_count	3
sustainable_development_goals[0].id	https://metadata.un.org/sdg/16
sustainable_development_goals[0].score	0.5299999713897705
sustainable_development_goals[0].display_name	Peace, Justice and strong institutions
citation_normalized_percentile.value	0.95367143
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True