---
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'
...