Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45996
Title: SELF-STABILIZING TOKEN CIRCULATION ON ANONYMOUS MESSAGE PASSING RINGS
Authors: Higham, Lisa
Myers, Steven
Keywords: Computer Science
Issue Date: 1-Dec-1998
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.
URI: http://hdl.handle.net/1880/45996
Appears in Collections:Higham, Lisa

Files in This Item:
File Description SizeFormat 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.