On stabilization in Herman's algorithm

DOI10.1007/978-3-642-22012-8_37MaRDI QIDQ3012941zbMATH OpenOpenAlexFDO

Authors Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, James Worrell, Lijun Zhang

Publication date 7 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.3100

Mathematics Subject Classification ID

Network protocols (68M12) Distributed systems (68M14) Distributed algorithms (68W15) Randomized algorithms (68W20)

Abstract: 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.

Recommendations

• Proving the Herman-protocol conjecture
• Bounds on Herman's algorithm
• Three tokens in Herman's algorithm
• On the expected time for Herman's probabilistic self-stabilizing algorithm
• An elementary proof that Herman's ring is \(\Theta (N^{2})\)

Cites work

• An elementary proof that Herman's ring is \(\Theta (N^{2})\)
• Coupling and self-stabilization
• Diffusion-reaction in one dimension
• scientific article; zbMATH DE number 3240796 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Interacting particle systems. With a new postface.
• On stabilization in Herman's algorithm
• On the expected time for Herman's probabilistic self-stabilizing algorithm
• Probabilistic self-stabilization
• Random walks, Brownian motion, and interacting particle systems. A Festschrift in honor of Frank Spitzer
• Self-stabilization
• Self-stabilizing systems in spite of distributed control
• Stabilizing time-adaptive protocols

Cited in

(12)

• An elementary proof that Herman's ring is \(\Theta (N^{2})\)
• Remarks on automatic algorithm stabilization
• Probabilistic verification of Herman's self-stabilisation algorithm
• Three tokens in Herman's algorithm
• A tighter bound for the self-stabilization time in Herman's algorithm
• On stabilization in Herman's algorithm
• Bounds on Herman's algorithm
• scientific article; zbMATH DE number 1182786 (Why is no real title available?)
• Proving the Herman-protocol conjecture
• Computing and Combinatorics
• A nearly optimal upper bound for the self-stabilization time in Herman's algorithm
• Analysis of toggle protocols

Describes a project that uses

Uses Software

• PRISM

This page was built for publication: On stabilization in Herman's algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012941)