## Proving the Herman-Protocol Conjecture

*Maria Bruna*, *Radu Grigore*, *Stefan Kiefer*,
*Joël
Ouaknine*, and *James Worrell*
Herman's self-stabilisation algorithm, introduced 25 years ago, is a
well-studied synchronous randomised 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 stabilisation 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
stabilisation time at most *hN*^{2}. 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 last year)
standing at approximately 0.156. In this paper, we prove McIver and
Morgan's conjecture and establish that *h* = 4/27 is indeed optimal.

*Proceedings of ICALP 16*, LIPIcs 55, 2016. 17 pages.

PDF
© 2016 Maria Bruna, Radu Grigore, Stefan Kiefer,
Joël Ouaknine, and James Worrell.