On the expected time for Herman's probabilistic self-stabilizing algorithm
On the expected time for Herman's probabilistic self-stabilizing algorithm
复制标题
DOI：
10.1016/j.tcs.2005.05.022
复制
发表时间：
2004-08
期刊：
影响因子：
--
通讯作者：
Toshio Nakata
中科院分区：
文献类型：
--
作者：
Toshio Nakata
本文研究了分布式系统中Herman概率自稳定算法的期望时间：假设单向环中相同进程的个数为奇数，n⩾为3。如果环的初始配置不合法，即令牌个数不同于1，则执行由局部参数为0和1的同步概率过程组成的算法将导致收敛到具有唯一令牌的合法配置(Herman算法)。然后我们证明了收敛的期望时间小于((π2-8)/8r(1-r))n2。请注意，如果r=12，则它以0.936n2为界。此外，还存在一个预期时间为Θ(N2)的配置。证明的方法是基于融合随机游动的分析。
In this article we investigate the expected time for Herman's probabilistic self-stabilizing algorithm in distributed systems: suppose that the number of identical processes in a unidirectional ring, say n, is odd and n⩾3. If the initial configuration of the ring is not “legitimate”, that is, the number of tokens differs from one, then execution of the algorithm made up of synchronous probabilistic procedures with a local parameter 0<r<1 results in convergence to a legitimate configuration with a unique token (Herman's algorithm). We then show that the expected time of the convergence is less than ((π2-8)/8r(1-r))n2. Note that if r=12 then it is bounded by 0.936n2. Moreover, there exists a configuration whose expected time is Θ(n2). The method of the proof is based on the analysis of coalescing random walks.