Home Page

Publications

Research activities

Teaching activities (French)



SS definition

SS protocols

Simulation of a Randomized Self-Stabilizing Leader election Protocol on rings

I present the simulation of a randomized self-stabilizing leader election 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 in "Randomized Self-Stabilizing and Space optimal Leader election under arbitrary scheduler on rings", Joffroy Beauquier, Maria Gradinariu, Colette Johnen, Distributed computing, vol. 20, no 1, pages 75-93, 2007
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 composed of three layers. The first layer encodes the leadership status. On this layer, each processor has one variables: ld taking values in [0, m_N]. ld encodes the leader mark: a processor is a leader (has the yellow color) if and only if its value of ld is not equal to the ld value of the processor at its left more one modulo m_N. The leader marks have the following properties:
1. There is always at least one leader mark in any configuration.
2. When a leader mark catches up with another leader mark, one of them disappears.

The two last layers provide a probabilistic colored token circulation. The second layer encodes the color of the processor: 0 to green and 1 to red. The third layer ensures the circulation of a token on the anonymous and unidirectional ring of any size, under any scheduler. Thus, only one probabilistic colored token will eventually circulate on the ring for any initial configuration and for any daemon.

The goal of the colored token is to freeze the leader mark when there is only one, but also to ensure the circulation of leader marks when the ring contains several ones.

When a processor has a deterministic, a colored token and a leader mark, it randomly selects a color. During the circulation of the probabilistic colored token, this color will be communicated to every processor of the ring. The leader waits until having again the probabilistic colored token. At that time, if the color of its left neighbor is the same as its color, then it stays leader and starts the checking again by randomly selecting a new color. In this case, it ``assumes'' that it is the only leader in the ring.

Since the color is randomly selected, when there are several leaders in the ring, a leader will eventually have the deterministic and probabilistic colored token when its left neighbor does not have the right color (i.e. its color, called "co"). In this case, the leader passes its leadership to its right neighbor. It ``assumes'' that several leaders coexist in the ring. The leader mark does several moves in the ring up to catch the next leader. More precisely, the leadership moves until it reaches a processor that does not have the "co" color (usually this processor is a leader) also a leader mark catches up another one;; therefore at least one leader mark is removed.