---
_id: '11844'
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) exactly 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.\r\n\r\nIn this work, we investigate the complexity of stable
    leader election on general graphs. We provide the first non-trivial time lower
    bounds for leader election on general graphs, showing that, when moving beyond
    cliques, the complexity landscape of leader election becomes very diverse: the
    time required to elect a leader can range from O(1) to Θ(n3) expected steps. On
    the upper bound side, we first observe that there exists 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(log2n) states that is at most a
    factor log n slower. Finally, we show that the constant-state protocol of Beauquier
    et al. [OPODIS 2013] is at most a factor n log n slower than the fast polynomial-state
    protocol. Moreover, among constant-state protocols, this protocol has near-optimal
    average case complexity on dense random graphs."
acknowledgement: We thank the anonymous reviewers for their helpful comments. 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)
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. In: <i>Proceedings of the Annual ACM Symposium on Principles
    of Distributed Computing</i>. Association for Computing Machinery; 2022:246-256.
    doi:<a href="https://doi.org/10.1145/3519270.3538435">10.1145/3519270.3538435</a>'
  apa: 'Alistarh, D.-A., Rybicki, J., &#38; Voitovych, S. (2022). Near-optimal leader
    election in population protocols on graphs. In <i>Proceedings of the Annual ACM
    Symposium on Principles of Distributed Computing</i> (pp. 246–256). Salerno, Italy:
    Association for Computing Machinery. <a href="https://doi.org/10.1145/3519270.3538435">https://doi.org/10.1145/3519270.3538435</a>'
  chicago: Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal
    Leader Election in Population Protocols on Graphs.” In <i>Proceedings of the Annual
    ACM Symposium on Principles of Distributed Computing</i>, 246–56. Association
    for Computing Machinery, 2022. <a href="https://doi.org/10.1145/3519270.3538435">https://doi.org/10.1145/3519270.3538435</a>.
  ieee: D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election
    in population protocols on graphs,” in <i>Proceedings of the Annual ACM Symposium
    on Principles of Distributed Computing</i>, Salerno, Italy, 2022, pp. 246–256.
  ista: 'Alistarh D-A, Rybicki J, Voitovych S. 2022. Near-optimal leader election
    in population protocols on graphs. Proceedings of the Annual ACM Symposium on
    Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
    Computing, 246–256.'
  mla: Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols
    on Graphs.” <i>Proceedings of the Annual ACM Symposium on Principles of Distributed
    Computing</i>, Association for Computing Machinery, 2022, pp. 246–56, doi:<a href="https://doi.org/10.1145/3519270.3538435">10.1145/3519270.3538435</a>.
  short: D.-A. Alistarh, J. Rybicki, S. Voitovych, in:, Proceedings of the Annual
    ACM Symposium on Principles of Distributed Computing, Association for Computing
    Machinery, 2022, pp. 246–256.
conference:
  end_date: 2022-07-29
  location: Salerno, Italy
  name: 'PODC: Symposium on Principles of Distributed Computing'
  start_date: 2022-07-25
date_created: 2022-08-14T22:01:46Z
date_published: 2022-07-21T00:00:00Z
date_updated: 2023-06-14T12:06:01Z
day: '21'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3519270.3538435
ec_funded: 1
external_id:
  arxiv:
  - '2205.12597'
file:
- access_level: open_access
  checksum: 4c6b29172b8e355b4fbc364a2e0827b2
  content_type: application/pdf
  creator: cchlebak
  date_created: 2022-08-16T08:05:15Z
  date_updated: 2022-08-16T08:05:15Z
  file_id: '11854'
  file_name: 2022_PODC_Alistarh.pdf
  file_size: 1593474
  relation: main_file
  success: 1
file_date_updated: 2022-08-16T08:05:15Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 246-256
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the Annual ACM Symposium on Principles of Distributed
  Computing
publication_identifier:
  isbn:
  - '9781450392624'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...