Comparison dynamics in population protocols

Alistarh D-A, Töpfer M, Uznański P. 2021. Comparison dynamics in population protocols. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 55–65.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Department
Abstract
There has recently been a surge of interest in the computational and complexity properties of the population model, which assumes n anonymous, computationally-bounded nodes, interacting at random, with the goal of jointly computing global predicates. Significant work has gone towards investigating majority or consensus dynamics in this model: that is, assuming that every node is initially in one of two states X or Y, determine which state had higher initial count. In this paper, we consider a natural generalization of majority/consensus, which we call comparison : in its simplest formulation, we are given two baseline states, X and Y, present in any initial configuration in fixed, but possibly small counts. One of these states has higher count than the other: we will assume |X_0| > C |Y_0| for some constant C > 1. The challenge is to design a protocol by which nodes can quickly and reliably decide on which of the baseline states X_0 and Y_0 has higher initial count. We begin by analyzing a simple and general dynamics solving the above comparison problem, which uses O( log n ) states per node, and converges in O(log n) (parallel) time, with high probability, to a state where the whole population votes on opinions X or Y at rates proportional to the initial concentrations of |X_0| vs. |Y_0|. We then describe how this procedure can be bootstrapped to solve comparison, i.e. have every node in the population reach the "correct'' decision, with probability 1 - o(1), at the cost of O (log log n) additional states. Further, we prove that this dynamics is self-stabilizing, in the sense that it converges to the correct decision from arbitrary initial states, and leak-robust, in the sense that it can withstand spurious faulty reactions, which are known to occur in practical implementations of population protocols. Our analysis is based on a new martingale concentration result relating the discrete-time evolution of a population protocol to its expected (steady-state) analysis, which should be a useful tool when analyzing opinion dynamics and epidemic dissemination in the population model.
Publishing Year
Date Published
2021-07-21
Proceedings Title
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
Acknowledgement
We would like to thank Rati Gelashvili for very useful discussions, and the PODC anonymous reviewers for their careful reading of our paper, and for their useful remarks. This work is partially supported by the Polish National Science Center (NCN) grant UMO2017/25/B/ST6/02010.
Page
55-65
Conference
PODC: Symposium on Principles of Distributed Computing
Conference Location
Virtual, Italy
Conference Date
2021-07-26 – 2021-07-30
IST-REx-ID

Cite this

Alistarh D-A, Töpfer M, Uznański P. Comparison dynamics in population protocols. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2021:55-65. doi:10.1145/3465084.3467915
Alistarh, D.-A., Töpfer, M., & Uznański, P. (2021). Comparison dynamics in population protocols. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (pp. 55–65). Virtual, Italy: Association for Computing Machinery. https://doi.org/10.1145/3465084.3467915
Alistarh, Dan-Adrian, Martin Töpfer, and Przemysław Uznański. “Comparison Dynamics in Population Protocols.” In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, 55–65. Association for Computing Machinery, 2021. https://doi.org/10.1145/3465084.3467915.
D.-A. Alistarh, M. Töpfer, and P. Uznański, “Comparison dynamics in population protocols,” in Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Virtual, Italy, 2021, pp. 55–65.
Alistarh D-A, Töpfer M, Uznański P. 2021. Comparison dynamics in population protocols. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 55–65.
Alistarh, Dan-Adrian, et al. “Comparison Dynamics in Population Protocols.” Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 55–65, doi:10.1145/3465084.3467915.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search