## Three tokens in Herman's algorithm

*Stefan Kiefer*, *Andrzej S. Murawski*,
*Joël
Ouaknine*, *Bjorn Wachter*, and *James Worrell*
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.

*Formal Aspects of Computing* 24(4-6), 2012. 8 pages.

PDF
© 2012 Springer.

Imprint / Data Protection