A Space-Efficient and Self-Stabilizing Depth-First Token Circulation Protocol for Asynchronous Message-Passing Systems (Extended Abstract)

Self-Stabilization was first introduced by Dijkstra in [Dij74]. In this pioneering paper, Dijkstra defines a system self-stabilizing if, starting with an arbitrary initial state, the system is guaranteed to reach a legitimate state in a finite number of steps. The self-stabilization property is very useful for distributed systems in which transient failures may occur and recover in an arbitrary state. In [CH93], Huang and Chen present the first self-stabilizing depth-first token circulation for general networks. The space complexity of their algorithm depends on n, n is the number of processors. In [BJ95], Johnen and Beauquier have improved the [CH93] result by reducing space for each processor to the best known complexity, i.e. O(log(Δ)), Δ is the upper bound of node's degree. Both algorithms run on state model far enough from message-passing..