Optimality and Self-Stabilization in Rooted Tree Networks
Franck Petit · Parallel Processing Letters · 2000
In this paper, we consider arbitrary tree networks where every processor, except one, called the root, executes the same program. We show that, to design a depth-rst token circulation protocol in such networks, it is necessary to have at least ( 1 + 1) Q n i=2 ( i + 2) congurations, where n is the number of processors in the network and i is the degree of processor p i . We then propose a depth-rst token circulation algorithm which matches the above minimal number of congurations. We show that the proposed algorithm is selfstabilizing, i.e., the system eventually recovers itself to a legitimate state after any perturbation modifying the state of the processors. Hence, the proposed algorithm is optimal in terms of the number of congurations and no extra cost is involved in making it stabilizing. Keywords: Depth-First Token Circulation, Distributed Systems, Mutual Exclusion, Optimality, Self-Stabilization. 1. Introduction Self-Stabilization was rst introduced by Dijkstra...