In: Mavronicolas, M.; Tsigas, Ph.: Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany, pages 260-274. Springer, September 1997.
Abstract: We present a deterministic distributed depth-first token passing protocol on a rooted network. This protocol does not use either the processor identifiers or the size of the network, but assumes the existence of a distinguished processor, called the root of the network. The protocol is self-stabilizing, meaning that starting from an arbitrary state (in response to an arbitrary perturbation modifying the memory state), it is guaranteed to reach a state with no more than one token in the network. The protocol implements a strictly fair token circulation - during a round, every processor obtains the token exactly once. The proposed protocol has extremely small memory requirement - only O(1) bits of memory per incident network link.
Keywords: Mutual exclusion, self-stabilization, spanning tree, token passing.