The Same Speed Timer in Population Protocols
The Same Speed Timer in Population Protocols
复制标题
群体协议中的同速计时器
DOI：
10.1109/icdcs.2016.82
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
L. Larmore
中科院分区：
文献类型：
--
作者：
Y. Sudo;T. Masuzawa;A. Datta;L. Larmore
提出了一种新的同速定时器的概念，并将其应用于种群协议（PP）模型中，以提高现有松散稳定领袖选举协议的收敛时间。松稳定的领导者选举保证了系统从任意配置出发，在短时间内达到安全配置（收敛），之后系统长时间保持唯一的领导者（闭包）。文献中存在两种任意图的松散稳定leader选举协议；一个使用节点标识符，另一个使用随机数来选举唯一的领导者。这两种协议都保证预期的收敛时间是多项式的，预期的保持时间（保持领头羊的时间）是指数的。在不影响指数保持时间的前提下，采用相同速度的定时器显著提高了这些协议的收敛时间。具体地说，给出了一种使用节点标识符的快速确定性松散稳定领导者选举协议和一种快速随机松散稳定领导者选举协议。前一种协议的期望收敛时间为O(mN log N)，期望保持时间为Ω（Ne2N），其中m为图中边数，N为节点数N的给定上界。后一种协议的期望收敛时间为O(mN2 log N)，期望保持时间为Ω（Ne2N）。给出了一种仅占用每个agent O（log n）内存空间的自稳定两跳着色协议，作为后一种协议的工具。给出了一个下界：任何具有期望指数保持时间的松散稳定领袖选举协议都需要Ω（mN）期望收敛时间。
A novel concept of the same speed timer is presented, and is applied in the population protocol (PP) model to improve the convergence time of existing loosely-stabilizing leader election protocols. Loosely-stabilizing leader election guarantees that, starting from any configuration, the system reaches a safe configuration within a short time (convergence), and after that, the system keeps the unique leader for a long time (closure). Two loosely-stabilizing leader election protocols for arbitrary graphs exist in the literature; one uses identifiers of nodes and the other uses random numbers to elect a unique leader. Both protocols guarantee that the expected convergence time is polynomial and the expected holding time (the time the leader is kept) is exponential. In this paper, convergence time of these protocols is dramatically improved by the same speed timer without impairing the exponential holding time. Specifically, a fast deterministic loosely-stabilizing leader election protocol that uses identifiers of nodes and a fast randomized looselystabilizing leader election protocol are given. The expected convergence time and expected holding time of the former protocol are O(mN log N) and Ω(Ne2N), respectively, where m is the number of edges in the graph and N is a given upper bound on the number of nodes n. The expected convergence time and expected holding time of the latter protocol are O(mN2 log n) and Ω(Ne2N), respectively. A self-stabilizing two-hop coloring protocol that uses only O(log n) memory space of each agent is given as a tool of the latter protocol. A lower bound is also given: any loosely-stabilizing leader election protocol with expected exponential holding time requires Ω(mN) expected convergence time.
介导群体协议中自稳定领导人选举的空间复杂度
影响因子：
1.3
作者：
Ryu Mizoguchi;Hirotaka Ono;Shuji Kijima;Masafumi Yamashita
通讯作者：
Masafumi Yamashita
群体协议模型中松散稳定的领导者选举
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
Sudo;Yuichi
通讯作者：
Yuichi