Efficient self-stabilizing algorithms for tree networks

Many proposed self-stabilizing algorithms require an exponential number of moves before stabilizing on a global solution, including some rooting algorithms for tree networks [1, 2, 3]. These results are vastly improved upon in [6] with tree rooting algorithms that require only O(n/sup 3/ + n/sup 2//spl middot/c/sub h/) moves, where n is the number of nodes in the network and c/sub h/ is the highest initial value of a variable. In the current paper, we describe a new set of tree rooting algorithms that brings the complexity down to O(n/sup 2/) moves. This not only reduces the first term by an order of magnitude, but also reduces the second term by an unbounded factor We further show a generic mapping that can be used to instantiate an efficient self-stabilizing tree algorithm from any traditional sequential tree algorithm that makes a single bottom-up pass through a rooted tree. The new generic mapping improves on the complexity of the technique presented in [8].