Optimal service time
Home Page

Publications

Research activities

Teaching activities (French)



SS definition

SS protocols

Optimal service time

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).

Once stabilized, our protocol provides an optimal service: after N computation steps, each processor has obtained one time the token, where N is the ring size.

A complet description of the protocol is given in "Service Time Optimal Self-Stabilizing Token Circulation Protocol on Anonymous Unidrectional Rings", Colette Johnen, 21st Symposium on Reliable Distributed Systems (SRDS 2002), page 80-89, 2002.

Each processor has two variables (v, r). v is an integer variable taking value in [0..K-1] where K value is greater than the ring size. r is a boolean variable.

The space complexity of the protocol is O(N) where N is the ring size.


The applet code was done by 4 Master students (Gorka Anguelu, Tiago Pires Gomes, Natacha Streby, Cédric Thepaut), in 2009.