A population protocol for exact majority with $O(\\log^{5/3} n)$ stabilization time and asymptotically optimal number of states. Article Swipe
Petra Berenbrink
,
Robert Elsässer⋆
,
Tom Friedetzky
,
Dominik Kaaser
,
Peter Kling
,
Tomasz Radzik
·
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.disc.2018.10
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.disc.2018.10
A population protocol is a sequence of pairwise interactions of n agents. During one interaction, two randomly selected agents update their states by applying a deterministic transition function. The goal is to stabilize the system at a desired output property. The main performance objectives in designing such protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem, which uses Theta(log n) states (per agent) and stabilizes in O(log^{5/3} n) parallel time (i.e., in O(n log^{5/3} n) interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that exact-majority protocols which stabilize in expected O(n^{1-Omega(1)}) parallel time and have the properties of monotonicity and output dominance require Omega(log n) states. Note that the properties mentioned above are satisfied by all known population protocols for exact majority, including ours. They also showed an O(log^2 n)-time exact-majority protocol with O(log n) states, which, prior to our work, was the fastest exact-majority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on O(log n) phases and requires that all agents are well synchronized within each phase, leading naturally to upper bounds of the order of log^2 n because of Theta(log n) synchronization time per phase. We show how this framework can be tightened with weak synchronization to break the O(log^2 n) upper bound of previous protocols.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.10
- OA Status
- green
- Cited By
- 25
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2899320093
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2899320093Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.disc.2018.10Digital Object Identifier
- Title
-
A population protocol for exact majority with $O(\\log^{5/3} n)$ stabilization time and asymptotically optimal number of states.Work title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2018Year of publication
- Publication date
-
2018-10-15Full 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://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.10Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.10Direct OA link when available
- Concepts
-
Upper and lower bounds, Population, Binary logarithm, Combinatorics, Omega, Mathematics, Monotonic function, Log-log plot, Discrete mathematics, Physics, Mathematical analysis, Sociology, Demography, Quantum mechanicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
25Total citation count in OpenAlex
- Citations by year (recent)
-
2024: 1, 2023: 1, 2022: 2, 2021: 9, 2020: 9Per-year citation counts (last 5 years)
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2899320093 |
|---|---|
| doi | https://doi.org/10.4230/lipics.disc.2018.10 |
| ids.mag | 2899320093 |
| ids.openalex | https://openalex.org/W2899320093 |
| fwci | |
| type | article |
| title | A population protocol for exact majority with $O(\\log^{5/3} n)$ stabilization time and asymptotically optimal number of states. |
| 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.9955999851226807 |
| 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/T10927 |
| topics[1].field.id | https://openalex.org/fields/33 |
| topics[1].field.display_name | Social Sciences |
| topics[1].score | 0.9524000287055969 |
| topics[1].domain.id | https://openalex.org/domains/2 |
| topics[1].domain.display_name | Social Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/3312 |
| topics[1].subfield.display_name | Sociology and Political Science |
| topics[1].display_name | Access Control and Trust |
| topics[2].id | https://openalex.org/T12203 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9078999757766724 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Mobile Agent-Based Network Management |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C77553402 |
| concepts[0].level | 2 |
| concepts[0].score | 0.654589056968689 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[0].display_name | Upper and lower bounds |
| concepts[1].id | https://openalex.org/C2908647359 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6214478015899658 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q2625603 |
| concepts[1].display_name | Population |
| concepts[2].id | https://openalex.org/C63553672 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6105636954307556 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q581168 |
| concepts[2].display_name | Binary logarithm |
| concepts[3].id | https://openalex.org/C114614502 |
| concepts[3].level | 1 |
| concepts[3].score | 0.5692994594573975 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[3].display_name | Combinatorics |
| concepts[4].id | https://openalex.org/C2779557605 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5687503218650818 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q9890 |
| concepts[4].display_name | Omega |
| concepts[5].id | https://openalex.org/C33923547 |
| concepts[5].level | 0 |
| concepts[5].score | 0.476629376411438 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[5].display_name | Mathematics |
| concepts[6].id | https://openalex.org/C72169020 |
| concepts[6].level | 2 |
| concepts[6].score | 0.44962745904922485 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q194404 |
| concepts[6].display_name | Monotonic function |
| concepts[7].id | https://openalex.org/C195292467 |
| concepts[7].level | 3 |
| concepts[7].score | 0.41843488812446594 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2091879 |
| concepts[7].display_name | Log-log plot |
| concepts[8].id | https://openalex.org/C118615104 |
| concepts[8].level | 1 |
| concepts[8].score | 0.37180575728416443 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[8].display_name | Discrete mathematics |
| concepts[9].id | https://openalex.org/C121332964 |
| concepts[9].level | 0 |
| concepts[9].score | 0.1668717861175537 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[9].display_name | Physics |
| concepts[10].id | https://openalex.org/C134306372 |
| concepts[10].level | 1 |
| concepts[10].score | 0.07495057582855225 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[10].display_name | Mathematical analysis |
| concepts[11].id | https://openalex.org/C144024400 |
| concepts[11].level | 0 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q21201 |
| concepts[11].display_name | Sociology |
| concepts[12].id | https://openalex.org/C149923435 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q37732 |
| concepts[12].display_name | Demography |
| concepts[13].id | https://openalex.org/C62520636 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[13].display_name | Quantum mechanics |
| keywords[0].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[0].score | 0.654589056968689 |
| keywords[0].display_name | Upper and lower bounds |
| keywords[1].id | https://openalex.org/keywords/population |
| keywords[1].score | 0.6214478015899658 |
| keywords[1].display_name | Population |
| keywords[2].id | https://openalex.org/keywords/binary-logarithm |
| keywords[2].score | 0.6105636954307556 |
| keywords[2].display_name | Binary logarithm |
| keywords[3].id | https://openalex.org/keywords/combinatorics |
| keywords[3].score | 0.5692994594573975 |
| keywords[3].display_name | Combinatorics |
| keywords[4].id | https://openalex.org/keywords/omega |
| keywords[4].score | 0.5687503218650818 |
| keywords[4].display_name | Omega |
| keywords[5].id | https://openalex.org/keywords/mathematics |
| keywords[5].score | 0.476629376411438 |
| keywords[5].display_name | Mathematics |
| keywords[6].id | https://openalex.org/keywords/monotonic-function |
| keywords[6].score | 0.44962745904922485 |
| keywords[6].display_name | Monotonic function |
| keywords[7].id | https://openalex.org/keywords/log-log-plot |
| keywords[7].score | 0.41843488812446594 |
| keywords[7].display_name | Log-log plot |
| keywords[8].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[8].score | 0.37180575728416443 |
| keywords[8].display_name | Discrete mathematics |
| keywords[9].id | https://openalex.org/keywords/physics |
| keywords[9].score | 0.1668717861175537 |
| keywords[9].display_name | Physics |
| keywords[10].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[10].score | 0.07495057582855225 |
| keywords[10].display_name | Mathematical analysis |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:9799 |
| 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/LIPIcs.DISC.2018.10 |
| locations[1].id | pmh:oai:durham-repository.worktribe.com:1144536 |
| locations[1].is_oa | True |
| locations[1].source | |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | publishedVersion |
| locations[1].raw_type | publishedVersion |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | True |
| locations[1].is_published | True |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.4230/lipics.disc.2018.10 |
| locations[2].id | pmh:oai:dro.dur.ac.uk.OAI2:27006 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400188 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | False |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | Durham Research Online (Durham University) |
| locations[2].source.host_organization | https://openalex.org/I190082696 |
| locations[2].source.host_organization_name | Durham University |
| locations[2].source.host_organization_lineage | https://openalex.org/I190082696 |
| locations[2].license | cc-by |
| locations[2].pdf_url | |
| locations[2].version | acceptedVersion |
| locations[2].raw_type | Book chapter |
| locations[2].license_id | https://openalex.org/licenses/cc-by |
| locations[2].is_accepted | True |
| locations[2].is_published | False |
| locations[2].raw_source_name | Schmid, Ulrich & Widder, Josef (Eds.). (2018). 32nd International Symposium on Distributed Computing (DISC 2018). Dagstuhl, Germany: LIPICS, pp. 10:1-10:18, Leibniz International Proceedings in Informatics (LIPIcs)(121) |
| locations[2].landing_page_url | http://dro.dur.ac.uk/27006/ |
| 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 | Universität Hamburg |
| 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 | Universität Hamburg |
| authorships[1].author.id | https://openalex.org/A5061445188 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Robert Elsässer⋆ |
| authorships[1].countries | AT |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I182212641 |
| authorships[1].affiliations[0].raw_affiliation_string | University of Salzburg; |
| authorships[1].institutions[0].id | https://openalex.org/I182212641 |
| authorships[1].institutions[0].ror | https://ror.org/05gs8cd61 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I182212641 |
| authorships[1].institutions[0].country_code | AT |
| authorships[1].institutions[0].display_name | University of Salzburg |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Robert Elsässer |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | University of Salzburg; |
| 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].countries | GB |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I190082696 |
| authorships[2].affiliations[0].raw_affiliation_string | University of Durham. |
| authorships[2].institutions[0].id | https://openalex.org/I190082696 |
| authorships[2].institutions[0].ror | https://ror.org/01v29qb04 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I190082696 |
| authorships[2].institutions[0].country_code | GB |
| authorships[2].institutions[0].display_name | Durham University |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Tom Friedetzky |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | University of Durham. |
| 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].countries | DE |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[3].affiliations[0].raw_affiliation_string | Universität Hamburg |
| authorships[3].institutions[0].id | https://openalex.org/I159176309 |
| authorships[3].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[3].institutions[0].country_code | DE |
| authorships[3].institutions[0].display_name | Universität Hamburg |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Dominik Kaaser |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | Universität Hamburg |
| 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].countries | DE |
| authorships[4].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[4].affiliations[0].raw_affiliation_string | Universität Hamburg |
| authorships[4].institutions[0].id | https://openalex.org/I159176309 |
| authorships[4].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[4].institutions[0].type | education |
| authorships[4].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[4].institutions[0].country_code | DE |
| authorships[4].institutions[0].display_name | Universität Hamburg |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Peter Kling |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | Universität Hamburg |
| 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].affiliations[0].raw_affiliation_string | Informatics |
| authorships[5].author_position | last |
| authorships[5].raw_author_name | Tomasz Radzik |
| authorships[5].is_corresponding | False |
| authorships[5].raw_affiliation_strings | Informatics |
| 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/LIPIcs.DISC.2018.10 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | A population protocol for exact majority with $O(\\log^{5/3} n)$ stabilization time and asymptotically optimal number of states. |
| has_fulltext | True |
| 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.9955999851226807 |
| 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/W2026030032, https://openalex.org/W2006072889, https://openalex.org/W2738922137, https://openalex.org/W2963943319, https://openalex.org/W2059505795, https://openalex.org/W2802138512, https://openalex.org/W3106250499, https://openalex.org/W2743261842, https://openalex.org/W2907311168, https://openalex.org/W2889078364, https://openalex.org/W2043683320, https://openalex.org/W2963844133, https://openalex.org/W2275408670, https://openalex.org/W2123429492, https://openalex.org/W2240696201, https://openalex.org/W2109043215, https://openalex.org/W2802891016, https://openalex.org/W2399651233, https://openalex.org/W2091275311 |
| cited_by_count | 25 |
| counts_by_year[0].year | 2024 |
| counts_by_year[0].cited_by_count | 1 |
| counts_by_year[1].year | 2023 |
| 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 | 9 |
| counts_by_year[4].year | 2020 |
| counts_by_year[4].cited_by_count | 9 |
| counts_by_year[5].year | 2019 |
| counts_by_year[5].cited_by_count | 2 |
| 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:9799 |
| 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/LIPIcs.DISC.2018.10 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:9799 |
| 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/LIPIcs.DISC.2018.10 |
| publication_date | 2018-10-15 |
| publication_year | 2018 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 0 |
| abstract_inverted_index.a | 4, 24, 36, 61 |
| abstract_inverted_index.n | 10, 203 |
| abstract_inverted_index.We | 59, 212 |
| abstract_inverted_index.an | 145 |
| abstract_inverted_index.at | 35 |
| abstract_inverted_index.be | 218 |
| abstract_inverted_index.by | 22, 132 |
| abstract_inverted_index.et | 96 |
| abstract_inverted_index.in | 44, 78, 84, 89, 106 |
| abstract_inverted_index.is | 3, 30, 176 |
| abstract_inverted_index.n) | 72, 80, 87, 122, 152, 180, 207, 227 |
| abstract_inverted_index.of | 6, 9, 51, 115, 167, 198, 201, 205, 230 |
| abstract_inverted_index.on | 178 |
| abstract_inverted_index.to | 31, 156, 195, 223 |
| abstract_inverted_index.O(n | 85 |
| abstract_inverted_index.The | 28, 40, 169 |
| abstract_inverted_index.al. | 97 |
| abstract_inverted_index.all | 133, 185 |
| abstract_inverted_index.and | 55, 76, 91, 111, 117, 182 |
| abstract_inverted_index.are | 48, 130, 187 |
| abstract_inverted_index.can | 217 |
| abstract_inverted_index.for | 65, 137, 173 |
| abstract_inverted_index.how | 214 |
| abstract_inverted_index.one | 13 |
| abstract_inverted_index.our | 157 |
| abstract_inverted_index.per | 53, 210 |
| abstract_inverted_index.the | 33, 66, 113, 126, 160, 199, 225 |
| abstract_inverted_index.two | 15 |
| abstract_inverted_index.was | 159 |
| abstract_inverted_index.(per | 74 |
| abstract_inverted_index.Note | 124 |
| abstract_inverted_index.They | 142 |
| abstract_inverted_index.also | 143 |
| abstract_inverted_index.each | 191 |
| abstract_inverted_index.fast | 56, 62 |
| abstract_inverted_index.goal | 29 |
| abstract_inverted_index.have | 112 |
| abstract_inverted_index.high | 93 |
| abstract_inverted_index.main | 41 |
| abstract_inverted_index.show | 213 |
| abstract_inverted_index.such | 46 |
| abstract_inverted_index.that | 101, 125, 184 |
| abstract_inverted_index.this | 215 |
| abstract_inverted_index.time | 82, 110, 209 |
| abstract_inverted_index.uses | 70 |
| abstract_inverted_index.weak | 221 |
| abstract_inverted_index.well | 188 |
| abstract_inverted_index.with | 92, 150, 164, 220 |
| abstract_inverted_index.2018] | 99 |
| abstract_inverted_index.O(log | 151, 179 |
| abstract_inverted_index.[SODA | 98 |
| abstract_inverted_index.above | 129 |
| abstract_inverted_index.agent | 54 |
| abstract_inverted_index.based | 177 |
| abstract_inverted_index.bound | 229 |
| abstract_inverted_index.break | 224 |
| abstract_inverted_index.exact | 138 |
| abstract_inverted_index.known | 134 |
| abstract_inverted_index.log^2 | 202 |
| abstract_inverted_index.order | 200 |
| abstract_inverted_index.ours. | 141 |
| abstract_inverted_index.prior | 155 |
| abstract_inverted_index.small | 49 |
| abstract_inverted_index.their | 20 |
| abstract_inverted_index.time. | 58 |
| abstract_inverted_index.upper | 196, 228 |
| abstract_inverted_index.which | 69, 104 |
| abstract_inverted_index.work, | 158 |
| abstract_inverted_index.(i.e., | 83 |
| abstract_inverted_index.During | 12 |
| abstract_inverted_index.agent) | 75 |
| abstract_inverted_index.agents | 18, 186 |
| abstract_inverted_index.bounds | 197 |
| abstract_inverted_index.design | 171 |
| abstract_inverted_index.number | 50, 166 |
| abstract_inverted_index.output | 38, 118 |
| abstract_inverted_index.phase, | 192 |
| abstract_inverted_index.phase. | 211 |
| abstract_inverted_index.phases | 181 |
| abstract_inverted_index.showed | 100, 144 |
| abstract_inverted_index.states | 21, 52, 73 |
| abstract_inverted_index.system | 34 |
| abstract_inverted_index.update | 19 |
| abstract_inverted_index.which, | 154 |
| abstract_inverted_index.within | 190 |
| abstract_inverted_index.O(log^2 | 146, 226 |
| abstract_inverted_index.agents. | 11 |
| abstract_inverted_index.because | 204 |
| abstract_inverted_index.desired | 37 |
| abstract_inverted_index.fastest | 161 |
| abstract_inverted_index.leading | 193 |
| abstract_inverted_index.n)-time | 147 |
| abstract_inverted_index.present | 60 |
| abstract_inverted_index.require | 120 |
| abstract_inverted_index.states, | 153 |
| abstract_inverted_index.states. | 123, 168 |
| abstract_inverted_index.Alistarh | 95 |
| abstract_inverted_index.applying | 23 |
| abstract_inverted_index.expected | 107 |
| abstract_inverted_index.majority | 174 |
| abstract_inverted_index.pairwise | 7 |
| abstract_inverted_index.parallel | 81, 109 |
| abstract_inverted_index.previous | 231 |
| abstract_inverted_index.problem, | 68 |
| abstract_inverted_index.protocol | 2, 64, 149, 163 |
| abstract_inverted_index.randomly | 16 |
| abstract_inverted_index.requires | 183 |
| abstract_inverted_index.selected | 17 |
| abstract_inverted_index.sequence | 5 |
| abstract_inverted_index.standard | 170 |
| abstract_inverted_index.Omega(log | 121 |
| abstract_inverted_index.Theta(log | 71, 206 |
| abstract_inverted_index.designing | 45 |
| abstract_inverted_index.dominance | 119 |
| abstract_inverted_index.framework | 172, 216 |
| abstract_inverted_index.function. | 27 |
| abstract_inverted_index.including | 140 |
| abstract_inverted_index.log^{5/3} | 86 |
| abstract_inverted_index.majority, | 139 |
| abstract_inverted_index.mentioned | 128 |
| abstract_inverted_index.naturally | 194 |
| abstract_inverted_index.property. | 39 |
| abstract_inverted_index.protocols | 47, 103, 136, 175 |
| abstract_inverted_index.satisfied | 131 |
| abstract_inverted_index.stabilize | 32, 105 |
| abstract_inverted_index.tightened | 219 |
| abstract_inverted_index.objectives | 43 |
| abstract_inverted_index.population | 1, 63, 135 |
| abstract_inverted_index.properties | 114, 127 |
| abstract_inverted_index.protocols. | 232 |
| abstract_inverted_index.stabilizes | 77 |
| abstract_inverted_index.transition | 26 |
| abstract_inverted_index.O(log^{5/3} | 79 |
| abstract_inverted_index.expectation | 90 |
| abstract_inverted_index.performance | 42 |
| abstract_inverted_index.interaction, | 14 |
| abstract_inverted_index.interactions | 8 |
| abstract_inverted_index.monotonicity | 116 |
| abstract_inverted_index.probability. | 94 |
| abstract_inverted_index.synchronized | 189 |
| abstract_inverted_index.deterministic | 25 |
| abstract_inverted_index.interactions) | 88 |
| abstract_inverted_index.stabilization | 57 |
| abstract_inverted_index.exact-majority | 67, 102, 148, 162 |
| abstract_inverted_index.polylogarithmic | 165 |
| abstract_inverted_index.synchronization | 208, 222 |
| abstract_inverted_index.O(n^{1-Omega(1)}) | 108 |
| cited_by_percentile_year | |
| countries_distinct_count | 3 |
| institutions_distinct_count | 6 |
| citation_normalized_percentile |