Loosely-stabilizing leader election with polylogarithmic convergence time
Loosely-stabilizing leader election with polylogarithmic convergence time
复制标题
具有多对数收敛时间的松散稳定领导者选举
DOI：
10.1016/j.tcs.2019.09.034
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Larmore Lawrence L.
中科院分区：
文献类型：
--
作者：
Sudo Yuichi;Ooshita Fukuhito;Kakugawa Hirotsugu;Masuzawa Toshimitsu;Datta Ajoy K.;Larmore Lawrence L.
提出了一种具有多对数收敛时间的群体协议模型中的松稳定领袖选举协议。在移动传感器网络常用的抽象模型——群体协议模型中，除非事先知道agent的确切数量，否则不可能设计出自稳定的leader选举协议。因此，在我们之前的工作中，我们引入了松散稳定的概念，它比自稳定弱，但在实践中具有类似的优势。在这项工作之后，给出了几个松散稳定的领导人选举协议。松散稳定的领导者选举保证了系统从任意配置开始，在短时间内达到具有单个领导者的安全配置，并在此后的很长一段时间内保持唯一领导者。现有所有松散稳定协议的收敛时间，即，即达到安全配置的预期时间是多项式，其中为节点数量，而它们的保持时间，即。，在达到安全配置后保持唯一领导者的预期时间为指数inn。提出了一种具有多对数收敛时间的松稳定协议。它的保持时间不是指数的，而是一个任意大的n的多项式函数。
A loosely-stabilizing leader election protocol with polylogarithmic convergence time in the population protocol model is presented in this paper. In the population protocol model, which is a common abstract model of mobile sensor networks, it is known to be impossible to design a self-stabilizing leader election protocol unless the exact number of agents is knowna priori. Thus, in our prior work, we introduced concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage in practice. Following this work, several loosely-stabilizing leader election protocols have been given. Loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a short time, and keeps the unique leader for a long time thereafter. The convergence times of all existing loosely-stabilizing protocols,i.e., the expected times to reach a safe configuration, are polynomial innwherenis the number of nodes, while their holding times,i.e., the expected times to keep the unique leader after reaching a safe configuration, are exponential inn. In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, rather an arbitrarily large polynomial function ofn.