Optimal memory space and bounded service time
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 optimality of the protocol is proven in "Memory space requirements for self-stabilizing leader election protocols", Joffroy Beauquier, Maria Gradinariu, Colette Johnen. in Proc. of the 18th ACM Symposium on Principles of Distributed Computing (PODC'99), pages 199-208, 1999.

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.
color variable takes value in [0..2].


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