## On stabilization in Herman's algorithm

*Stefan Kiefer*, *Andrzej S. Murawski*,
*Joël
Ouaknine*, *James Worrell*, and *Lijun Zhang*
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 Θ(*N*^{2}). Our first
contribution is to give an upper bound of 0.64*N*^{2} 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*(*N*^{2}) 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.

*Proceedings of ICALP 11*, LNCS 6756, 2011. 27 pages.

PDF
© 2011
Springer-Verlag.

Imprint / Data Protection