Brief Announcement: Fast Graphical Population Protocols

DOI10.4230/LIPICS.DISC.2021.43arXiv2102.08808OpenAlexW3209321351MaRDI QIDQ6083418FDOQ6083418

Authors: Dan Alistarh, Rati Gelashvili, Joel Rybicki 

Publication date: 8 December 2023

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 $noperatornamepolylogn$ pairwise interactions, with high probability, using at most $operatornamepolylogn$ 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 a sample application, we show that, in any regular graph with conductance $phi$, both leader election and exact majority can be solved in $ph{i}^{-2}cdotnoperatornamepolylogn$ pairwise interactions, with high probability, using at most $ph{i}^{-2}cdotoperatornamepolylogn$ 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.

Full work available at URL: https://arxiv.org/abs/2102.08808

Recommendations

• Brief Announcement
• Population protocols on graphs: a hierarchy
• The Dynamics of Probabilistic Population Protocols
• The computational power of population protocols
• scientific article; zbMATH DE number 7651155
• Fast and exact majority in population protocols
• Brief announcement: Fast approximate counting and leader election in populations

zbMATH Keywords

majorityleader electionpopulation protocols

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (1)

• Brief Announcement

This page was built for publication: Brief Announcement: Fast Graphical Population Protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083418)