[FengZb14] A Nearly Optimal Upper Bound for the Self-Stabilization Time in Herman's Algorithm Feng, Y. and Zhang, L. In Concurrency Theory - 25th International Conference (CONCUR 2014), pages 342-356, Springer, LNCS 8704, 2014.
Downloads: pdf, bibURL: http://dx.doi.org/10.1007/978-3-662-44584-6_24 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.