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 [5] with tree rooting algorithms that require only O(n³+n²·c_h) moves, where n is the number of nodes in the network and c_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²) 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 [7]