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

摘要

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.