Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434113 | Theoretical Computer Science | 2014 | 7 Pages |
Abstract
Herman's self-stabilization algorithm allows a ring of N processors having any odd number of tokens to reach a stable state where exactly one token remains. McIver and Morgan conjecture that the expected time taken for stabilization is maximized when there are three equally-spaced tokens. We prove exact results on a related cost function, and obtain a bound on expected time which is very close to the conjectured bound.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
John Haslegrave,