TY - JOUR

T1 - An elementary proof that Herman's Ring is Θ(N2)

AU - McIver, Annabelle

AU - Morgan, Carroll

PY - 2005/4/30

Y1 - 2005/4/30

N2 - Herman's Ring [Inform. Process. Lett. 35 (1990) 63; http://www.cs.uiowa. edu/ftp/selfstab/H90.ps.gz] is an algorithm for self-stabilization of N identical processors connected uni-directionally in a synchronous ring; in its original form it has been shown to achieve stabilization, with probability one, in expected steps O(N2logN). We give an elementary proof that the original algorithm is in fact O(N2); and for the special case of three tokens initially we give an exact (quadratic) solution of 4abc/N, where a,b,c are the tokens' initial separations. Thus the algorithm overall has worst-case expected running time of Θ(N2). Although we use only simple matrix algebra in the proof, the approach was suggested by the general notions of abstraction, nondeterminism and probabilistic variants [A. McIver, C. Morgan, Refinement and Proof for Probabilistic Systems, Technical Monographs in Computer Science, Springer-Verlag, New York, 2004]. It is hoped they could also be useful for other, similar problems. We conclude with an open problem concerning the worst-case analysis.

AB - Herman's Ring [Inform. Process. Lett. 35 (1990) 63; http://www.cs.uiowa. edu/ftp/selfstab/H90.ps.gz] is an algorithm for self-stabilization of N identical processors connected uni-directionally in a synchronous ring; in its original form it has been shown to achieve stabilization, with probability one, in expected steps O(N2logN). We give an elementary proof that the original algorithm is in fact O(N2); and for the special case of three tokens initially we give an exact (quadratic) solution of 4abc/N, where a,b,c are the tokens' initial separations. Thus the algorithm overall has worst-case expected running time of Θ(N2). Although we use only simple matrix algebra in the proof, the approach was suggested by the general notions of abstraction, nondeterminism and probabilistic variants [A. McIver, C. Morgan, Refinement and Proof for Probabilistic Systems, Technical Monographs in Computer Science, Springer-Verlag, New York, 2004]. It is hoped they could also be useful for other, similar problems. We conclude with an open problem concerning the worst-case analysis.

UR - http://www.scopus.com/inward/record.url?scp=14644386774&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2004.12.013

DO - 10.1016/j.ipl.2004.12.013

M3 - Article

AN - SCOPUS:14644386774

VL - 94

SP - 79

EP - 84

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 2

ER -