Home Page Publications Research activities Teaching activities (French) SS definition SS protocols |
Optimal service timeThe 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. |