Acyclic Strategy for Silent Self-Stabilization in Spanning Forests

Karine Altisen (1) , Stéphane Devismes (1) , Anaïs Durand (2)

1 VERIMAG - IMAG - VERIMAG
2 WIDE - the World Is Distributed Exploring the tension between scale and coordination

We formalize design patterns, commonly used in self-stabilization, to obtain general statements regarding both correctness and time complexity. Precisely, we study a class of algorithms devoted to networks endowed with a sense of direction describing a spanning forest 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 polynomial in moves and asymptotically optimal in rounds. To illustrate the versatility of our method, we review several works where our results apply.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Karine Altisen, Stéphane Devismes, Anaïs Durand. Acyclic Strategy for Silent Self-Stabilization in Spanning Forests. SSS 2018 - 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Nov 2018, Tokyo, Japan. pp.186-202, ⟨10.1007/978-3-030-03232-6_13⟩. ⟨hal-01938671⟩