We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A nearly optimal upper bound for the self-stabilization time in Herman's algorithm.
- Authors
Feng, Yuan; Zhang, Lijun
- Abstract
Self-stabilization algorithms are very important in designing fault-tolerant distributed systems. In this paper we consider Herman's self-stabilization algorithm and study its expected termination time. McIver and Morgan have conjectured the optimal upper bound being $$0.148N^2$$ , where $$N$$ denotes the number of processors. We present an elementary proof showing a bound of $$0.167N^2$$ , a sharp improvement compared with the best known bound $$0.521N^2$$ . Our proof is inspired by McIver and Morgan's approach: we find a nearly optimal closed form of the expected stabilization time for any initial configuration, and apply the Lagrange multipliers method to give an upper bound.
- Subjects
SELF-stabilization (Computer science); FAULT-tolerant computing; DISTRIBUTED computing; MATHEMATICAL bounds; LAGRANGE multiplier
- Publication
Distributed Computing, 2015, Vol 28, Issue 4, p233
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-015-0241-z