Computer Science – Data Structures and Algorithms
Scientific paper
2011-04-15
Computer Science
Data Structures and Algorithms
Technical report accompanying an ICALP'11 paper with the same title
Scientific paper
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 Theta(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.
Kiefer Stefan
Murawski Andrzej
Ouaknine Joël
Worrell James
Zhang Lijun
No associations
LandOfFree
On Stabilization in Herman's Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Stabilization in Herman's Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Stabilization in Herman's Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-9174