




Publications  Three tokens in Herman's algorithm





Reference:
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.
Abstract:
Herman's algorithm is a synchronous randomized protocol for achieving selfstabilization 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 threetoken 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): 7984, 2005), which states that the expected stabilization time is minimized by the equidistant configuration.
Suggested BibTeX entry:
@article{12KMOWW:FAC,
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 = {671678},
title = {Three tokens in {H}erman's algorithm},
volume = {24},
year = {2012}
}




