Proving the Herman-Protocol Conjecture
Proving the Herman-Protocol Conjecture
复制标题
DOI：
10.4230/lipics.icalp.2016.104
复制
发表时间：
2015-04
期刊：
影响因子：
--
通讯作者：
M. Bruna;Radu Grigore;S. Kiefer;Joël Ouaknine;J. Worrell
中科院分区：
文献类型：
--
作者：
M. Bruna;Radu Grigore;S. Kiefer;Joël Ouaknine;J. Worrell
Herman的自稳定算法是25年前引入的，是一个经过充分研究的同步随机协议，它使N个进程的环能够共同持有任意奇数个令牌，从而达到一个稳定的状态，在这个状态下只有一个令牌保留。确定最坏情况下的预期稳定时间是该协议的核心突出开放问题。已知存在一个常数h，使得任何初始构型的预期稳定时间最多为hN2。十年前，McIver和Morgan为h建立了一个4/27 ~ 0.148的下界，用三个等间距的代币实现，并推测这是h的最优值。过去十年的一系列论文逐渐降低了h的上界，目前的记录（2014年实现）约为0.156。本文证明了McIver和Morgan的猜想，证明了h = 4/27确实是最优的。
Herman's self-stabilization algorithm, introduced 25 years ago, is a well-studied synchronous randomized protocol for enabling a ring of N processes collectively holding any odd number of tokens to reach a stable state in which a single token remains. Determining the worst-case expected time to stabilization is the central outstanding open problem about this protocol. It is known that there is a constant h such that any initial configuration has expected stabilization time at most hN2. Ten years ago, McIver and Morgan established a lower bound of 4/27 ~ 0.148 for h, achieved with three equally-spaced tokens, and conjectured this to be the optimal value of h. A series of papers over the last decade gradually reduced the upper bound on h, with the present record (achieved in 2014) standing at approximately 0.156. In this paper, we prove McIver and Morgan's conjecture and establish that h = 4/27 is indeed optimal.