2020/10/08 by Shaan Mathur, Rafail Ostrovsky, Mathur, Shaan +1
Computer Science · Social Sciences · #Access Control and Trust #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2010.03869
openalex publication_date 2020/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We fully characterize self-stabilizing functions in population protocols for\ncomplete interaction graphs. In particular, we investigate self-stabilization\nin systems of n finite state agents in which a malicious scheduler selects an\narbitrary sequence of pairwise interactions under a global fairness condition.\nWe show a necessary and sufficient condition for self-stabilization.\nSpecifically we show that functions without certain set-theoretic conditions\nare impossible to compute in a self-stabilizing manner. Our main contribution\nis in the converse, where we construct a self-stabilizing protocol for all\nother functions that meet this characterization. Our positive construction uses\nDickson's Lemma to develop the notion of the root set, a concept that turns out\nto fundamentally characterize self-stabilization in this model. We believe it\nmay lend to characterizing self-stabilization in more general models as well.\n