SELF-STABILIZING DEPTH-FIRST TOKEN CIRCULATION IN ASYNCHRONOUS MESSAGE-PASSING SYSTEMS

Abstract

Self-stabilization was first introduced by Dijkstra. A self-stabilizing system, regardless of the initial states of the processors and initial messages in the links, is guaranteed to converge to the intended behavior in finite time.  This is a very desirable property for systems to tolerate arbitrary transient faults. This paper proposes the first self-stabilizing depth-first token circulation algorithm for message-passing systems. The algorithm deals with the dynamic networks, i.e., the topology of the network may change during the execution of the algorithm. The size of the messages is five bits only. Once the system is stabilized, the message complexity is {O}(m D), where D and m are the upper bound of node's degree and the number of links of the network, respectively.