Home Page

Publications

Research activities

Teaching activities (French)




SS definition

SS protocols

Simulation of a Deterministic Self-Stabilizing Leader Election Algorithm on unidirectional rings


I present the simulation of a deterministic self-stabilizing token circulation algorithm on anonymous and unidirectional prime-size rings, under any central scheduler (in particular no fairness assumption is required). There is no deterministic self-stabilizing leader election algorithm, under a distributed scheduler (where several processors can take a step at the same time) because it is impossible to break symmetry. The same is true if the ring size is composite.

Processors have 10N states - N being the ring size, matching the known lower bound for this model to within a small constant factor.

A complet description of the protocol is given in "Space Optimal, Deterministic, Self-Stabilizing, Leader Election Algorithm for Unidirectional Rings", Faith E. Fich, Colette Johnen. DISC'01, LNCS 2180, pages 224-239, 2001. The known lower bound is given in "Memory space requirements for self-stabilizing leader election protocols", Joffroy Beauquier, Maria Gradinariu, Colette Johnen, PODC'99, Eighteenth ACM Symposium on Principles of Distributed Computing, pages 199-208, 1999.

The state of a processor consists of three components: (bv, tag, value). bv is a boolean variable taking value in {0, 1}, tag takes value in the set {B,C,D,c,d} and a value is an integer in the interval [1,N]. A processor is leader if its tag is "B", "C", or "D".

A processor can perform an action if and only if its boolean value its equal to the boolean value of its left neighbour. Except initially, between every two steps of each processor, there is at least one step of each of its neighbours.

When a processor has tag "B", its value counts the number of steps (of the processor) for which it has been a leader, up to a maximum of N Thus, such a process can be viewed as a beginner, that is, a leader which has just recently become a leader. After a leader has performed N steps with tag "B", it will get tag "D". However, it needs to get an appropriate value (ideally, the distance from the closest leader to its left) which it cannot get from its left neighbour when its left neighbour has tag "c". Thus the processor waits in "(B,N)" until it takes one additional step.

When the system is in a configuration with no leaders, it is necessary to create one. A nonleader whose left neighbour is in state "(d, N-1)" can detect this possibility and becomes a new leader.

When the tag of a leader p is "B" or "D", this signals the nonleaders to its right (up to the next leader) to compute their distance from p. These non leaders set their tags to "d". The right neighbour of p sets its value to 1 and the others each set their value to one more than their left neighbour's value.

When the tag of a leader p is "C", it is a signal to the nonleaders with tag "d" to p's right to convey p's value to the next leader. Each of these nonleaders changes their tag from "d" to "c" and their value to be the same as the value of their left neighbour

Except initially, the value of a processor q with tag "C" or "D" is a lower bound on the distance from the closest leader p to the left of q. If a processor p with tag "C" or "D" has value N, it indicates that "P" is the only leader. In this case, p remains in state "(D,N)". If it has value less than N, then while it remains a leader, p keeps changing its tag between "C" and "D".

When the system is in a configuration with multiple leaders, some of these leaders have to be destroyed. Suppose p, q, and r are successive leaders. Processor r can learn about the distance between p and q from the value of its left neighbour r_L when r_L has tag "c", "C", or "D". If this value is larger than the value of r (which is supposed to be the distance from q to r) or r_L = q, then r gives up its leadership.