---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Dan-Adrian
      foaf_name: Alistarh, Dan-Adrian
      foaf_surname: Alistarh
      foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-3650-940X
  - foaf_Person:
      foaf_givenName: Rati
      foaf_name: Gelashvili, Rati
      foaf_surname: Gelashvili
  - foaf_Person:
      foaf_givenName: Joel
      foaf_name: Rybicki, Joel
      foaf_surname: Rybicki
      foaf_workInfoHomepage: http://www.librecat.org/personId=334EFD2E-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-6432-6646
  bibo_doi: 10.4230/LIPIcs.OPODIS.2021.14
  bibo_volume: 217
  dct_date: 2022^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959772198
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Fast graphical population protocols@
...