On Stabilization in Herman’s Algorithm

Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, James Worrell, Lijun Zhang

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    Herman’s algorithm is a synchronous randomized protocol for achieving self-stabilization in a token ring consisting of N processes. The interaction of tokens makes the dynamics of the protocol very difficult to analyze. In this paper we study the expected time to stabilization in terms of the initial configuration. It is straightforward that the algorithm achieves stabilization almost surely from any initial configuration, and it is known that the worst-case expected time to stabilization (with respect to the initial configuration) is Θ(N2). Our first contribution is to give an upper bound of 0.64N2 on the expected stabilization time, improving on previous upper bounds and reducing the gap with the best existing lower bound. We also introduce an asynchronous version of the protocol, showing a similar O(N2) convergence bound in this case. Assuming that errors arise from the corruption of some number k of bits, where k is fixed independently of the size of the ring, we show that the expected time to stabilization is O(N). This reveals a hitherto unknown and highly desirable property of Herman’s algorithm: it recovers quickly from bounded errors. We also show that if the initial configuration arises by resetting each bit independently and uniformly at random, then stabilization is significantly faster than in the worst case.
    Original languageEnglish
    Title of host publicationAutomata, Languages and Programming : 38th International Colloquium, ICALP 2011 - Zurich, Switzerland, July 4-8, 2011 - Proceedings, Part II
    PublisherSpringer
    Publication date2011
    Pages466-477
    ISBN (Print)978-3-642-22011-1
    ISBN (Electronic)978-3-642-22012-8
    DOIs
    Publication statusPublished - 2011
    Event38th International Colloquium on Automata, Languages and Programming - Zürich, Switzerland
    Duration: 4 Jul 20118 Jul 2011
    Conference number: 38

    Conference

    Conference38th International Colloquium on Automata, Languages and Programming
    Number38
    CountrySwitzerland
    CityZürich
    Period04/07/201108/07/2011
    SeriesLecture Notes in Computer Science
    Number6756
    ISSN0302-9743

    Fingerprint Dive into the research topics of 'On Stabilization in Herman’s Algorithm'. Together they form a unique fingerprint.

    Cite this