License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.104
URN: urn:nbn:de:0030-drops-62393
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6239/
Go to the corresponding LIPIcs Volume Portal

Bruna, Maria ; Grigore, Radu ; Kiefer, Stefan ; Ouaknine, Joël ; Worrell, James

Proving the Herman-Protocol Conjecture

pdf-format:
LIPIcs-ICALP-2016-104.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bruna_et_al:LIPIcs:2016:6239,
  author =	{Maria Bruna and Radu Grigore and Stefan Kiefer and Jo{\"e}l Ouaknine and James Worrell},
  title =	{{Proving the Herman-Protocol Conjecture}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{104:1--104:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6239},
  URN =		{urn:nbn:de:0030-drops-62393},
  doi =		{10.4230/LIPIcs.ICALP.2016.104},
  annote =	{Keywords: randomized protocols, self-stabilization, Lyapunov function, expected time}
}

Keywords: randomized protocols, self-stabilization, Lyapunov function, expected time
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI