Efficiency and Simplicity in Self-Stabilizing Distributed Depth-First Token Circulation Algorithms (Extended Abstract)

The self-stabilizing distributed depth-ørst token circulation algorithms have many applications in distributed systems. The solution to this problem can be used to solve the mutual exclusion, spanning tree construction, synchronization, and many others. In this thesis, we propose several depth-ørst token circulation algorithms for trees and arbitrary networks. The algorithms do not use the processor identities, except the root. We used either the state model [Dij74] or the message-passing model. In the state model, each processor can read its own state and the states of its neighbors. In this model, a conøguration (referred to as istatesj from now onwards) of the distributed system is expressed as a n-tuple of the processor states, where n is the number of processors in the network. The minimal number of states that each processor is required to have to circulate a token has been extensively studied for the linear chain or ring networks. In his pioneering paper, Dijkstra [..