Self-Stabilizing Labeling and Ranking in Ordered Trees?

lastname Abstract. We propose two self-stabilizing algorithms for tree networks. The first one computes a special label, called guide pair of each process P in O(h) rounds (h being the height of the tree) using O(δP log n) space per process P, where δP is the degree of P and n the number of processes in the network. Guide pairs have numerous applications, including ordered traversal or navigation of the processes in the tree. Our second self-stabilizing algorithm, which uses the guide pairs com-puted by the first algorithm, solves the ranking problem in O(n) rounds and has space complexityO(b+δP log n) in each process P, where b is the number of bits needed to store a value. The first algorithm orders the tree processes according to their topological positions. The second algorithm orders (ranks) the processes according to the values stored in them