Home Page

Publications

Research activities

Teaching activities (French)



SS definition

SS protocols

Simulation of a Randomized Self-Stabilizing Token Circulation Protocol on rings

I present the simulation of a randomized self-stabilizing token circulation protocol for anonymous and unidirectional rings of any size, under any scheduler (in particular no fairness assumption is required).

This protocol is space optimal. The space complexity is O(m_N). m_N is the smallest integer that does not divide the ring size: N. 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 and the optimality of the protocol is proven in ( Randomized Self-Stabilizing and Space optimal Leader election under arbitrary scheduler on rings, Joffroy Beauquier, Maria Gardinariu, Colette Johnen. research report no. 1225, L.R.I., September, 1999)

In BCD95, Beauquier, Cordier and Delaët have presented a randomized self-stabilizing token circulation protocol, Pr, on anonymous and unidirectional rings having the following properties:
1. There is always at least one probabilistic token in any configuration.
2. When a processor having a processor token performs an action, either it passes its probabilistic token to its successor or it keeps its (according to the output of a random variable).
3. When a probabilistic token catches up with another probabilistic token, one of them disappears.

If the daemon is k-bounded (when a processor holds a probabilistic token, another processor can performed at most k actions), this protocol converges toward configurations where a single token fairly circulates in the ring.

Our protocol TC modifies the actions of Pr in such a way that holding a deterministic token is necessary to perform the action of Pr. After the action of Pr, the processor has passed the deterministic token to its neighbor. If a processor holds a deterministic token and it does not satisfy any guard of Pr it must pass its deterministic token when it is chosen by the daemon. When a processor passes a deterministic token, if it can perform the action of Pr, it performs this action. The deterministic token circulations verifies the following properties:
1. There is always at least one deterministic token in a configuration.
2. a processor has a deterministic token if and only if the processor is enabled (on the processor, an action guard is satisfied).
3. When a processor performs an action, it passes its token to its successor.
4. When a deterministic token catches up with another token, one of them disappears.

Along any computation, the difference between the number of p's actions with the number of q's actions is bounded by the number of deterministic tokens between p and q (this number is bounded by the distance between p and q). Thus, this difference is bounded by N. All computations of TC even under an unfair daemon are N-bounded in regard to the Pr protocol. Thus TC is a randomized self-stabilizing token circulation protocol under any deamon (without any assumption on the daemon fairness).

Each processor has two variables: (dt, pt). Each variable takes values in [0, m_N]. dt (resp. pt) is used to encode the deterministic token (resp. probabilistic token). A processor has a deterministic token (resp. probabilistic token) 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.