---
res:
bibo_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.\r\n\r\nIn 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.@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: Martin
foaf_name: Töpfer, Martin
foaf_surname: Töpfer
foaf_workInfoHomepage: http://www.librecat.org/personId=4B865388-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Przemysław
foaf_name: Uznański, Przemysław
foaf_surname: Uznański
bibo_doi: 10.1145/3465084.3467915
dct_date: 2021^xs_gYear
dct_identifier:
- UT:000744439800005
dct_isPartOf:
- http://id.crossref.org/issn/9781450385480
dct_language: eng
dct_publisher: Association for Computing Machinery@
dct_title: Comparison dynamics in population protocols@
...