Abstract
A self-stabilizing algorithm that solves the problems of token circulation
and leader election on anonymous and uniform, unidirectional, message
passing rings of arbitrary, but known, size is developed. From any inital
configuration, the expected time to stabilization on a ring of size \fIn\fR
is in \fIO\fR (\fIn\fR log \fIn\fR). Furthermore, the size of the
configuration of the system remains constant throughtout the execution; each
processor state and message state has size in \fIO\fR (log \fIn\fR). The
correctness of the algorithm relies upon a novel duality between messages and
processes.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca
