Please use this identifier to cite or link to this item:
|Title:||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.|
|Appears in Collections:||Higham, Lisa|
Files in This Item:
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.