A SELF-STABILIZING ALGORITHM FOR CONSTRUCTING BREADTH-1ST TREES

A self-stabilizing algorithm for constructing breadth-first trees is proposed. Its self-stabilizing property is proven. A convincing and straightforward way to prove a system self-stabilizing is: First prove that the system can always make a computation step as long as the system is not stabilized, and give a bounded function whose value decreases for each computation step. But in some cases, it may be hard or even unlikely to find such a bounded function. However, by transforming the original set of rules into another set of rules so that both sets of rules have the equivalent effect, it may become easier to find such a bounded function from the transformed rules. The provided proof adopts this concept.