Home Page

Publications

Research activities

Teaching activities (French)



SS definition

SS protocols

Simulation of the k-state protocol by E.W. Dijkstra

I present the simulation of one of three self-stabilizing token circulation protocol presented by Dijkstra in its seminal paper (ref: E.W. Dijkstra: Self-stabilizing systems in spite of distributed control. Commun. ACM 17 (1974), 11: 643-644).

This protocol is the K-state protocol by E.W. Dijkstra.

This protocol works on semi-uniform unidirectional rings of any size, under any centralized scheduler (in particular no fairness assumption is required). A semi-uniform ring is an anonymous ring where all processors except one perform the sames rules.

Any processor has a single integer variable, named v, taking value in [0..K-1] where K is geater than the ring size.

Only a processor having a token is enabled. Thus, once the ring is stabilized, only one processor is enabled.

An ordinary processor is enabled (or has a token) if its v's value is not equal to the v's value of its left neighbor. The action of an ordinary processor is to set up its the v's value to the v's value of its left neighbor.

Conversely, the leader (the distinguished processor) is enabled (or has a token) if its variable's value is equal to the variable's value of its left neighbor. The action of the leader is to set up its v's value to v's value of its left neighbor more one modulo k.

The space complexity of the protocol is O(N) where N is the ring size.


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