---
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. In this work,
we consider the more general setting where G is an arbitrary 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 an example,
this implies 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.@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.DISC.2021.43
bibo_volume: 209
dct_date: 2021^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/9-783-9597-7210-5
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: 'Brief announcement: Fast graphical population protocols@'
...