SELF-STABILIZING DEPTH-1ST TOKEN CIRCULATION ON NETWORKS

This paper proposes a self-stabilizing protocol which circulates a token on a connected network in nondeterministic depth-first-search order, rooted at a special node. Starting with any initial state in which the network may have no token at all or more than one token, the protocol eventually makes the system stabilize in states having exactly one circulating token. With a slight modification to the protocol - by removing nondeterminism in the search - a depth-first-search tree on the network can be constructed. The proposed protocol runs on systems that allow parallel operations.