Self-Stabilizing Leader Election in Regular Graphs
Self-Stabilizing Leader Election in Regular Graphs
复制标题
正则图中的自稳定领导者选举
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ho
中科院分区：
文献类型：
--
作者：
Hsueh;Ho
人口协议[3]被用作分布式模型，捕获被动移动的代理的行为。领导人选举是该模型中研究最多的问题之一。在本文中，我们专注于自稳定的领导者选举（SSLE）问题提出的Angluin等。以前，已知SSLE可以在具有恒定状态数的任意环和环面上执行[11]，但完全图上的SSLE需要Ω（n）个状态[9]。在本文中，我们提出了第一个SSLE人口协议的任意k-正则图，解决了一个公开的问题，在[5]。本文中有两种不同的SSLE协议。在这两个协议中，状态的数量与图的大小无关。第一个协议更简单，更直观，但需要O（（64 c）k ·k4 k +4）个状态，其中c是SSLE协议用于环的常数状态数[11]。第二个协议是更仔细地设计，以减少状态的数量为O（k12）。这两种构造都可以应用于任意图，如果每个节点都知道自己的度。
Population protocols [3] are used as a distributed model that captures the behavior of passively mobile agents. Leader election is one of the most well-studied problems in this model. In this paper, we focus on the self-stabilizing leader election (SSLE) problem proposed by Angluin et al. [5]. Previously, it is known that SSLE can be performed on arbitrary rings and tori with a constant number of states [11], but SSLE on complete graphs requires Ω(n) states [9]. In this paper, we propose the first SSLE population protocol for arbitrary k-regular graphs, which solves an open question proposed in [5]. There are two different SSLE protocols in this paper. In both protocols, the number of states is independent of the size of the graph. The first protocol is simpler and more intuitive but requires O((64c)k · k4k+4) states, where c is the constant number of states used by the SSLE protocol for rings [11]. The second protocol is more carefully designed to reduce the number of states to O(k12). Both of these two constructions can apply to arbitrary graphs if every node knows its own degree.