Self-Stabilizing Master-Slave Token Circulation and Efficient Topology Computation in a Tree of Arbitrary Size

Self-stabilizing algorithms represent an extension of distributed algorithms in which nodes of the network have neither coordination, synchronization, nor initialization. We consider the model introduced by Lee et al. where there is one designated master node and all other nodes are anonymous and as simple as possible. We provide here a master-slave algorithm that achieves token circulation in a tree, and using that, enables the master node to compute the topology of the tree. We show that the complexity of the algorithm is at most 2n rounds O(n²) steps, and the space complexity at the slave nodes is almost constant in the sense that storage needed collectively at all n slave nodes is 2n bits.