A nearly optimal upper bound for the self-stabilization time in Herman's algorithm

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8704 LNCS pp. 342 - 356
Issue Date:
Full metadata record
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 self-stabilization 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.167N2, a sharp improvement compared with the best known bound 0.521N2. 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 of it. © 2014 Springer-Verlag.
Please use this identifier to cite or link to this item: