Home Page Publications Research activities Teaching activities (French) SS definition SS protocols |
Optimal memory space and bounded service time
Once the
system is stabilized the circulation of the sole token is 1-fair (i.e.
in every round every processor
obtains the token once).
N token circulations are done in at most N^3 computation steps where
N is the ring size.
The memory space required by our algorithm on each processor is m_N.
m_N is the smallest integer that does not divide the ring size.
It should be noticed that m_N is constant on average.
On odd size rings, 2 bits are sufficient for token circulation protocol.
A complet description of the protocol is given in
"Bounded Service Time and Memory Space Optimal Self-Stabilizing Token Circulation
Protocol on unidirectional rings", Colette Johnen.
in Proc. of the 18th International Parallel & Distributed
Processing Symposium (IPDPS'04), 2004.
The protocol is the conjunction of two protocols.
The first protocol is a self-stabilizing token circulation protocol.
A simulation of this sole protocol exists.
A processor having a token called "Probabilistic Mark" randomly
decides to keep its Mark or to pass it to its right neighbor.
This protocol allows to
distinct one processor in the ring "the processor having the Probabilistic Mark".
The distinguished
processor changes time to time when the Mark moves.
The second layer is a self-stabilizing token circulation on semi-uniform rings of any size.
The distinguished processor does not execute the same algorithm as the other processors.
A standard
processor (a processor that does not have the Probabilistic Mark) has a token when it does not
have the same color has its left neighbor.
A standard processor passes its token by taking the
color of its left neighbor. Unlike, the others processors, the distinguished processor
(the processor having the probabilistic Mark) has a token
when it does have the same color has its left neighbor : it
passes the token by changing its color.
Three colors is enough.
Each processor has three variables: (dt) (pt,color).
dt and pt take values in [0, m_N]. dt (resp. pt) is used to encode the Deterministic Mark
(resp. Probabilistic Mark).
A processor has a Deterministic Mark (resp. a Probabilistic Mark) if and only
if its value of dt (resp. pt) is not equal to the dt (resp. pt) value of the processor
at its left more one modulo m_N.
The processors enabled are the processors having a Deterministic Mark.
The applet code was done by 4 Master students (Gorka Anguelu, Tiago Pires Gomes, Natacha Streby, Cédric Thepaut), in 2009. |