Efficient generic multi-stage self-stabilizing algorithms for trees

We define a general framework for developing efficient multi-stage self-stabilizing algorithms for trees. This is achieved by combining multiple self-stabilizing algorithms (stages) in such a way that the local stabilized values resulting from execution of one stage drive the predicates of subsequent stages. Independently each of our stages has a moves complexity of circle minus(n(2)). Contrary to what one might expect, the moves complexity of any self-stabilizing algorithm made up of k of our stages is significantly less than the expected multiplicative combined moves complexity of O(n(2k)), coming in at only O(n(k+1)). This provides an improvement of several orders of magnitude over a number of previously published self-stabilizing algorithms.