| Abstract |
|
We present a self-stabilizing token circulation protocol on unidirectional anonymous rings. This protocol does not required processor identifiers, no distinguished processor (i.e. all processors perform the same algorithm). The protocol is a randomized self-stabilizing, meaning that starting from an arbitrary configuration (in response to an arbitrary perturbation modifying the memory state), it reaches (with probability 1) a legitimate configuration (i.e. a configuration with only one token in the network). All previous randomized self-stabilizing token circulation protocols design to work under unfair distributed schedulers have the same drawback: once stabilized, the service time is slow (in the best case, it is bounded by 2N where N is the ring size). Once stabilized, our protocol provides an optimal service: after N computation steps, each processor has obtained one time the token. The protocol can be used to implement a fair distributed mutual exclusion in any ring topology network.
|
 Additional Information
|
Index Terms- distributed protocol, fault-tolerant, mutual exclusion, self-stabilization, anonymous ring, token circulation, unfair scheduler, service time
Citation:
Colette Johnen,
"Service Time Optimal Self-Stabilizing Token Circulation Protocol on Anonymous Unidrectional Rings,"
srds,
p. 80,
21st IEEE Symposium on Reliable Distributed Systems (SRDS'02),
2002
|
