---
_id: '11184'
abstract:
- lang: eng
  text: "Let G be a graph on n nodes. In the stochastic population protocol model,
    a collection of n indistinguishable, resource-limited nodes collectively solve
    tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
    first read each other’s states, and then update their local states. A rich line
    of research has established tight upper and lower bounds on the complexity of
    fundamental tasks, such as majority and leader election, in this model, when G
    is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
    in n polylog n pairwise interactions, with high probability, using at most polylog
    n states per node.\r\nIn this work, we consider the more general setting where
    G is an arbitrary regular graph, and present a technique for simulating protocols
    designed for fully-connected networks in any connected regular graph. Our main
    result is a simulation that is efficient on many interesting graph families: roughly,
    the simulation overhead is polylogarithmic in the number of nodes, and quadratic
    in the conductance of the graph. As a sample application, we show that, in any
    regular graph with conductance φ, both leader election and exact majority can
    be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability,
    using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast
    and space-efficient population protocols for leader election and exact majority
    on graphs with good expansion properties. We believe our results will prove generally
    useful, as they allow efficient technology transfer between the well-mixed (clique)
    case, and the under-explored spatial setting."
acknowledgement: "Dan Alistarh: This project has received funding from the European
  Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
  programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has
  received from the European Union’s Horizon 2020 research and\r\ninnovation programme
  under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements
  We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock
  construction to non-regular graphs. We also thank anonymous reviewers for their
  useful comments on earlier versions of this manuscript."
alternative_title:
- LIPIcs
article_number: '14'
article_processing_charge: No
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: Rati
  full_name: Gelashvili, Rati
  last_name: Gelashvili
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
citation:
  ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols.
    In: Bramas Q, Gramoli V, Milani A, eds. <i>25th International Conference on Principles
    of Distributed Systems</i>. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2022. doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.14">10.4230/LIPIcs.OPODIS.2021.14</a>'
  apa: 'Alistarh, D.-A., Gelashvili, R., &#38; Rybicki, J. (2022). Fast graphical
    population protocols. In Q. Bramas, V. Gramoli, &#38; A. Milani (Eds.), <i>25th
    International Conference on Principles of Distributed Systems</i> (Vol. 217).
    Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.14">https://doi.org/10.4230/LIPIcs.OPODIS.2021.14</a>'
  chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical
    Population Protocols.” In <i>25th International Conference on Principles of Distributed
    Systems</i>, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol.
    217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.14">https://doi.org/10.4230/LIPIcs.OPODIS.2021.14</a>.
  ieee: D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population
    protocols,” in <i>25th International Conference on Principles of Distributed Systems</i>,
    Strasbourg, France, 2022, vol. 217.
  ista: Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols.
    25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs,
    vol. 217, 14.
  mla: Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” <i>25th
    International Conference on Principles of Distributed Systems</i>, edited by Quentin
    Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022, doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.14">10.4230/LIPIcs.OPODIS.2021.14</a>.
  short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A.
    Milani (Eds.), 25th International Conference on Principles of Distributed Systems,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
  end_date: 2021-12-15
  location: Strasbourg, France
  name: OPODIS
  start_date: 2021-12-13
corr_author: '1'
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2025-04-14T07:49:13Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.14
ec_funded: 1
editor:
- first_name: Quentin
  full_name: Bramas, Quentin
  last_name: Bramas
- first_name: Vincent
  full_name: Gramoli, Vincent
  last_name: Gramoli
- first_name: Alessia
  full_name: Milani, Alessia
  last_name: Milani
external_id:
  arxiv:
  - '2102.08808'
file:
- access_level: open_access
  checksum: 2c7c982174c6f98c4ca6e92539d15086
  content_type: application/pdf
  creator: dernst
  date_created: 2022-05-02T08:06:33Z
  date_updated: 2022-05-02T08:06:33Z
  file_id: '11346'
  file_name: 2022_LIPICs_Alistarh.pdf
  file_size: 959406
  relation: main_file
  success: 1
file_date_updated: 2022-05-02T08:06:33Z
fulldoi: https://doi.org/10.4230/LIPIcs.OPODIS.2021.14
has_accepted_license: '1'
intvolume: '       217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '840605'
  name: Coordination in constrained and natural distributed systems
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
  isbn:
  - '9783959772198'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast graphical population protocols
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
volume: 217
year: '2022'
...