---
_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
corr_author: '1'
date_created: 2022-08-14T22:01:46Z
date_published: 2022-07-21T00:00:00Z
date_updated: 2025-12-30T09:04:17Z
day: '21'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3519270.3538435
ec_funded: 1
external_id:
  arxiv:
  - '2205.12597'
  isi:
  - '001031439100030'
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'
isi: 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'
related_material:
  record:
  - id: '19969'
    relation: later_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: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2022'
...
---
OA_place: publisher
OA_type: green
_id: '22374'
abstract:
- lang: eng
  text: We study the broadcast problem on dynamic networks with n processes. The processes
    communicate in synchronous rounds along an arbitrary rooted tree. The sequence
    of trees is given by an adversary whose goal is to maximize the number of rounds
    until at least one process reaches all other processes. Previous research has
    shown a ⌈(3n-1)/(2)⌉-2 lower bound and an O(n log log n) upper bound. We show
    the first linear upper bound for this problem, namely ⌈(1 + √2) n-1⌉ ~2.4n. Our
    result follows from a detailed analysis of the evolution of the adjacency matrix
    of the network over time.
acknowledgement: "This project has received funding from the European Research\r\nCouncil
  (ERC) under the European Union’s Horizon 2020 research\r\nand innovation programme
  (grant agreement No. 101019564). This\r\nwork was further supported by the Austrian
  Science Fund (FWF)\r\nand netIDEE SCIENCE project P 33775-N, and by the Federal
  Ministry of Education and Research (BMBF, Germany), 6G-RIC under\r\nGrant 16KISK020K.
  We would like to thank Kyrill Winkler for his\r\ninputs and feedback on this paper.\r\n"
article_processing_charge: No
arxiv: 1
author:
- first_name: Antoine
  full_name: El-Hayek, Antoine
  id: 888a098e-fcac-11ee-aff7-d347be57b725
  last_name: El-Hayek
  orcid: 0000-0003-4268-7368
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: 'El-Hayek A, Henzinger M, Schmid S. Brief announcement: Broadcasting time in
    dynamic rooted trees is linear. In: <i>Proceedings of the ACM Symposium on Principles
    of Distributed Computing</i>. Association for Computing Machinery; 2022:54-56.
    doi:<a href="https://doi.org/10.1145/3519270.3538460">10.1145/3519270.3538460</a>'
  apa: 'El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2022). Brief announcement:
    Broadcasting time in dynamic rooted trees is linear. In <i>Proceedings of the
    ACM Symposium on Principles of Distributed Computing</i> (pp. 54–56). Salerno,
    Italy: Association for Computing Machinery. <a href="https://doi.org/10.1145/3519270.3538460">https://doi.org/10.1145/3519270.3538460</a>'
  chicago: 'El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Brief Announcement:
    Broadcasting Time in Dynamic Rooted Trees Is Linear.” In <i>Proceedings of the
    ACM Symposium on Principles of Distributed Computing</i>, 54–56. Association for
    Computing Machinery, 2022. <a href="https://doi.org/10.1145/3519270.3538460">https://doi.org/10.1145/3519270.3538460</a>.'
  ieee: 'A. El-Hayek, M. Henzinger, and S. Schmid, “Brief announcement: Broadcasting
    time in dynamic rooted trees is linear,” in <i>Proceedings of the ACM Symposium
    on Principles of Distributed Computing</i>, Salerno, Italy, 2022, pp. 54–56.'
  ista: 'El-Hayek A, Henzinger M, Schmid S. 2022. Brief announcement: Broadcasting
    time in dynamic rooted trees is linear. Proceedings of the ACM Symposium on Principles
    of Distributed Computing. PODC: Symposium on Principles of Distrubuted Computing,
    54–56.'
  mla: 'El-Hayek, Antoine, et al. “Brief Announcement: Broadcasting Time in Dynamic
    Rooted Trees Is Linear.” <i>Proceedings of the ACM Symposium on Principles of
    Distributed Computing</i>, Association for Computing Machinery, 2022, pp. 54–56,
    doi:<a href="https://doi.org/10.1145/3519270.3538460">10.1145/3519270.3538460</a>.'
  short: A. El-Hayek, M. Henzinger, S. Schmid, in:, Proceedings of the ACM Symposium
    on Principles of Distributed Computing, Association for Computing Machinery, 2022,
    pp. 54–56.
conference:
  end_date: 2022-07-29
  location: Salerno, Italy
  name: 'PODC: Symposium on Principles of Distrubuted Computing'
  start_date: 2022-07-25
date_created: 2026-07-20T11:46:26Z
date_published: 2022-07-21T00:00:00Z
date_updated: 2026-07-24T12:48:29Z
day: '21'
doi: 10.1145/3519270.3538460
extern: '1'
external_id:
  arxiv:
  - '2211.11352'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1145/3519270.3538460
month: '07'
oa: 1
oa_version: Published Version
page: 54-56
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - '9781450392624'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
  record:
  - id: '22281'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: 'Brief announcement: Broadcasting time in dynamic rooted trees is linear'
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2022'
...