Self-stabilizing depth-first token circulation in asynchronous message-passing systems

Self-stabilization was first introduced by Dijkstra. A self-stabilizing sys tem, regardless of the initial states of the processors and initial message s in the links, is guaranteed to concierge to the intended behavior in fini te time. This is a very desirable property for systems to tolerate arbitrar y transient faults. This paper proposes the first self-stabilizing depth-first token circulatio n algorithim for message-passing systems. The algorithm deals with the dyna mic networks, i.e., the topology of the network may change during the execu tion of the algorithm. The size of the messages is five bits only. Once the system is stabilized, the message complexity is O(m Delta), where Delta an d m are the upper bound of node's degree and the number of links of the net work, respectively.