论文标题
全球知识在自我稳定人群方案方面的力量
The Power of Global Knowledge on Self-stabilizing Population Protocols
论文作者
论文摘要
在人口协议模型中，无法以自动稳定的方式解决许多问题。但是，全球知识，例如网络中的节点数量，有时使我们可以针对此类问题设计一个自动化的协议。在本文中，我们研究了全球知识对任意图中人口协议的可能性的影响。具体而言，我们通过了解网络中的节点数量和/或网络中的边缘数来阐明领导者选举问题，排名问题，学位识别问题和邻居识别问题的解决性。
In the population protocol model, many problems cannot be solved in a self-stabilizing way. However, global knowledge, such as the number of nodes in a network, sometimes allows us to design a self-stabilizing protocol for such problems. In this paper, we investigate the effect of global knowledge on the possibility of self-stabilizing population protocols in arbitrary graphs. Specifically, we clarify the solvability of the leader election problem, the ranking problem, the degree recognition problem, and the neighbor recognition problem by self-stabilizing population protocols with knowledge of the number of nodes and/or the number of edges in a network.
