




Publications  Proving the HermanProtocol Conjecture





Reference:
Maria Bruna, Radu Grigore, Stefan Kiefer, Joël Ouaknine, and James Worrell. Proving the Hermanprotocol conjecture. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 104:1–104:12, 2016.
Abstract:
Herman's selfstabilization algorithm, introduced 25 years ago, is a wellstudied 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 worstcase 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 h N^2. Ten years ago, McIver and Morgan established a lower bound of 4/27 for h, achieved with three equallyspaced 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.
Suggested BibTeX entry:
@inproceedings{16BGKOWICALP,
author = {Maria Bruna and Radu Grigore and Stefan Kiefer and Jo{\"e}l Ouaknine and James Worrell},
booktitle = {Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {104:1104:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
title = {Proving the {H}ermanProtocol Conjecture},
volume = {55},
year = {2016}
}




