Skip to main content

Proving the Herman-Protocol Conjecture

Bruna, Maria, Grigore, Radu, Kiefer, Stefan, Ouaknine, Joël, Worrell, James (2016) Proving the Herman-Protocol Conjecture. In: Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide, eds. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics . 104:1-104:12. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Saarbrücken/Wadern, Germany ISBN 978-3-95977-013-2. (doi:10.4230/LIPIcs.ICALP.2016.104) (KAR id:55083)

PDF Author's Accepted Manuscript
Language: English


Download (368kB) Preview
[thumbnail of 1504.01130v3.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL
http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.104

Abstract

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 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.

Item Type: Conference or workshop item (Paper)
DOI/Identification number: 10.4230/LIPIcs.ICALP.2016.104
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Radu Grigore
Date Deposited: 03 May 2016 11:30 UTC
Last Modified: 10 Mar 2021 17:16 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/55083 (The current URI for this page, for reference purposes)
Grigore, Radu: https://orcid.org/0000-0003-1128-0311
  • Depositors only (login required):

Downloads

Downloads per month over past year