Self-Stabilizing Population Protocols With Global Knowledge
Self-Stabilizing Population Protocols With Global Knowledge
复制标题
DOI：
10.1109/tpds.2021.3076769
复制
发表时间：
2021-12
影响因子：
5.3
通讯作者：
Y. Sudo;M. Shibata;Junya Nakamura;Yonghwan Kim;T. Masuzawa
中科院分区：
文献类型：
--
作者：
Y. Sudo;M. Shibata;Junya Nakamura;Yonghwan Kim;T. Masuzawa
在种群协议模型中，许多问题不能以自稳定的方式解决。然而，全局知识（例如网络中的节点数量）有时可以为此类问题设计自稳定协议。例如，已知当且仅当每个节点都知道确切的节点数时，我们可以解决完全图中的自稳定领导者选举问题。在本文中，我们研究了全局知识对任意图中自稳定种群协议可能性的影响。具体来说，我们利用已知网络中节点数和/或边数的自稳定种群协议，阐明了首领选举问题、排序问题、度识别问题和邻居识别问题的可解性。
In the population protocol model, many problems cannot be solved in a self-stabilizing manner. However, global knowledge, such as the number of nodes in a network, sometimes enables the design of a self-stabilizing protocol for such problems. For example, it is known that we can solve the self-stabilizing leader election in complete graphs if and only if every node knows the exact number of nodes. In this article, 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.