A Tighter Bound for the Self-Stabilization Time in Herman's Algorithm
In Information Processing Letters
, 113: 486-488, 2013.
Downloads: pdf, bibURL: http://dx.doi.org/10.1016/j.ipl.2013.04.006
Abstract. We study the expected self-stabilization time of the Herman's algorithm. For N processors the lower bound is frac427N^2 (0.148N^2), and an upper bound of 0.64N^2 is presented in . In this paper we give a tighter upper bound 0.521N^2.