Acyclic Strategy for Silent Self-Stabilization in Spanning Forests
share
In this paper, we formalize design patterns, commonly used in the self-stabilizing area, to obtain general statements regarding both correctness and time complexity guarantees. Precisely, we study a general class of algorithms designed for networks endowed with a sense of direction describing a spanning forest (e.g., a directed tree or a network where a directed spanning tree is available) whose characterization is a simple (i.e., quasi-syntactic) condition. We show that any algorithm of this class is (1) silent and self-stabilizing under the distributed unfair daemon, and (2) has a stabilization time which is polynomial in moves and asymptotically optimal in rounds. To illustrate the versatility of our method, we review several existing works where our results apply.
READ FULL TEXT