On a random walk problem arising in self-stabilizing token management
On a random walk problem arising in self-stabilizing token management
复制标题
关于自稳定代币管理中出现的随机游走问题
DOI：
10.1145/112600.112623
复制
发表时间：
1991
影响因子：
2.5
通讯作者：
P. Winkler
中科院分区：
文献类型：
--
作者：
P. Tetali;P. Winkler
我们证明了以色列和Jalfon在PODC‘90中提出的令牌管理协议在多项式时间内自稳定。该协议利用随机行走中的偶然相遇，将多个令牌减少到只有一个。在抽象的情况下，我们的定理是这样的：设两个记号被放置在一个连通的、无向的、n-顶点图的顶点上。假设在时钟的每一刻都有一个“调度恶魔”指向其中一个令牌，然后该令牌随机一步到达相邻的顶点。然后，不管恶魔的策略是什么，令牌将在预期的时间内最多在8n3/27见面。我们的证明技术新颖地使用了顶点对上的势函数、“远程性”序和随机游走恒等式，所有这些都可能具有独立的理论兴趣。
We show that the token management protocol proposed by Israeli and Jalfon in PODC ’90 self-stabilizes in polynomial time. The protocol makes use of accidental meetings in random walks to reduce a multiplicity of tokens to only one. In an abstract setting, our theorem reads as follows: Let two tokens be placed on vertices of a connected, undirected, n-vertex graph. Suppose that at each tick of a clock a “schedule demon” points to one of the tokens, which then takes a random step to a neighboring vertex. Then, regardless of the demon’s strategy, the tokens will meet in expected time at most 8n3/27. Our proof technique makes novel use of a potential function on pairs of vertices, a “remoteness” ordering and a random walk identity, all of which may be of independent theoretical interest.