I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Three tokens in Herman's algorithm


Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, Björn Wachter, and James Worrell. Three tokens in Herman's algorithm. Formal Aspects of Computing, 24(4):671–678, 2012.


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 distribution of the time to stabilization, assuming that there are three tokens in the initial configuration. We show for arbitrary N and for an arbitrary timeout t that the probability of stabilization within time t is minimized by choosing as the initial three-token configuration the configuration in which the tokens are placed equidistantly on the ring. Our result strengthens a corollary of a theorem of McIver and Morgan (Inf. Process. Lett. 94(2): 79-84, 2005), which states that the expected stabilization time is minimized by the equidistant configuration.

Suggested BibTeX entry:

    author = {Stefan Kiefer and Andrzej S. Murawski and Jo\"el Ouaknine and Bj\"orn Wachter and James Worrell},
    journal = {Formal Aspects of Computing},
    number = {4},
    pages = {671--678},
    title = {Three tokens in {H}erman's algorithm},
    volume = {24},
    year = {2012}

PDF (281 kB)
See dx.doi.org ...