---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '19969'
abstract:
- lang: eng
  text: "In the stochastic population protocol model, we are given a connected graph
    with n nodes, and in every time step, a scheduler samples an edge of the graph
    uniformly at random and the nodes connected by this edge interact. A fundamental
    task in this model is stable leader election, in which all nodes start in an identical
    state and the aim is to reach a configuration in which (1)\r\nexactly one node
    is elected as leader and (2) this node remains as the unique leader no matter
    what sequence of interactions follows. On cliques, the complexity of this problem
    has recently been settled: time-optimal protocols stabilize in (n log n) expected
    steps using (log log n) states, whereas protocols that use O(1) states require
    (n2) expected steps. In this work, we investigate the complexity of stable leader
    election on graphs. We provide the first non-trivial time lower bounds on general
    graphs, showing that, when moving beyond cliques, the complexity of stable leader
    election can range from O(1) to (n3) expected steps. We describe a protocol that
    is time-optimal on many graph families, but uses polynomially-many states. In
    contrast, we give a near-time-optimal protocol that uses only O(log2 n) states
    that is at most a factor O(log n) slower. Finally, we observe that for many graphs
    the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor
    O(n log n) slower than the fast polynomial-state protocol, and among constant-state
    protocols, this protocol has near-optimal average case complexity on dense random
    graphs."
acknowledgement: We thank all anonymous reviewers for their helpful comments. We would
  also like to thank Jakob Solnerzik and Olivier Stietel for catching some errors
  in the proofs. Open Access funding enabled and organized by Projekt DEAL. We gratefully
  acknowledge funding from the European Research Council (ERC) under the European
  Union’s Horizon 2020 research and innovation programme (grant agreement No 805223
  ScaleML).
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
- first_name: Sasha
  full_name: Voitovych, Sasha
  last_name: Voitovych
citation:
  ama: Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population
    protocols on graphs. <i>Distributed Computing</i>. 2025;38:207-245. doi:<a href="https://doi.org/10.1007/s00446-025-00487-7">10.1007/s00446-025-00487-7</a>
  apa: Alistarh, D.-A., Rybicki, J., &#38; Voitovych, S. (2025). Near-optimal leader
    election in population protocols on graphs. <i>Distributed Computing</i>. Springer
    Nature. <a href="https://doi.org/10.1007/s00446-025-00487-7">https://doi.org/10.1007/s00446-025-00487-7</a>
  chicago: Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal
    Leader Election in Population Protocols on Graphs.” <i>Distributed Computing</i>.
    Springer Nature, 2025. <a href="https://doi.org/10.1007/s00446-025-00487-7">https://doi.org/10.1007/s00446-025-00487-7</a>.
  ieee: D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election
    in population protocols on graphs,” <i>Distributed Computing</i>, vol. 38. Springer
    Nature, pp. 207–245, 2025.
  ista: Alistarh D-A, Rybicki J, Voitovych S. 2025. Near-optimal leader election in
    population protocols on graphs. Distributed Computing. 38, 207–245.
  mla: Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols
    on Graphs.” <i>Distributed Computing</i>, vol. 38, Springer Nature, 2025, pp.
    207–45, doi:<a href="https://doi.org/10.1007/s00446-025-00487-7">10.1007/s00446-025-00487-7</a>.
  short: D.-A. Alistarh, J. Rybicki, S. Voitovych, Distributed Computing 38 (2025)
    207–245.
corr_author: '1'
date_created: 2025-07-06T22:01:24Z
date_published: 2025-09-01T00:00:00Z
date_updated: 2025-12-30T09:04:18Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.1007/s00446-025-00487-7
ec_funded: 1
external_id:
  arxiv:
  - '2205.12597'
  isi:
  - '001518300400001'
file:
- access_level: open_access
  checksum: 2789c0fdfb58f64930f05f6ac2b3ca61
  content_type: application/pdf
  creator: dernst
  date_created: 2025-12-30T09:03:55Z
  date_updated: 2025-12-30T09:03:55Z
  file_id: '20900'
  file_name: 2025_DistributedComp_Alistarh.pdf
  file_size: 770705
  relation: main_file
  success: 1
file_date_updated: 2025-12-30T09:03:55Z
has_accepted_license: '1'
intvolume: '        38'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 207-245
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
publication: Distributed Computing
publication_identifier:
  eissn:
  - 1432-0452
  issn:
  - 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11844'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Near-optimal leader election in population protocols on graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 38
year: '2025'
...
---
_id: '12164'
abstract:
- lang: eng
  text: 'A shared-memory counter is a widely-used and well-studied concurrent object.
    It supports two operations: An Inc operation that increases its value by 1 and
    a Read operation that returns its current value. In Jayanti et al (SIAM J Comput,
    30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case
    step complexity of obstruction-free implementations, from read-write registers,
    of a large class of shared objects that includes counters. The lower bound leaves
    open the question of finding counter implementations with sub-linear amortized
    step complexity. In this work, we address this gap. We show that n-process, wait-free
    and linearizable counters can be implemented from read-write registers with O(log2n)
    amortized step complexity. This is the first counter algorithm from read-write
    registers that provides sub-linear amortized step complexity in executions of
    arbitrary length. Since a logarithmic lower bound on the amortized step complexity
    of obstruction-free counter implementations exists, our upper bound is within
    a logarithmic factor of the optimal. The worst-case step complexity of the construction
    remains linear, which is optimal. This is obtained thanks to a new max register
    construction with O(logn) amortized step complexity in executions of arbitrary
    length in which the value stored in the register does not grow too quickly. We
    then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel
    [1] in which we “plug” our max register implementation to show that it remains
    linearizable while achieving O(log2n) amortized step complexity.'
acknowledgement: A preliminary version of this work appeared in DISC’19. Mirza Ahad
  Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes
  and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported
  by the Israel Science Foundation (Grants 380/18 and 1425/22).
article_processing_charge: No
article_type: original
author:
- first_name: Mirza Ahad
  full_name: Baig, Mirza Ahad
  id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
  last_name: Baig
- first_name: Danny
  full_name: Hendler, Danny
  last_name: Hendler
- first_name: Alessia
  full_name: Milani, Alessia
  last_name: Milani
- first_name: Corentin
  full_name: Travers, Corentin
  last_name: Travers
citation:
  ama: Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic
    amortized step complexity. <i>Distributed Computing</i>. 2023;36:29-43. doi:<a
    href="https://doi.org/10.1007/s00446-022-00439-5">10.1007/s00446-022-00439-5</a>
  apa: Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2023). Long-lived
    counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-022-00439-5">https://doi.org/10.1007/s00446-022-00439-5</a>
  chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
    “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed
    Computing</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s00446-022-00439-5">https://doi.org/10.1007/s00446-022-00439-5</a>.
  ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with
    polylogarithmic amortized step complexity,” <i>Distributed Computing</i>, vol.
    36. Springer Nature, pp. 29–43, 2023.
  ista: Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic
    amortized step complexity. Distributed Computing. 36, 29–43.
  mla: Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized
    Step Complexity.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023,
    pp. 29–43, doi:<a href="https://doi.org/10.1007/s00446-022-00439-5">10.1007/s00446-022-00439-5</a>.
  short: M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023)
    29–43.
date_created: 2023-01-12T12:10:08Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-08-16T08:39:36Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00446-022-00439-5
external_id:
  isi:
  - '000890138700001'
intvolume: '        36'
isi: 1
keyword:
- Computational Theory and Mathematics
- Computer Networks and Communications
- Hardware and Architecture
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://drops.dagstuhl.de/opus/volltexte/2019/11310/
month: '03'
oa: 1
oa_version: Preprint
page: 29-43
publication: Distributed Computing
publication_identifier:
  eissn:
  - 1432-0452
  issn:
  - 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long-lived counters with polylogarithmic amortized step complexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '12330'
abstract:
- lang: eng
  text: 'The design and implementation of efficient concurrent data structures has
    seen significant attention. However, most of this work has focused on concurrent
    data structures providing good worst-case guarantees, although, in real workloads,
    objects are often accessed at different rates. Efficient distribution-adaptive
    data structures, such as splay-trees, are known in the sequential case; however,
    they often are hard to translate efficiently to the concurrent case. We investigate
    distribution-adaptive concurrent data structures, and propose a new design called
    the splay-list. At a high level, the splay-list is similar to a standard skip-list,
    with the key distinction that the height of each element adapts dynamically to
    its access rate: popular elements “move up,” whereas rarely-accessed elements
    decrease in height. We show that the splay-list provides order-optimal amortized
    complexity bounds for a subset of operations, while being amenable to efficient
    concurrent implementation. Experiments show that the splay-list can leverage distribution-adaptivity
    for performance, and can outperform the only previously-known distribution-adaptive
    concurrent design in certain workloads.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vitalii
  full_name: Aksenov, Vitalii
  id: 2980135A-F248-11E8-B48F-1D18A9856A87
  last_name: Aksenov
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Alexandra
  full_name: Drozdova, Alexandra
  last_name: Drozdova
- first_name: Amirkeivan
  full_name: Mohtashami, Amirkeivan
  last_name: Mohtashami
citation:
  ama: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive
    concurrent skip-list. <i>Distributed Computing</i>. 2023;36:395-418. doi:<a href="https://doi.org/10.1007/s00446-022-00441-x">10.1007/s00446-022-00441-x</a>'
  apa: 'Aksenov, V., Alistarh, D.-A., Drozdova, A., &#38; Mohtashami, A. (2023). The
    splay-list: A distribution-adaptive concurrent skip-list. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-022-00441-x">https://doi.org/10.1007/s00446-022-00441-x</a>'
  chicago: 'Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan
    Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>Distributed
    Computing</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s00446-022-00441-x">https://doi.org/10.1007/s00446-022-00441-x</a>.'
  ieee: 'V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list:
    A distribution-adaptive concurrent skip-list,” <i>Distributed Computing</i>, vol.
    36. Springer Nature, pp. 395–418, 2023.'
  ista: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2023. The splay-list:
    A distribution-adaptive concurrent skip-list. Distributed Computing. 36, 395–418.'
  mla: 'Aksenov, Vitalii, et al. “The Splay-List: A Distribution-Adaptive Concurrent
    Skip-List.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp.
    395–418, doi:<a href="https://doi.org/10.1007/s00446-022-00441-x">10.1007/s00446-022-00441-x</a>.'
  short: V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, Distributed Computing
    36 (2023) 395–418.
date_created: 2023-01-22T23:00:55Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2023-08-14T12:54:32Z
day: '01'
department:
- _id: DaAl
doi: 10.1007/s00446-022-00441-x
external_id:
  arxiv:
  - '2008.01009'
  isi:
  - '000913424000001'
intvolume: '        36'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2008.01009
month: '09'
oa: 1
oa_version: Preprint
page: 395-418
publication: Distributed Computing
publication_identifier:
  eissn:
  - 1432-0452
  issn:
  - 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The splay-list: A distribution-adaptive concurrent skip-list'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '7939'
abstract:
- lang: eng
  text: "We design fast deterministic algorithms for distance computation in the Congested
    Clique model. Our key contributions include:\r\n    A (2+ϵ)-approximation for
    all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs.
    With a small additional additive factor, this also applies for weighted graphs.
    This is the first sub-polynomial constant-factor approximation for APSP in this
    model.\r\n    A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√)
    sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first
    sub-polynomial algorithm obtaining this approximation for a set of sources of
    polynomial size.\r\n\r\nOur main techniques are new distance tools that are obtained
    via improved algorithms for sparse matrix multiplication, which we leverage to
    construct efficient hopsets and shortest paths. Furthermore, our techniques extend
    to additional distance problems for which we improve upon the state-of-the-art,
    including diameter approximation, and an exact single-source shortest paths algorithm
    for weighted undirected graphs in O~(n1/6) rounds. "
acknowledgement: Open access funding provided by Institute of Science and Technology
  (IST Austria). We thank Mohsen Ghaffari, Michael Elkin and Merav Parter for fruitful
  discussions. This project has received funding from the European Union’s Horizon
  2020 Research And Innovation Program under Grant Agreement No. 755839.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Keren
  full_name: Censor-Hillel, Keren
  last_name: Censor-Hillel
- first_name: Michal
  full_name: Dory, Michal
  last_name: Dory
- first_name: Janne
  full_name: Korhonen, Janne
  id: C5402D42-15BC-11E9-A202-CA2BE6697425
  last_name: Korhonen
- first_name: Dean
  full_name: Leitersdorf, Dean
  last_name: Leitersdorf
citation:
  ama: Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest
    paths in the congested clique. <i>Distributed Computing</i>. 2021;34:463-487.
    doi:<a href="https://doi.org/10.1007/s00446-020-00380-5">10.1007/s00446-020-00380-5</a>
  apa: Censor-Hillel, K., Dory, M., Korhonen, J., &#38; Leitersdorf, D. (2021). Fast
    approximate shortest paths in the congested clique. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-020-00380-5">https://doi.org/10.1007/s00446-020-00380-5</a>
  chicago: Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf.
    “Fast Approximate Shortest Paths in the Congested Clique.” <i>Distributed Computing</i>.
    Springer Nature, 2021. <a href="https://doi.org/10.1007/s00446-020-00380-5">https://doi.org/10.1007/s00446-020-00380-5</a>.
  ieee: K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate
    shortest paths in the congested clique,” <i>Distributed Computing</i>, vol. 34.
    Springer Nature, pp. 463–487, 2021.
  ista: Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate
    shortest paths in the congested clique. Distributed Computing. 34, 463–487.
  mla: Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested
    Clique.” <i>Distributed Computing</i>, vol. 34, Springer Nature, 2021, pp. 463–87,
    doi:<a href="https://doi.org/10.1007/s00446-020-00380-5">10.1007/s00446-020-00380-5</a>.
  short: K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, Distributed Computing
    34 (2021) 463–487.
corr_author: '1'
date_created: 2020-06-07T22:00:54Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2026-06-18T19:28:41Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00446-020-00380-5
external_id:
  arxiv:
  - '1903.05956'
  isi:
  - '000556444600001'
intvolume: '        34'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/s00446-020-00380-5
month: '12'
oa: 1
oa_version: Published Version
page: 463-487
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: Distributed Computing
publication_identifier:
  eissn:
  - 1432-0452
  issn:
  - 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '6933'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Fast approximate shortest paths in the congested clique
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2021'
...
---
_id: '7150'
abstract:
- lang: eng
  text: "In this work, we use algebraic methods for studying distance computation
    and subgraph detection tasks in the congested clique model. Specifically, we adapt
    parallel matrix multiplication implementations to the congested clique, obtaining
    an O(n1−2/ω) round matrix multiplication algorithm, where ω<2.3728639 is the exponent
    of matrix multiplication. In conjunction with known techniques from centralised
    algorithmics, this gives significant improvements over previous best upper bounds
    in the congested clique model. The highlight results include:\r\n\r\n1.    triangle
    and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) algorithm
    of Dolev et al. [DISC 2012],\r\n2. a (1+o(1))-approximation of all-pairs shortest
    paths in O(n0.158) rounds, improving upon the O~(n1/2)-round (2+o(1))-approximation
    algorithm given by Nanongkai [STOC 2014], and\r\n 3. computing the girth in O(n0.158)
    rounds, which is the first non-trivial solution in this model.\r\n   \r\nIn addition,
    we present a novel constant-round combinatorial algorithm for detecting 4-cycles."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Keren
  full_name: Censor-Hillel, Keren
  last_name: Censor-Hillel
- first_name: Petteri
  full_name: Kaski, Petteri
  last_name: Kaski
- first_name: Janne
  full_name: Korhonen, Janne
  id: C5402D42-15BC-11E9-A202-CA2BE6697425
  last_name: Korhonen
- first_name: Christoph
  full_name: Lenzen, Christoph
  last_name: Lenzen
- first_name: Ami
  full_name: Paz, Ami
  last_name: Paz
- first_name: Jukka
  full_name: Suomela, Jukka
  last_name: Suomela
citation:
  ama: Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. Algebraic
    methods in the congested clique. <i>Distributed Computing</i>. 2019;32(6):461-478.
    doi:<a href="https://doi.org/10.1007/s00446-016-0270-2">10.1007/s00446-016-0270-2</a>
  apa: Censor-Hillel, K., Kaski, P., Korhonen, J., Lenzen, C., Paz, A., &#38; Suomela,
    J. (2019). Algebraic methods in the congested clique. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-016-0270-2">https://doi.org/10.1007/s00446-016-0270-2</a>
  chicago: Censor-Hillel, Keren, Petteri Kaski, Janne Korhonen, Christoph Lenzen,
    Ami Paz, and Jukka Suomela. “Algebraic Methods in the Congested Clique.” <i>Distributed
    Computing</i>. Springer Nature, 2019. <a href="https://doi.org/10.1007/s00446-016-0270-2">https://doi.org/10.1007/s00446-016-0270-2</a>.
  ieee: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, and J. Suomela,
    “Algebraic methods in the congested clique,” <i>Distributed Computing</i>, vol.
    32, no. 6. Springer Nature, pp. 461–478, 2019.
  ista: Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. 2019. Algebraic
    methods in the congested clique. Distributed Computing. 32(6), 461–478.
  mla: Censor-Hillel, Keren, et al. “Algebraic Methods in the Congested Clique.” <i>Distributed
    Computing</i>, vol. 32, no. 6, Springer Nature, 2019, pp. 461–78, doi:<a href="https://doi.org/10.1007/s00446-016-0270-2">10.1007/s00446-016-0270-2</a>.
  short: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, J. Suomela, Distributed
    Computing 32 (2019) 461–478.
date_created: 2019-12-05T09:49:49Z
date_published: 2019-12-01T00:00:00Z
date_updated: 2021-01-12T08:12:05Z
day: '01'
doi: 10.1007/s00446-016-0270-2
extern: '1'
external_id:
  arxiv:
  - '1503.04963'
intvolume: '        32'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1503.04963
month: '12'
oa: 1
oa_version: Preprint
page: 461-478
publication: Distributed Computing
publication_identifier:
  issn:
  - 0178-2770
  - 1432-0452
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Algebraic methods in the congested clique
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 32
year: '2019'
...
---
_id: '536'
abstract:
- lang: eng
  text: 'We consider the problem of consensus in the challenging classic model. In
    this model, the adversary is adaptive; it can choose which processors crash at
    any point during the course of the algorithm. Further, communication is via asynchronous
    message passing: there is no known upper bound on the time to send a message from
    one processor to another, and all messages and coin flips are seen by the adversary.
    We describe a new randomized consensus protocol with expected message complexity
    O(n2log2n) when fewer than n / 2 processes may fail by crashing. This is an almost-linear
    improvement over the best previously known protocol, and within logarithmic factors
    of a known Ω(n2) message lower bound. The protocol further ensures that no process
    sends more than O(nlog3n) messages in expectation, which is again within logarithmic
    factors of optimal. We also present a generalization of the algorithm to an arbitrary
    number of failures t, which uses expected O(nt+t2log2t) total messages. Our approach
    is to build a message-efficient, resilient mechanism for aggregating individual
    processor votes, implementing the message-passing equivalent of a weak shared
    coin. Roughly, in our protocol, a processor first announces its votes to small
    groups, then propagates them to increasingly larger groups as it generates more
    and more votes. To bound the number of messages that an individual process might
    have to send or receive, the protocol progressively increases the weight of generated
    votes. The main technical challenge is bounding the impact of votes that are still
    “in flight” (generated, but not fully propagated) on the final outcome of the
    shared coin, especially since such votes might have different weights. We achieve
    this by leveraging the structure of the algorithm, and a technical argument based
    on martingale concentration bounds. Overall, we show that it is possible to build
    an efficient message-passing implementation of a shared coin, and in the process
    (almost-optimally) solve the classic consensus problem in the asynchronous message-passing
    model.'
article_processing_charge: Yes (via OA deal)
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: James
  full_name: Aspnes, James
  last_name: Aspnes
- first_name: Valerie
  full_name: King, Valerie
  last_name: King
- first_name: Jared
  full_name: Saia, Jared
  last_name: Saia
citation:
  ama: Alistarh D-A, Aspnes J, King V, Saia J. Communication-efficient randomized
    consensus. <i>Distributed Computing</i>. 2018;31(6):489-501. doi:<a href="https://doi.org/10.1007/s00446-017-0315-1">10.1007/s00446-017-0315-1</a>
  apa: Alistarh, D.-A., Aspnes, J., King, V., &#38; Saia, J. (2018). Communication-efficient
    randomized consensus. <i>Distributed Computing</i>. Springer. <a href="https://doi.org/10.1007/s00446-017-0315-1">https://doi.org/10.1007/s00446-017-0315-1</a>
  chicago: Alistarh, Dan-Adrian, James Aspnes, Valerie King, and Jared Saia. “Communication-Efficient
    Randomized Consensus.” <i>Distributed Computing</i>. Springer, 2018. <a href="https://doi.org/10.1007/s00446-017-0315-1">https://doi.org/10.1007/s00446-017-0315-1</a>.
  ieee: D.-A. Alistarh, J. Aspnes, V. King, and J. Saia, “Communication-efficient
    randomized consensus,” <i>Distributed Computing</i>, vol. 31, no. 6. Springer,
    pp. 489–501, 2018.
  ista: Alistarh D-A, Aspnes J, King V, Saia J. 2018. Communication-efficient randomized
    consensus. Distributed Computing. 31(6), 489–501.
  mla: Alistarh, Dan-Adrian, et al. “Communication-Efficient Randomized Consensus.”
    <i>Distributed Computing</i>, vol. 31, no. 6, Springer, 2018, pp. 489–501, doi:<a
    href="https://doi.org/10.1007/s00446-017-0315-1">10.1007/s00446-017-0315-1</a>.
  short: D.-A. Alistarh, J. Aspnes, V. King, J. Saia, Distributed Computing 31 (2018)
    489–501.
corr_author: '1'
date_created: 2018-12-11T11:47:01Z
date_published: 2018-11-01T00:00:00Z
date_updated: 2026-04-16T09:53:54Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00446-017-0315-1
external_id:
  isi:
  - '000443832300005'
file:
- access_level: open_access
  checksum: 69b46e537acdcac745237ddb853fcbb5
  content_type: application/pdf
  creator: dernst
  date_created: 2019-01-22T07:25:51Z
  date_updated: 2020-07-14T12:46:38Z
  file_id: '5867'
  file_name: 2017_DistribComp_Alistarh.pdf
  file_size: 595707
  relation: main_file
file_date_updated: 2020-07-14T12:46:38Z
has_accepted_license: '1'
intvolume: '        31'
isi: 1
issue: '6'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 489-501
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: Distributed Computing
publication_identifier:
  issn:
  - 0178-2770
publication_status: published
publisher: Springer
publist_id: '7281'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Communication-efficient randomized consensus
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 31
year: '2018'
...