Introduction.

Rightnow this directory is under construction.

Please be patient with us.

Self-Stabilization in spite of Distributed Control.

The idea of self-stabilization in distributed computing first appeared in a classic paper by E.W. Dijkstra in 1974. In this short paper in Communications of ACM, he proposed the idea of stabilization of a distributed system from some illegitimate global state to some legitimate state. The idea was that the system should be able to converge to a legitimate state with in a bounded amount of time by itself with out any outside intervention. In this paper he showed an example of a self-stabilizing token ring system. The global states of the token ring at which there are multiple tokens or there is no token are defined to be illegitimate states. He gave three self-stabilizing protocols, one with K states where K is greater or equal to the number of processors in the ring. The other two with 3 and 4 states respectively. There has been considerable amount of interest on analyzing these protocols and proving the correctness of these protocols. Also people have worked on explaining these protocols from a more generic frame work. (e.g,see "Dijkstra's protocol as example of local checking and counter flushing" or see Self-Stabilization by Counter Flushing"(PODC'94) both by George Varghese.)