License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.43
URN: urn:nbn:de:0030-drops-148451
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14845/
Go to the corresponding LIPIcs Volume Portal

Alistarh, Dan ; Gelashvili, Rati ; Rybicki, Joel

Brief Announcement: Fast Graphical Population Protocols

pdf-format:
LIPIcs-DISC-2021-43.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{alistarh_et_al:LIPIcs.DISC.2021.43,
  author =	{Alistarh, Dan and Gelashvili, Rati and Rybicki, Joel},
  title =	{{Brief Announcement: Fast Graphical Population Protocols}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{43:1--43:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14845},
  URN =		{urn:nbn:de:0030-drops-148451},
  doi =		{10.4230/LIPIcs.DISC.2021.43},
  annote =	{Keywords: population protocols, leader election, majority}
}

Keywords: population protocols, leader election, majority
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI