Robust Comparison in Population Protocols
There has recently been a surge of interest in the computational and complexity properties of the population model, which assumes anonymous, computationally-bounded nodes, interacting at random, and attempting to jointly compute global predicates. Significant work has gone towards investigating majority and consensus dynamics in this model: assuming that each node is initially in one of two states or , determine which state had higher initial count. In this paper, we consider a natural generalization of majority/consensus, which we call comparison. We are given two baseline states, and , present in any initial configuration in fixed, possibly small counts. Importantly, one of these states has higher count than the other: we will assume for some constant . The challenge is to design a protocol which can quickly and reliably decide on which of the baseline states and has higher initial count. We propose a simple algorithm solving comparison: the baseline algorithm uses states per node, and converges in (parallel) time, with high probability, to a state where whole population votes on opinions or at rates proportional to initial vs. concentrations. We then describe how such output can be then used to solve comparison. The algorithm is self-stabilizing, in the sense that it converges to the correct decision even if the relative counts of baseline states and change dynamically during the execution, and leak-robust, in the sense that it can withstand spurious faulty reactions. Our analysis relies on a new martingale concentration result which relates the evolution of a population protocol to its expected (steady-state) analysis, which should be broadly applicable in the context of population protocols and opinion dynamics.