Color optimal self-stabilizing depth-first token circulation

The notion of self-stabilization was first introduced by Dijkstra: it is the property for a system to eventually recover itself a legitimate state after any perturbation modifying the memory state. This paper proposes a self-stabilizing depth-first token circulation protocol for uniform rooted networks. Such an algorithm is very convenient to obtain the mutual exclusion or to construct a spanning tree. Our contribution consists of explaining how the basic depth-first token circulation protocol is nearly self-stabilizing and how to obtain a self-stabilizing protocol by just adding what is necessary to destroy cycles. We achieve an efficient algorithm working for any dynamic connected network in which the topology may change during the execution. Moreover, we shed a new light on proving self-stabilizing algorithms based on the locking property: a processor is locked if it eventually stops to modify its variables. We also improve the best known space complexity for this problem to the same as the basic algorithm, i.e. [log,(Δ+1)1]+1 bits, Δ is the upper bound of node´s degree