论文标题
自我稳定人群方案的组合表征
A Combinatorial Characterization of Self-Stabilizing Population Protocols
论文作者
论文摘要
我们完全表征了人口协议中的自动稳定功能，以进行完整的交互图。特别是，我们调查了$ n $有限状态代理系统中的自动稳定化，其中恶意调度程序在全球公平条件下选择了任意的成对互动序列。我们展示了自我稳定的必要条件。具体而言，我们表明，没有某些设定理论条件的功能是不可能以自动稳定的方式计算的。我们的主要贡献是在匡威中，我们为所有其他符合此特征的功能构建了一个自动化的协议。我们的积极结构利用迪克森的引理来开发根集的概念，这个概念从根本上表征了这种模型中的自我稳定。我们认为，这也可以在更一般的模型中表征自我稳定。
We fully 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.
