A combinatorial characterization of self-stabilizing population protocols.
A combinatorial characterization of self-stabilizing population protocols.
复制标题
自稳定群体协议的组合表征。
DOI：
10.1007/978-3-030-64348-5_13
复制
发表时间：
2022
影响因子：
1
通讯作者：
Ostrovsky, Rafail
中科院分区：
文献类型：
--
作者：
Mathur, Shaan;Ostrovsky, Rafail
我们的特点是自稳定功能的人口协议的完整的相互作用图。特别是，我们调查的自稳定系统ofNfinite状态代理，其中一个恶意的调度程序选择一个任意序列的成对的相互作用下的全球公平性条件。我们证明了自稳定的一个充分必要条件。具体来说，我们表明，没有一定的集合论条件的功能是不可能计算的自稳定的方式。我们的主要贡献是在匡威的情况下，我们构建了一个自稳定协议的所有其他功能，满足此特性。我们的正向构造使用迪克森引理来发展根集的概念，事实证明，这个概念从根本上描述了该模型中的自稳定性。我们相信，这可能有助于在更一般的模型中描述自稳定性。
We characterize self-stabilizing functions in population protocols for complete interaction graphs. In particular, we investigate self-stabilization in systems ofNfinite 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.