SELF-STABILIZING TOKEN CIRCULATION ON ANONYMOUS MESSAGE PASSING RINGS

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.