SELF-STABILIZING TOKEN CIRCULATION ON ANONYMOUS MESSAGE PASSING RINGS
Date
1998-12-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science