Majority & Stabilization in Population Protocols. Article Swipe
Petra Berenbrink
,
Robert Elsässer⋆
,
Tom Friedetzky
,
Dominik Kaaser
,
Peter Kling
,
Tomasz Radzik
·
YOU?
·
· 2018
· Open Access
·
YOU?
·
· 2018
· Open Access
·
Population protocols are a distributed model focused on simplicity and robustness. A system of $n$ identical nodes must perform a global task like electing a unique leader or determining the majority opinion when each node has one of two opinions. Nodes communicate in pairwise interactions. Communication partners cannot be chosen but are assigned randomly. Quality is measured in two ways: the number of interactions and the number of states per node. Under strong requirements, when the protocol may not fail with even negligible probability, the best protocol for leader election requires $O(n \cdot {(\log n)}^2)$ interactions and $O(\log\log n)$ states [Gasieniec and Stachowiak; SODA'18]. The best protocol for majority requires $O(n \cdot {(\log n)}^2)$ interactions and $O(\log n)$ states [Alistarh, Aspnes, and Gelashvili; SODA'18]. Both bounds are known to be space-optimal for protocols with subquadratic many interactions. We present protocols which allow for a trade-off between space and time. Compared to another trade-off result [Alistarh, Gelashvili, Vojnovic; PODC'15], we improve the number of interactions by almost a linear factor. Compared to the state of the art, we match their bounds and, at a moderate cost in terms of states, improve upon the number of interactions. Our results extend to a slightly weaker stability notion known as convergence.
Related Topics
Concepts
Binary logarithm
Protocol (science)
Pairwise comparison
Robustness (evolution)
Population
Upper and lower bounds
Node (physics)
Computer science
Log-log plot
Combinatorics
Mathematics
Discrete mathematics
Biology
Physics
Artificial intelligence
Medicine
Biochemistry
Gene
Sociology
Pathology
Demography
Quantum mechanics
Mathematical analysis
Alternative medicine
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://dblp.uni-trier.de/db/journals/corr/corr1805.html#abs-1805-04586
- OA Status
- green
- Cited By
- 5
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2799373097
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2799373097Canonical identifier for this work in OpenAlex
- Title
-
Majority & Stabilization in Population Protocols.Work title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2018Year of publication
- Publication date
-
2018-05-11Full publication date if available
- Authors
-
Petra Berenbrink, Robert Elsässer⋆, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz RadzikList of authors in order
- Landing page
-
https://dblp.uni-trier.de/db/journals/corr/corr1805.html#abs-1805-04586Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://dblp.uni-trier.de/db/journals/corr/corr1805.html#abs-1805-04586Direct OA link when available
- Concepts
-
Binary logarithm, Protocol (science), Pairwise comparison, Robustness (evolution), Population, Upper and lower bounds, Node (physics), Computer science, Log-log plot, Combinatorics, Mathematics, Discrete mathematics, Biology, Physics, Artificial intelligence, Medicine, Biochemistry, Gene, Sociology, Pathology, Demography, Quantum mechanics, Mathematical analysis, Alternative medicineTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
5Total citation count in OpenAlex
- Citations by year (recent)
-
2021: 1, 2020: 3, 2018: 1Per-year citation counts (last 5 years)
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2799373097 |
|---|---|
| doi | |
| ids.mag | 2799373097 |
| ids.openalex | https://openalex.org/W2799373097 |
| fwci | |
| type | preprint |
| title | Majority & Stabilization in Population Protocols. |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| 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.9973999857902527 |
| 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/T10764 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9822999835014343 |
| 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 | Privacy-Preserving Technologies in Data |
| 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.9517999887466431 |
| 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/C63553672 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6742170453071594 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q581168 |
| concepts[0].display_name | Binary logarithm |
| concepts[1].id | https://openalex.org/C2780385302 |
| concepts[1].level | 3 |
| concepts[1].score | 0.5896623730659485 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q367158 |
| concepts[1].display_name | Protocol (science) |
| concepts[2].id | https://openalex.org/C184898388 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5722251534461975 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1435712 |
| concepts[2].display_name | Pairwise comparison |
| concepts[3].id | https://openalex.org/C63479239 |
| concepts[3].level | 3 |
| concepts[3].score | 0.5489403605461121 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q7353546 |
| concepts[3].display_name | Robustness (evolution) |
| concepts[4].id | https://openalex.org/C2908647359 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5312547087669373 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2625603 |
| concepts[4].display_name | Population |
| concepts[5].id | https://openalex.org/C77553402 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5189290046691895 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[5].display_name | Upper and lower bounds |
| concepts[6].id | https://openalex.org/C62611344 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5004937648773193 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q1062658 |
| concepts[6].display_name | Node (physics) |
| concepts[7].id | https://openalex.org/C41008148 |
| concepts[7].level | 0 |
| concepts[7].score | 0.492336630821228 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[7].display_name | Computer science |
| concepts[8].id | https://openalex.org/C195292467 |
| concepts[8].level | 3 |
| concepts[8].score | 0.460333913564682 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q2091879 |
| concepts[8].display_name | Log-log plot |
| concepts[9].id | https://openalex.org/C114614502 |
| concepts[9].level | 1 |
| concepts[9].score | 0.42968854308128357 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[9].display_name | Combinatorics |
| concepts[10].id | https://openalex.org/C33923547 |
| concepts[10].level | 0 |
| concepts[10].score | 0.351939857006073 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[10].display_name | Mathematics |
| concepts[11].id | https://openalex.org/C118615104 |
| concepts[11].level | 1 |
| concepts[11].score | 0.33186495304107666 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[11].display_name | Discrete mathematics |
| concepts[12].id | https://openalex.org/C86803240 |
| concepts[12].level | 0 |
| concepts[12].score | 0.09112763404846191 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q420 |
| concepts[12].display_name | Biology |
| concepts[13].id | https://openalex.org/C121332964 |
| concepts[13].level | 0 |
| concepts[13].score | 0.09043508768081665 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[13].display_name | Physics |
| concepts[14].id | https://openalex.org/C154945302 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0707065761089325 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[14].display_name | Artificial intelligence |
| concepts[15].id | https://openalex.org/C71924100 |
| concepts[15].level | 0 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q11190 |
| concepts[15].display_name | Medicine |
| concepts[16].id | https://openalex.org/C55493867 |
| concepts[16].level | 1 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q7094 |
| concepts[16].display_name | Biochemistry |
| concepts[17].id | https://openalex.org/C104317684 |
| concepts[17].level | 2 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q7187 |
| concepts[17].display_name | Gene |
| concepts[18].id | https://openalex.org/C144024400 |
| concepts[18].level | 0 |
| concepts[18].score | 0.0 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q21201 |
| concepts[18].display_name | Sociology |
| concepts[19].id | https://openalex.org/C142724271 |
| concepts[19].level | 1 |
| concepts[19].score | 0.0 |
| concepts[19].wikidata | https://www.wikidata.org/wiki/Q7208 |
| concepts[19].display_name | Pathology |
| concepts[20].id | https://openalex.org/C149923435 |
| concepts[20].level | 1 |
| concepts[20].score | 0.0 |
| concepts[20].wikidata | https://www.wikidata.org/wiki/Q37732 |
| concepts[20].display_name | Demography |
| concepts[21].id | https://openalex.org/C62520636 |
| concepts[21].level | 1 |
| concepts[21].score | 0.0 |
| concepts[21].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[21].display_name | Quantum mechanics |
| concepts[22].id | https://openalex.org/C134306372 |
| concepts[22].level | 1 |
| concepts[22].score | 0.0 |
| concepts[22].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[22].display_name | Mathematical analysis |
| concepts[23].id | https://openalex.org/C204787440 |
| concepts[23].level | 2 |
| concepts[23].score | 0.0 |
| concepts[23].wikidata | https://www.wikidata.org/wiki/Q188504 |
| concepts[23].display_name | Alternative medicine |
| keywords[0].id | https://openalex.org/keywords/binary-logarithm |
| keywords[0].score | 0.6742170453071594 |
| keywords[0].display_name | Binary logarithm |
| keywords[1].id | https://openalex.org/keywords/protocol |
| keywords[1].score | 0.5896623730659485 |
| keywords[1].display_name | Protocol (science) |
| keywords[2].id | https://openalex.org/keywords/pairwise-comparison |
| keywords[2].score | 0.5722251534461975 |
| keywords[2].display_name | Pairwise comparison |
| keywords[3].id | https://openalex.org/keywords/robustness |
| keywords[3].score | 0.5489403605461121 |
| keywords[3].display_name | Robustness (evolution) |
| keywords[4].id | https://openalex.org/keywords/population |
| keywords[4].score | 0.5312547087669373 |
| keywords[4].display_name | Population |
| keywords[5].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[5].score | 0.5189290046691895 |
| keywords[5].display_name | Upper and lower bounds |
| keywords[6].id | https://openalex.org/keywords/node |
| keywords[6].score | 0.5004937648773193 |
| keywords[6].display_name | Node (physics) |
| keywords[7].id | https://openalex.org/keywords/computer-science |
| keywords[7].score | 0.492336630821228 |
| keywords[7].display_name | Computer science |
| keywords[8].id | https://openalex.org/keywords/log-log-plot |
| keywords[8].score | 0.460333913564682 |
| keywords[8].display_name | Log-log plot |
| keywords[9].id | https://openalex.org/keywords/combinatorics |
| keywords[9].score | 0.42968854308128357 |
| keywords[9].display_name | Combinatorics |
| keywords[10].id | https://openalex.org/keywords/mathematics |
| keywords[10].score | 0.351939857006073 |
| keywords[10].display_name | Mathematics |
| keywords[11].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[11].score | 0.33186495304107666 |
| keywords[11].display_name | Discrete mathematics |
| keywords[12].id | https://openalex.org/keywords/biology |
| keywords[12].score | 0.09112763404846191 |
| keywords[12].display_name | Biology |
| keywords[13].id | https://openalex.org/keywords/physics |
| keywords[13].score | 0.09043508768081665 |
| keywords[13].display_name | Physics |
| keywords[14].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[14].score | 0.0707065761089325 |
| keywords[14].display_name | Artificial intelligence |
| language | en |
| locations[0].id | mag:2799373097 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | arXiv (Cornell University) |
| locations[0].landing_page_url | https://dblp.uni-trier.de/db/journals/corr/corr1805.html#abs-1805-04586 |
| 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/A5061445188 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Robert Elsässer⋆ |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Robert Elsässer |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5011308108 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-1299-5514 |
| authorships[2].author.display_name | Tom Friedetzky |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Tom Friedetzky |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5085356058 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-2083-7145 |
| authorships[3].author.display_name | Dominik Kaaser |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Dominik Kaaser |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5007675663 |
| authorships[4].author.orcid | https://orcid.org/0000-0003-0000-8689 |
| authorships[4].author.display_name | Peter Kling |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Peter Kling |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5070579616 |
| authorships[5].author.orcid | https://orcid.org/0000-0002-7776-5461 |
| authorships[5].author.display_name | Tomasz Radzik |
| authorships[5].author_position | last |
| authorships[5].raw_author_name | Tomasz Radzik |
| authorships[5].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://dblp.uni-trier.de/db/journals/corr/corr1805.html#abs-1805-04586 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Majority & Stabilization in Population Protocols. |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-10-10T17:16:08.811792 |
| 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.9973999857902527 |
| 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/W2952048613, https://openalex.org/W2476148693, https://openalex.org/W3016416987, https://openalex.org/W2962724086, https://openalex.org/W3165876575, https://openalex.org/W3209321351, https://openalex.org/W2092163107, https://openalex.org/W3160918026, https://openalex.org/W2962422787, https://openalex.org/W2901106279, https://openalex.org/W2950049138, https://openalex.org/W2089101914, https://openalex.org/W1557189197, https://openalex.org/W3133334000, https://openalex.org/W2763147606, https://openalex.org/W2811510304, https://openalex.org/W1529640672, https://openalex.org/W2615415387, https://openalex.org/W1943680860, https://openalex.org/W2483628663 |
| cited_by_count | 5 |
| counts_by_year[0].year | 2021 |
| counts_by_year[0].cited_by_count | 1 |
| counts_by_year[1].year | 2020 |
| counts_by_year[1].cited_by_count | 3 |
| counts_by_year[2].year | 2018 |
| counts_by_year[2].cited_by_count | 1 |
| locations_count | 1 |
| best_oa_location.id | mag:2799373097 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| 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 | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | arXiv (Cornell University) |
| best_oa_location.landing_page_url | https://dblp.uni-trier.de/db/journals/corr/corr1805.html#abs-1805-04586 |
| primary_location.id | mag:2799373097 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | arXiv (Cornell University) |
| primary_location.landing_page_url | https://dblp.uni-trier.de/db/journals/corr/corr1805.html#abs-1805-04586 |
| publication_date | 2018-05-11 |
| publication_year | 2018 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 11 |
| abstract_inverted_index.a | 3, 19, 24, 144, 167, 183, 200 |
| abstract_inverted_index.as | 206 |
| abstract_inverted_index.at | 182 |
| abstract_inverted_index.be | 48, 130 |
| abstract_inverted_index.by | 165 |
| abstract_inverted_index.in | 42, 57, 186 |
| abstract_inverted_index.is | 55 |
| abstract_inverted_index.of | 13, 37, 62, 67, 163, 174, 188, 194 |
| abstract_inverted_index.on | 7 |
| abstract_inverted_index.or | 27 |
| abstract_inverted_index.to | 129, 151, 171, 199 |
| abstract_inverted_index.we | 159, 177 |
| abstract_inverted_index.$n$ | 14 |
| abstract_inverted_index.Our | 196 |
| abstract_inverted_index.The | 105 |
| abstract_inverted_index.and | 9, 64, 97, 102, 116, 122, 148 |
| abstract_inverted_index.are | 2, 51, 127 |
| abstract_inverted_index.but | 50 |
| abstract_inverted_index.for | 88, 108, 132, 143 |
| abstract_inverted_index.has | 35 |
| abstract_inverted_index.may | 78 |
| abstract_inverted_index.n)$ | 99, 118 |
| abstract_inverted_index.not | 79 |
| abstract_inverted_index.one | 36 |
| abstract_inverted_index.per | 69 |
| abstract_inverted_index.the | 29, 60, 65, 76, 85, 161, 172, 175, 192 |
| abstract_inverted_index.two | 38, 58 |
| abstract_inverted_index. We | 138 |
| abstract_inverted_index.$O(n | 92, 111 |
| abstract_inverted_index.Both | 125 |
| abstract_inverted_index.and, | 181 |
| abstract_inverted_index.art, | 176 |
| abstract_inverted_index.best | 86, 106 |
| abstract_inverted_index.cost | 185 |
| abstract_inverted_index.each | 33 |
| abstract_inverted_index.even | 82 |
| abstract_inverted_index.fail | 80 |
| abstract_inverted_index.like | 22 |
| abstract_inverted_index.many | 136 |
| abstract_inverted_index.must | 17 |
| abstract_inverted_index.node | 34 |
| abstract_inverted_index.task | 21 |
| abstract_inverted_index.upon | 191 |
| abstract_inverted_index.when | 32, 75 |
| abstract_inverted_index.with | 81, 134 |
| abstract_inverted_index.Nodes | 40 |
| abstract_inverted_index.\cdot | 93, 112 |
| abstract_inverted_index.allow | 142 |
| abstract_inverted_index.known | 128, 205 |
| abstract_inverted_index.match | 178 |
| abstract_inverted_index.model | 5 |
| abstract_inverted_index.node. | 70 |
| abstract_inverted_index.nodes | 16 |
| abstract_inverted_index.space | 147 |
| abstract_inverted_index.state | 173 |
| abstract_inverted_index.terms | 187 |
| abstract_inverted_index.their | 179 |
| abstract_inverted_index.time. | 149 |
| abstract_inverted_index.ways: | 59 |
| abstract_inverted_index.which | 141 |
| abstract_inverted_index.almost | 166 |
| abstract_inverted_index.bounds | 126, 180 |
| abstract_inverted_index.cannot | 47 |
| abstract_inverted_index.chosen | 49 |
| abstract_inverted_index.extend | 198 |
| abstract_inverted_index.global | 20 |
| abstract_inverted_index.leader | 26, 89 |
| abstract_inverted_index.linear | 168 |
| abstract_inverted_index.notion | 204 |
| abstract_inverted_index.number | 61, 66, 162, 193 |
| abstract_inverted_index.result | 154 |
| abstract_inverted_index.states | 68, 100, 119 |
| abstract_inverted_index.strong | 72 |
| abstract_inverted_index.system | 12 |
| abstract_inverted_index.unique | 25 |
| abstract_inverted_index.weaker | 202 |
| abstract_inverted_index.{(\log | 94, 113 |
| abstract_inverted_index. Under | 71 |
| abstract_inverted_index.$O(\log | 117 |
| abstract_inverted_index.Aspnes, | 121 |
| abstract_inverted_index.Quality | 54 |
| abstract_inverted_index.another | 152 |
| abstract_inverted_index.between | 146 |
| abstract_inverted_index.factor. | 169 |
| abstract_inverted_index.focused | 6 |
| abstract_inverted_index.improve | 160, 190 |
| abstract_inverted_index.n)}^2)$ | 95, 114 |
| abstract_inverted_index.opinion | 31 |
| abstract_inverted_index.perform | 18 |
| abstract_inverted_index.present | 139 |
| abstract_inverted_index.results | 197 |
| abstract_inverted_index.states, | 189 |
| abstract_inverted_index.Compared | 150, 170 |
| abstract_inverted_index.assigned | 52 |
| abstract_inverted_index.electing | 23 |
| abstract_inverted_index.election | 90 |
| abstract_inverted_index.majority | 30, 109 |
| abstract_inverted_index.measured | 56 |
| abstract_inverted_index.moderate | 184 |
| abstract_inverted_index.pairwise | 43 |
| abstract_inverted_index.partners | 46 |
| abstract_inverted_index.protocol | 77, 87, 107 |
| abstract_inverted_index.requires | 91, 110 |
| abstract_inverted_index.slightly | 201 |
| abstract_inverted_index.PODC'15], | 158 |
| abstract_inverted_index.SODA'18]. | 104, 124 |
| abstract_inverted_index.Vojnovic; | 157 |
| abstract_inverted_index.identical | 15 |
| abstract_inverted_index.opinions. | 39 |
| abstract_inverted_index.protocols | 1, 133, 140 |
| abstract_inverted_index.randomly. | 53 |
| abstract_inverted_index.stability | 203 |
| abstract_inverted_index.trade-off | 145, 153 |
| abstract_inverted_index.Population | 0 |
| abstract_inverted_index.[Alistarh, | 120, 155 |
| abstract_inverted_index.[Gasieniec | 101 |
| abstract_inverted_index.negligible | 83 |
| abstract_inverted_index.simplicity | 8 |
| abstract_inverted_index.$O(\log\log | 98 |
| abstract_inverted_index.Gelashvili, | 156 |
| abstract_inverted_index.Gelashvili; | 123 |
| abstract_inverted_index.Stachowiak; | 103 |
| abstract_inverted_index.communicate | 41 |
| abstract_inverted_index.determining | 28 |
| abstract_inverted_index.distributed | 4 |
| abstract_inverted_index.robustness. | 10 |
| abstract_inverted_index.convergence. | 207 |
| abstract_inverted_index.interactions | 63, 96, 115, 164 |
| abstract_inverted_index.probability, | 84 |
| abstract_inverted_index.subquadratic | 135 |
| abstract_inverted_index.Communication | 45 |
| abstract_inverted_index.interactions. | 44, 137, 195 |
| abstract_inverted_index.requirements, | 74 |
| abstract_inverted_index.space-optimal | 131 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 6 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/17 |
| sustainable_development_goals[0].score | 0.5299999713897705 |
| sustainable_development_goals[0].display_name | Partnerships for the goals |
| citation_normalized_percentile |