A Combinatorial Characterization of Self-stabilizing Population Protocols
Shaan Mathur, Rafail Ostrovsky
Abstract:
We characterize self-stabilizing functions in population protocols for complete interaction graphs. In particular, we investigate self-stabilization in systems of n finite state agents in which a malicious scheduler selects an arbitrary sequence of pairwise interactions under a global fairness condition. We show a necessary and sufficient condition for self-stabilization. Specifically we show that functions without certain set-theoretic conditions are impossible to compute in a self-stabilizing manner. Our main contribution is in the converse, where we construct a self-stabilizing protocol for all other functions that meet this characterization. Our positive construction uses Dickson’s Lemma to develop the notion of the root set, a concept that turns out to fundamentally characterize self-stabilization in this model. We believe it may lend to characterizing self-stabilization in more general models as well.
comment:
SSS 2020: 167-182
Journal version: Information and Computation 285: 104829 (2022) [Journal]
Fetch PDF file of the paper