Karine Altisen

Stéphane Devismes

Anaïs Durand

Acyclic Strategy for Silent Self-Stabilization in Spanning Forests

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Numerous self-stabilizing algorithms have been proposed so far to solve various tasks. Those works also consider a large taxonomy of topologies: rings [START_REF] Blin | Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative[END_REF], (directed) trees [START_REF] Chaudhuri | Improved self-stabilizing algorithms for l(2, 1)-labeling tree networks[END_REF][START_REF] Turau | A distributed algorithm for minimum distance-k domination in trees[END_REF], planar graphs [START_REF] Ghosh | A self-stabilizing algorithm for coloring planar graphs[END_REF], arbitrary connected graphs [START_REF] Altisen | Self-stabilizing leader election in polynomial steps[END_REF], etc. Among those topologies, the class of directed (in-)trees is of particular interest. Indeed, such topologies often appear, at an intermediate level, in self-stabilizing composite algorithms. Composition is a popular way to design self-stabilizing algorithms [START_REF] Tel | Introduction to distributed algorithms[END_REF] since it allows to simplify both the design and the proofs. Numerous self-stabilizing algorithms [START_REF] Arora | Composite routing protocols[END_REF][START_REF] Blin | Loop-free super-stabilizing spanning tree construction[END_REF][START_REF] Datta | Competitive self-stabilizing k-clustering[END_REF] are actually made as a composition of a spanning directed treelike (e.g., tree or forest) construction and some other algorithms specifically designed for directed tree/forest topologies. Notice that, even though not mandatory, most of these constructions additionally achieve silence [START_REF] Dolev | Memory requirements for silent stabilization[END_REF]: a silent algorithm converges within finite time to a configuration from which the values of the communication registers used by the algorithm remain fixed. Silence is a desirable property, as it usually implies more simplicity in the design, and so allows to write simpler proofs; moreover, a silent algorithm may utilize fewer communication operations and communication bandwidth. We consider here the locally shared memory model with composite atomicity, where executions proceed in atomic steps and the asynchrony is captured by the notion of daemon. The most general daemon is the distributed unfair daemon. Hence, solutions stabilizing under such an assumption are highly desirable, because they work under any other daemon assumption. The daemon assumption and time complexity are closely related. The stabilization time (the main time complexity measure to compare self-stabilizing algorithms) is usually evaluated in terms of rounds, which capture the execution time according to the speed of the slowest processes. But, another crucial issue is the number of local state updates, called moves. Indeed, the stabilization time in moves captures the amount of computations an algorithm needs to recover a correct behavior. Now, this complexity can be bounded only if the algorithm works under an unfair daemon. If an algorithm requires a stronger daemon to stabilize, e.g., a weakly fair daemon, then it is possible to construct executions whose convergence is arbitrarily long in terms of atomic steps (and so in moves), meaning that, in such executions, there are processes whose moves do not make the system progress towards the convergence. In other words, these latter processes waste computation power and so energy. Such a situation should be therefore prevented, making solutions working under the unfair daemon more desirable. There are many self-stabilizing algorithms proven under the distributed unfair daemon, e.g., [START_REF] Altisen | Self-stabilizing leader election in polynomial steps[END_REF][START_REF] Datta | An O(N )-time self-stabilizing leader election algorithm[END_REF][START_REF] Glacet | Disconnected components detection and rooted shortestpath tree maintenance in networks[END_REF]. However, analyses of the stabilization time in moves is rather unusual and this may be an important issue. Indeed, recently, several self-stabilizing algorithms which work under a distributed unfair daemon have been shown to have an exponential stabilization time in moves in the worst case, e.g., the silent leader election algorithms from [START_REF] Datta | An O(N )-time self-stabilizing leader election algorithm[END_REF] (see [START_REF] Altisen | Self-stabilizing leader election in polynomial steps[END_REF]), the Breadth-First Search (BFS) algorithm of Huang and Chen [START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF] (see [START_REF] Devismes | Silent self-stabilizing BFS tree algorithms revisited[END_REF]). Contribution. 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 for networks endowed with a sense of direction describing a spanning forest (e.g., a directed tree, or a network equipped with a spanning tree) 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. Our condition mainly uses the concept of acyclic strategy, which is based on the notions of top-down and bottom-up actions. Our first goal has been to formally define these two paradigms. We have combined this formalization together with a notion of acyclic causality between actions and a last criteria called correct-alone (n.b., only this criteria is not syntactic) to obtain the notion of acyclic strategy. We show that any algorithm following an acyclic strategy reaches a terminal configuration in a polynomial number of moves, assuming a distributed unfair daemon. Hence, if its terminal configurations satisfy the specification, the algorithm is both silent and self-stabilizing. Unfortunately, we show that this condition is not sufficient to obtain an asymptotically optimal stabilization time in rounds. So, we enforce the acyclic strategy with the property of local mutual exclusivity to have an asymptotically optimal round complexity. We also propose a simple method to make any algorithm, that follows an acyclic strategy, locally mutually exclusive. This method has no overhead in moves. Finally, to show the versatility of our approach, we review works where our results apply. Related Work. General schemes and efficiency are usually understood as orthogonal issues. For example, the general scheme proposed in [START_REF] Katz | Self-stabilizing extensions for message-passing systems[END_REF] transforms almost any algorithm working on an asynchronous message-passing identified system of arbitrary topology into its corresponding self-stabilizing version. Such a universal transformer is, by essence, inefficient in space and time complexities: its purpose is only to demonstrate the feasibility of the transformation. However, few works [START_REF] Ducourthial | Self-stabilization with r-operators[END_REF][START_REF] Delaët | Self-stabilization with r-operators revisited[END_REF][START_REF] Blin | On proof-labeling schemes versus silent self-stabilizing algorithms[END_REF] target both general self-stabilizing algorithm patterns and efficiency in rounds. In [START_REF] Ducourthial | Self-stabilization with r-operators[END_REF][START_REF] Delaët | Self-stabilization with r-operators revisited[END_REF], authors propose a method to design silent self-stabilizing algorithms for a class of fix-point problems. Their solution works in non-bidirectional networks using bounded memory per process. In [START_REF] Ducourthial | Self-stabilization with r-operators[END_REF], they consider the locally shared memory model with composite atomicity assuming a distributed unfair daemon, while in [START_REF] Delaët | Self-stabilization with r-operators revisited[END_REF], they bring their approach to asynchronous message-passing systems. In both papers, they establish a stabilization time in O(D) rounds, where D is the network diameter, that holds for the synchronous case only. Moreover, move complexity is not considered. The rest of the related work only concerns the locally shared memory model with composite atomicity assuming a distributed unfair daemon. In [START_REF] Blin | On proof-labeling schemes versus silent self-stabilizing algorithms[END_REF], labeling schemes [START_REF] Korman | Proof labeling schemes[END_REF] are used to show that every static task has a silent self-stabilizing algorithm which converges within a linear number of rounds in an arbitrary identified network, however no move complexity is given. To our knowledge, until now, only two works [START_REF] Cournier | Light enabling snap-stabilization of fundamental protocols[END_REF][START_REF] Devismes | Silent self-stabilizing scheme for spanning-tree-like constructions[END_REF] conciliate general schemes for stabilization and efficiency in both moves and rounds. In [START_REF] Cournier | Light enabling snap-stabilization of fundamental protocols[END_REF], Cournier et al propose a general scheme for snap-stabilizing wave, henceforth non-silent, algorithms in arbitrary connected and rooted networks.

Using their approach, one can obtain snap-stabilizing algorithms that execute each wave in polynomial number of rounds and moves. In [START_REF] Devismes | Silent self-stabilizing scheme for spanning-tree-like constructions[END_REF], authors propose a general scheme to compute, in a linear number of rounds, spanning directed treelike data structures on arbitrary networks. They also show polynomial upper bounds on its stabilization time in moves holding for several instantiations of their scheme. Our approach is then complementary to [START_REF] Devismes | Silent self-stabilizing scheme for spanning-tree-like constructions[END_REF]. Roadmap. In Section 2, we define the model. In Section 3, we define the acyclic strategy and propose a toy example. In Section 4, we study the move complexity of algorithms that follow an acyclic strategy.

In Section 5, we analyze our case study regarding our results. In Section 6, we consider the round complexity issue. In Section 7, we review several existing works where our method applies. We conclude in Section 8.

Preliminaries

A network is made of a set of n interconnected processes. Communications are bidirectional. Hence, the topology of the network is a simple undirected graph G = (V, E), where V is a set of processes and E is a set of edges that represents communication links, i.e., {p, q} ∈ E means that p and q can directly exchange information. In this latter case, p and q are said to be neighbors. For any process p, we denote by p.Γ the set of its neighbors. We also note ∆ the degree of G. A distributed algorithm A is a collection of n = |V | local algorithms, each one operating on a single process: A = {A(p) : p ∈ V } where each process p is equipped with a local algorithm A(p) = (V ar p , Actions p ): V ar p is the finite set of variables of p, and Actions p is the finite set of actions. Notice that A may not be uniform. We identify each variable involved in Algorithm A by the notation p.x ∈ V ar p , where x is the name of the variable and p the process that holds it. Each process p runs its local algorithm A(p) by atomically executing actions. If executed, an action of p consists of reading all variables of p and its neighbors, and then writing into a part of the writable variables of p. For any process p, each action in Actions p is written as follows: L(p) :: G(p) → S(p). L(p) is a label used to identify the action in the discussion. The guard G(p) is a Boolean predicate involving variables of p and its neighbors. The statement S(p) is a sequence of assignments on writable variables of p. A variable q.x is said to be G-read by L(p) if q.x is involved in predicate G(p) (in this case, q is either p or one of its neighbors). Let G-Read(L(p)) be the set of variables that are G-read by L(p). A variable p.x is said to be written by L(p) if p.x appears as the left operand in an assignment of S(p). Let Write(L(p)) be the set of variables written by L(p). An action can be executed by a process p only if it is enabled, i.e., its guard evaluates to true. By extension, a process is enabled when at least one of its actions is enabled. The state of a process p is a vector of valuations of its variables. A configuration of an algorithm A is a vector made of a state of each process in V . For any configuration γ, we denote by γ(p) (resp. γ(p).x) the state of process p (resp. the value of the variable x of process p) in γ.

The asynchrony of the system is modeled by the daemon. Assume that the current configuration of the system is γ. If the set of enabled processes in γ is empty, then γ is said to be terminal. Otherwise, a step of A is performed as follows: the daemon selects a non-empty subset S of enabled processes in γ, and every process p in S atomically executes the statement of one of its actions enabled in γ, leading the system to a new configuration γ . The step (of A) from γ to γ is noted γ → γ : → is the binary relation over configurations defining all possible steps of A in G. An execution of A is a maximal sequence γ 0 γ 1 ...γ i ... of configurations such that γ i-1 → γ i for all i > 0. The term "maximal" means that the execution is either infinite, or ends at a terminal configuration. We define a daemon D as a predicate over executions. An execution e is then said to be an execution under the daemon D if e satisfies D. Here, we assume that the daemon is distributed and unfair. "Distributed" means that, unless the configuration is terminal, the daemon selects at least one enabled process (maybe more) at each step. "Unfair" means that there is no fairness constraint, i.e., the daemon might never select a process unless it is the only enabled one.

We measure the time complexity using two notions: rounds and moves. A process moves in γ i → γ i+1 when it executes an action in γ i → γ i+1 . The definition of round uses the concept of neutralization:

a process v is neutralized during a step γ i → γ i+1 , if v is enabled in γ i but not in configuration γ i+1 ,
and it is not activated in the step γ i → γ i+1 . The first round of an execution e = γ 0 γ 1 ... is its minimal prefix e such that every process that is enabled in γ 0 either executes an action or is neutralized during a step of e . If e is finite, then the second round of e is the first round of the suffix γ t γ t+1 ... of e starting from the last configuration γ t of e , and so forth.

Let A be a distributed algorithm for a network G, SP a predicate over the configurations of A, and D a daemon. A is silent and self-stabilizing for SP in G under D if the following two conditions hold: (1) every execution of A under D is finite, and (2) every terminal configuration of A satisfies SP . In this case, every terminal (resp. non-terminal) configuration is said to be legitimate w.r.t. SP (resp. illegitimate w.r.t. SP ). The stabilization time in rounds (resp. moves) of a silent self-stabilizing algorithm is the maximum number of rounds (resp. moves) over every execution possible under the considered daemon to reach a terminal (legitimate) configuration.

Algorithm with Acyclic Strategy

Let A be a distributed algorithm running on some network G = (V, E). Variable Names. We assume that every process is endowed with the same set of variables and we denote by N ames the set of names of those variables, namely: N ames = {x : p ∈ V ∧ p.x ∈ V ar p }. We also assume that for every name x ∈ N ames, for all processes p and q, variables p.x and q.x have the same definition domain. The set of names is partitioned into two subsets: ConstN ames, the set of constant names, and V arN ames = N ames \ ConstN ames, the set of writable variable names. A name x is in V arN ames as soon as there exists a process p such that p.x ∈ V ar p and p.x is written by an action of its local algorithm A(p). For every c ∈ ConstN ames and every process p ∈ V , p.c is never written by any action and it has a pre-defined constant value (which may differ from one process to another, e.g., Γ, the name of the neighborhood).

We assume that A is well-formed, i.e., V arN ames is partitioned into k sets V ar 1 , ..., V ar k such that ∀p ∈ V , A(p) consists of exactly k actions A 1 (p), ..., A k (p) where Write(A i (p)) = {p.v : v ∈ V ar i }, for all i ∈ {1, ..., k}. Let A i = {A i (p) : p ∈ V }, for all i ∈ {1, ..., k}. Every A i is called a family (of actions). By definition, A 1 , ..., A k is a partition over all actions of A, henceforth called a families' partition.

Remark 1. Since A is assumed to be well-formed, there is exactly one action of A(p) where p.v is written, for every process p and every writable variable p.v (of p).

Spanning Forest. We assume that every process is endowed with constants that define a spanning forest over the graph G: we assume the constant names par and chldrn such that for every process p ∈ V , p.par and p.chldrn are preset as follows.

p.par ∈ p.Γ ∪ {⊥}: p.par is either a neighbor of p (its parent in the forest), or ⊥. In this latter case, p is called a (tree) root. Hence, the graph made of vertices V and edges {(p, p.par) : p ∈ V ∧ p.par = ⊥} is assumed to be a spanning forest of G. -p.chldrn ⊆ p.Γ: p.chldrn contains the neighbors of p which are the children of p in the forest, i.e., for every p, q ∈ V , p.par = q ⇐⇒ p ∈ q.chldrn. If p.chldrn = ∅, p is called a leaf. Notice that p.Γ\({p.par}∪p.chldrn) may not be empty. The set of p's ancestors, Anc(p), is recursively defined as follows: Anc(p) = {p} if p is a root, Anc(p) = {p} ∪ Anc(p.par) otherwise. Similarly, the set of p's descendants, Desc(p), can be recursively defined as follows: Desc(p) = {p} if p is a leaf, Desc(p) = {p} ∪ q∈p.chldrn Desc(q) otherwise. Acyclic Strategy. Let A 1 , ..., A k be the families' partition of A. A i , with i ∈ {1, ..., k}, is said to be correct-alone if for every process p and every step γ → γ such that

A i (p) is executed in γ → γ , if no variable in G-Read(A i (p)) \ Write(A i (p)) is modified in γ → γ , then A i (p) is disabled in γ . Notice that if a variable in Write(A i (p)) is modified in γ → γ , then it is necessarily modified by A i (p), by Remark 1.
Let ≺ A be a binary relation over the families of actions of A such that for i, j ∈ {1, ..., k}, A j ≺ A A i if and only if i = j and there exist two processes p and q such that q ∈ p.Γ ∪ {p} and Write(A j (p)) ∩ G-Read(A i (q)) = ∅. We conveniently represent the relation ≺ A by a directed graph GC called Graph of actions' Causality and defined as follows:

GC = ({A 1 , ..., A k }, {(A j , A i ), A j ≺ A A i }).
Intuitively, a family of actions A i is top-down if activations of its corresponding actions are only propagated down in the forest, i.e., when some process q executes action A i (q), A i (q) can only activate A i at some of its children p, if any. In this case, A i (q) writes to some variables G-read by A i (p), these latter are usually G-read to be compared to variables written by A i (p) itself. In other words, a variable G-read by A i (p) can be written by A i (q) only if q = p or q = p.par. Formally, a family of actions A i is top-down if for every process p and every q.v ∈ G-Read(A i (p)), we have q.v ∈ Write(A i (q)) ⇒ q ∈ {p, p.par}. Bottom-up families are defined similarly: a family A i is bottom-up if for every process p and every q.v ∈ G-Read(A i (p)), we have q.v ∈ Write(A i (q)) ⇒ q ∈ p.chldrn ∪ {p}.

A distributed algorithm A follows an acyclic strategy if it is well-formed, its graph of actions' causality GC is (directed) acyclic, and for every A i in its families' partition, A i is correct-alone and either bottom-up or top-down. Toy Example. We now propose a simple example of an algorithm, called T E, that follows an acyclic strategy. T E assumes a constant integer input p.in ∈ N at each process. T E computes the sum of all inputs and then spreads this result everywhere in the network. T E assumes that the network T = (V, E) is a tree with a sense of direction (given by par and chldrn) which orientates T as an in-tree rooted at process r. Apart from those constant variables, every process p has two variables: p.sub ∈ N (which is used to compute the sum of input values in the subtree of p) and p.res ∈ N (which stabilizes to the result of the computation). T E consists of two families of actions S and R. S computes variables sub and is defined as follows. For every process p, S is bottom-up and correct-alone, while R is top-down and correct-alone. Moreover, the graph of actions' causality is simply S -→ R. So, T E follows an acyclic strategy.

Move Complexity of Algorithms with Acyclic Strategy

We now exhibit a polynomial upper bound on the move complexity of any algorithm that follows an acyclic strategy. To that goal, we consider a distributed algorithm A which follows an acyclic strategy and runs on the network G = (V, E). We use the same notation as in Section 3, e.g., we let A 1 , ..., A k be the families' partition of A.

For a process p and a family of actions A i , i ∈ {1, ..., k}, we define the impacting zone of p and A i , denoted Z(p, A i ), as follows: Z(p, A i ) is the set of p's ancestors if A i is top-down, Z(p, A i ) is the set of p's descendants otherwise (i.e., A i is bottom-up). Roughly speaking, a process q belongs to Z(p, A i ) if the execution of A i (q) may cause an execution of A i (p) in the future.

Remark 2. By definition, we have

1 ≤ |Z(p, A i )| ≤ n. Moreover, if A i is top-down, then we have 1 ≤ |Z(p, A i )| ≤ H + 1 ≤ n,
where H is the height of G, i.e., the maximum among the heights trees of the forest.

We also define the quantity M (A i , p) as the level1 of p in G if A i is top-down, the height of p in G otherwise (i.e., A i is bottom-up).

Remark 3. By definition, we have 0 ≤ M (A i , p) ≤ H, where H is the height of G.

We define Others(A i , p) = {q ∈ p.Γ : ∃A j , i = j ∧ Write(A j (q)) ∩ G-Read(A i (p)) = ∅} to be the set of neighbors q of p that have actions other than A i (q) which write variables that are G-read by

A i (p). Let maxO(A i ) = max({|Others(A i , p)| : p ∈ V } ∪ {maxO(A j ) : A j ≺ A A i )})
Remark 4. By definition, we have maxO(A i ) ≤ ∆. Moreover, if ∀p ∈ V , ∀i ∈ {1, ..., k}, Others(A i , p) is empty, then ∀j ∈ {1, ..., k}, maxO(A j ) = 0. Lemma 1. Let A i be a family of actions and p be a process. For every execution e of the algorithm Proof. Let e = γ 0 ...γ x ... be any execution of

A on G, #m(e, A i , p) ≤ n • 1 + d • 1 + maxO(A i ) H(A i ) • |Z(p, A i )|,
A on G. Let K(A i , p) = M (A i , p) + (H + 1) • H(A i ).
We proceed by induction on K(A i , p). Base Case: Assume K(A i , p) = 0 for some family A i and some process p. By definition, H ≥ 0,

H(A i ) ≥ 0 and M (A i , p) ≥ 0. Hence, K(A i , p) = 0 implies that H(A i ) = 0 and M (A i , p) = 0. Since M (A i , p) = 0, Z(p, A i ) = {p}. A i is top-down or bottom-up so, for every q.v ∈ G-Read(A i (p)), q.v ∈ Write(A i (q)) ⇒ q = p. Moreover, since H(A i ) = 0, ∀j = i, A j ≺ A A i .
So, for every j = i and every q ∈ p.Γ ∪ {p}, Write(A j (p)) ∩ G-Read(A i (q)) = ∅. Hence, no action except A i (p) can modify a variable in G-Read(A i (p)). Thus, #m(e, A i , p) ≤ 1 since A i is correct-alone. Induction Hypothesis: Let K ≥ 0. Assume that for every family A j and every process q such that K(A j , q) ≤ K, we have

#m(e, A j , q) ≤ n • 1 + d • 1 + maxO(A j ) H(A j )
• |Z(q, A j )|

Induction

Step: Assume that for some family A i and some process p, K(A i , p) = K+1. If #m(e, A i , p) equals 0 or 1, then the result trivially holds. Assume now that #m(e, A i , p) > 1 and consider two consecutive executions of A i (p) in e, i.e., there exist x, y such that 0 ≤ x < y, A i (p) is executed in both γ x → γ x+1 and γ y → γ y+1 , but not in steps γ z → γ z+1 with z ∈ {x + 1, ..., y -1}. Then, since A i is correct-alone, at least one variable in G-Read(A i (p)) has to be modified by an action other than A i (p) in a step γ z → γ z+1 with z ∈ {x, ..., y -1} so that A i (p) becomes enabled again. Namely, there are j ∈ {1, ..., k} and q ∈ V such that (a) j = i or q = p, A j (q) is executed in a step γ z → γ z+1 , and Write(A j (q)) ∩ G-Read(A i (p)) = ∅. Note also that, by definition, (b) q ∈ p.Γ ∪ {p}. Finally, by definitions of top-down and bottom-up, (a), and (b), A j (q) satisfies: (1)

j = i ∧ q = p, (2) j = i ∧ q ∈ p.Γ ∩ Z(p, A i ), or (3) j = i ∧ q ∈ p.Γ.
In other words, at least one of the three following cases occurs:

(1) p executes A j (p) in step γ z → γ z+1 with j = i and Write(A

j (p)) ∩ G-Read(A i (p)) = ∅. Consequently, A j ≺ A A i and, so, H(A j ) < H(A i ). Moreover, M (A j , p)-M (A i , p) ≤ H and H(A j ) < H(A i ) imply K(A j , p) < K(A i , p) = K + 1.
Hence, by induction hypothesis, we have

#m(e, A j , p) ≤ n • 1 + d • 1 + maxO(A j ) H(A j ) • |Z(p, A j )|.
(2) There is q ∈ p.Γ ∩ Z(p, A i ) such that q executes A i (q) in step γ z → γ z+1 and Write(A i (q)) ∩ G-Read(A i (p)) = ∅. Then, M (A i , q) < M (A i , p). Since M (A i , q) < M (A i , p), K(A i , q) < K(A i , p) = K + 1 and, by induction hypothesis, we have

#m(e, A i , q) ≤ n • 1 + d • 1 + maxO(A i ) H(A i ) • |Z(q, A i )|.
(3) A neighbor q of p executes an action A j (q) in step γ z → γ z+1 , with j = i and Write(A j (q)) ∩ G-Read(A i (p)) = ∅. Consequently, A j ≺ A A i and, so, H(A j ) < H(A i ). Moreover, M (A j , q) -M (A i , p) ≤ H and H(A j ) < H(A i ) imply K(A j , q) < K(A i , p) = K + 1. Hence, by induction hypothesis, we have

#m(e, A j , q) ≤ n • 1 + d • 1 + maxO(A j ) H(A j ) • |Z(q, A j )|.
(Notice that Cases 1 and 3 can only occur when H(A i ) > 0.) We now bound the number of times each of the three above cases occur in the execution e.

Case 1: By definition, there exist at most d predecessors A j of A i in GC (i.e., such that A j ≺ A A i ). For each of them, we have

H(A j ) < H(A i ), |Z(p, A j )| ≤ n (Remark 2) and maxO(A j ) ≤ maxO(A i ).
Hence, overall, Case 1 appears at most m 1 = {A j : A j ≺ A A i } #m(e, A j , p) times and

m 1 ≤ {A j : A j ≺ A A i } n • 1 + d • 1 + maxO(A j ) H(A j ) • |Z(p, A j )| ≤ d • n H(A i ) • 1 + d • 1 + maxO(A i ) H(A i )-1
Case 2: By definition, Z(p, A i ) = {p} q∈p.Γ∩Z(p,A i ) Z(q, A i ) Hence, overall, this case appears at most m 2 = q∈p.Γ∩Z(p,A i ) #m(e, A i , q) times and

m 2 ≤ q∈p.Γ∩Z(p,A i ) n • 1 + d • 1 + maxO(A i ) H(A i ) • |Z(q, A i )| ≤ n H(A i ) • 1 + d • 1 + maxO(A i ) H(A i ) • |Z(p, A i )| -1
Case 3: q ∈ Others(A i , p) since i = j and q ∈ p.Γ. Then, for every A j ≺ A A i , we have H(A j ) < H(A i ), maxO(A j ) ≤ maxO(A i ), and Z(q, A j ) ≤ n (Remark 2). By definition, there are at most d families A j such that A j ≺ A A i . Finally, |Others(A i , p)| ≤ maxO(A i ), by definition. Hence, overall, this case appears at most m 3 = {A j : A j ≺ A A i } {q∈Others(A i ,p)} #m(e, A j , q) times and

m 3 ≤ {A j : A j ≺ A A i } {q∈Others(A i ,p)} n • 1 + d • 1 + maxO(A j ) H(A j ) • |Z(q, A j )| ≤ d • maxO(A i ) • n H(A i ) • 1 + d • 1 + maxO(A i ) H(A i )-1
Hence, overall, we have

#m(e, A i , p) ≤ 1 + m 1 + m 2 + m 3 ≤ n H(A i ) • 1 + d • 1 + maxO(A i ) H(A i ) • |Z(p, A i )| Since maxO(A i ) ≤ ∆ (Remark 4) and |Z(p, A i )| ≤ n (Remark 2)
, we can deduce the following theorem from Lemma 1 and the definition of silent self-stabilization. Theorem 1. If A follows an acyclic strategy and every terminal configuration of A satisfies SP , then (1) A is silent and self-stabilizing for SP in G under the distributed unfair daemon, and (2) its stabilization time is at most

1 + d • (1 + ∆) H • k • n H+2 moves,
where k is the number of families of A, d is the in-degree of GC, and H the height of GC.

Analysis of T E

We now analyze T E using our results. The aim is to show that: (1) correctness and move complexity of T E can be easily deduced from our general results, (2) our upper bound on stabilization time in moves is tight for this example, and (3) our definition of acyclic strategy does not preclude the design of solutions (like T E) that are inefficient in terms of rounds. We will see how to circumvent this latter negative result in Section 6. First, we already saw that T E follows an acyclic strategy and that the graph of actions' causality is simply S -→ R. Then, by induction on the tree T , we can show that every terminal configuration of T E is legitimate. Hence, by Theorem 1, we can conclude that T E is silent and self-stabilizing for computing the sum of the inputs assuming a distributed unfair daemon. Moreover, its stabilization time is at most 2 • (2 + ∆) • n 3 moves. Now, using Lemma 1, the move complexity of T E can be further refined. Let e be any execution and H be the height of T . First, note that maxO(S) = maxO(R) = 0 by Remark 4. Since S is bottom-up, |Z(p, S)| ≤ n, for every process p. Moreover, the height of S is 0 in the graph of actions' causality. Hence, by Lemma 1, we have #m(e, S, p) ≤ n, for all processes p. Thus, e contains at most n 2 moves of S. Similarly, since R is top-down, |Z(p, R)| ≤ H + 1, for every process p. Moreover, the height of R is 1 in the graph of actions' causality. Hence, by Lemma 1, we have #m(e, R, p) ≤ 2 • n • (H + 1), for all processes p. Thus, e contains at most 2 • n 2 • (H + 1) moves of R. Overall, the stabilization time of T E is actually at most n 2 (3 + 2H) moves. Lower Bound in Moves. We now show that the stabilization time of T E is Ω(H • n 2 ) moves, meaning that the previous upper bound (obtained by Lemma 1) is asymptotically reachable. To that goal, we consider a directed line of n processes, with n ≥ 4, noted p 1 , ..., p n : p 1 is the root and for every i ∈ {2, ..., n}, there is a link between p i-1 and p i , moreover, p i .par = p i-1 (note that H = n). We build a possible execution of T E running on this line that contains Ω(H • n 2 ) moves. We assume a central unfair daemon: at each step exactly one process executes an action. In this execution, we fix that p i .in = 1, for every i ∈ {1, ..., n}. We consider two classes of configurations: Configurations X 2i+1 (with 3 ≤ 2i + 1 ≤ n) and Configurations Y 2i+2 (with 4 ≤ 2i + 2 ≤ n), see Figure 1. The initial configuration of the execution is X 3 . Then, we proceed as follows: the system converges from configuration X 2i+1 to configuration Y 2i+2 in Ω(i 2 ) moves using Schedule 1 and then from Y 2i+2 to X 2i+3 in Ω(i) moves using Schedule 2, back and forth, until reaching a terminal configuration (X n if n is odd, Y n otherwise). Hence, following this scheduling of actions, the execution that starts in configuration X 3 converges to X n (resp. Y n ) if n is odd (resp. even) and contains Ω(n 3 ) moves, precisely, Ω(H • n 2 ) since the network is a line (H = n -1).

Configuration X 2i+1 , 3 ≤ 2i + 1 ≤ n: p 1 . . . p 2i-2 p 2i-1 p 2i p 2i+1 p 2i+2 p 2i+3 p 2i+4 p 2i+5 . . . in 1 . . . 1 1 1 1 1 1 1 1 . . . sub 2i . . . 3 2 1 0 2i 0 2i + 2 0 . . . res 2i . . . 2i 2i 2i 0 0 0 0 0 . . . Configuration Y 2i+2 , 4 ≤ 2i + 2 ≤ n: p 1 . . . p 2i-2 p 2i-1 p 2i p 2i+1 p 2i+2 p 2i+3 p 2i+4 p 2i+5 . . . in 1 . . . 1 1 1 1 1 1 1 1 . . . sub 4i + 1 . . . 2i + 4 2i + 3 2i + 2 2i + 1 2i 0 2i + 2 0 . . . res 4i + 1 . . . 4i + 1 4i + 1 4i + 1 4i + 1 0 0 0 0 . . .
Remark that in this execution, for every process p, when R(p) is activated, S(p) is disabled: this means that if the algorithm is modified so that S(p) has local priority over R(p) for every process p (like in the method proposed in Section 6), the proposed execution is still possible keeping a move complexity in Ω(H • n 2 ) even for such a prioritized algorithm. Schedule 1 from X 2i+1 to Y 2i+2 1: for j = 2i + 1 down to 1 do 2:

p j executes S(p j )

3:

for k = j to 2i + 1 do 4:

p k executes R(p k )
Schedule 2 from Y 2i+2 to X 2i+3 1: for j = 2i + 2 down to 1 do 2:

p j executes S(p j ) 3: for j = 1 to 2i + 1 do 4:

p j executes R(p j )
Lower Bound in Rounds. We now show that T E has a stabilization time in Ω(n) rounds in any tree of height H = 1, i.e., a star network. This negative result is due to the fact that families R and S are not locally mutually exclusive. In the next section, we will propose a transformation to obtain a stabilization time in O(H) rounds, so O(1) rounds in the case of a star network, without affecting the move complexity.

We now construct a possible execution that terminates in n+2 rounds in a star network of n processes (n ≥ 2): p 1 is the root of the tree and p 2 , ..., p n are the leaves (namely links are {{p 1 , p i }, i = 2, ..., n}). We note C i , i ∈ {1, ..., n}, the configuration satisfying the following three conditions:

(1) ∀i ∈ {1, ..., n}, p i .in = 1;

(2) p 1 .sub = i, ∀j ∈ {2, ..., i}, p j .sub = 1, and ∀j ∈ {i + 1, ..., n}, p j .sub = 0; (3) ∀i ∈ {1, ..., n}, p i .res = i.

Schedule 3 from C i to C i+1 4: for j = 2 to n do 5:

p j executes R(p j )
In every configuration C i , processes p 1 , ..., p i are disabled and processes p i+1 , ..., p n are enabled for S. We now build a possible execution that starts from C 1 and successively converges to configurations C 2 , ..., C n (C n is a terminal configuration). To converge from C i to C i+1 , i ∈ {1, ..., n -1}, the daemon applies Schedule 3. The convergence from C 1 to C n-1 last n -2 rounds since for i ∈ {1, ..., n -2}, the convergence from C i to C i+1 lasts exactly one round. Indeed, each process executes at least one action between C i and C i+1 and process p n is enabled in configuration C i and remains continuously enabled until being activated as the last process to execute in the round. The convergence from C n-1 to C n lasts 4 rounds: in C n-1 , only p n is enabled to execute S(p n ) hence the round terminates in one step where only S(p n ) is executed. Similarly, p 1 then sequentially executes S(p 1 ) and R(p 1 ) in two rounds. Finally, p 2 , ..., p n execute R in one round and then the system is in the terminal configuration C n . Hence the execution lasts n + 2 rounds.

Round Complexity of Algorithms with Acyclic Strategy

We now propose an extra condition that is sufficient for any algorithm following an acyclic strategy to stabilize in O(H) rounds. We then propose a simple method to add this property to any algorithm that follows an acyclic strategy, without affecting the move complexity. Throughout this section, we consider a distributed well-formed algorithm A designed for a network G endowed with a spanning forest. Let A 1 , ..., A k be the families' partition of A. A Condition for a Stabilization Time in O(H) rounds. We say that families A i and A j are locally mutually exclusive if for every process p, there is no configuration γ where both A i (p) and A j (p) are enabled. By extension, we say A is locally mutually exclusive if ∀i, j ∈ {1, ..., k}, i = j implies that A i and A j are locally mutually exclusive. Below, note that H < k and, in usual cases, the number of families k is a constant. Theorem 2. If A follows an acyclic strategy and is locally mutually exclusive, then every execution of A reaches a terminal configuration within at most (H + 1) • (H + 1) rounds, where H is the height of the graph of actions' causality of A and H is the height of the spanning forest. Proof Outline. Let A i be a family of actions of A and p be a process. We note R(A i , p) = H(A i ) • (H + 1) + M (A i , p) + 1. We first show, by induction, that for every family A i and every process p, after R(A i , p) rounds, A i (p) is disabled forever. Then, since for every family A i and every process p, H(A i ) ≤ H and M (A i , p) ≤ H, we have R(A i , p) ≤ (H + 1) • (H + 1), and the theorem holds.

A Transformer. We know that there exist algorithms that follow an acyclic strategy, are not locally mutually exclusive, and stabilize in Ω(n) rounds (see Section 5). We now formalize a method, based on priorities over actions, to transform such algorithms into locally mutually exclusive ones. This ensures a complexity in O(H) rounds, without degrading the move complexity.

In the following, for every process p and every family A i , we identify the guard and the statement of Action A i (p) by G i (p) and S i (p), respectively. Let A be any strict total order on families of A compatible with ≺ A , i.e., A is a binary relation on families of A that satisfies: Strict Order: A is irreflexive and transitive; Total: for every two families A i , A j , we have either A i A A j , A j A A i , or i = j; and Compatibility: for every two families A i , A j , if A i ≺ A A j , then A i A A j . Let T(A) be the following algorithm:

(1) T(A) and A have the same set of variables.

(2) Every process p ∈ V holds k actions (recall that k is the number of families of A): for every i ∈ {1, ..., k}, A T i (p) ::

G T i (p) → S T i (p) where G T i (p) = A j A A i ¬G j (p) ∧ G i (p) and S T i (p) = S i (p). G i (p) (resp. the set {G j (p) : A j A A i }) is called the positive part (resp. negative part) of G T i (p)
. By definition, ≺ A is irreflexive and the graph of actions' causality induced by ≺ A is acyclic. So, there always exists a strict total order compatible with ≺ A , i.e., the above transformation is always possible for any algorithm A which follows an acyclic strategy. Moreover, by construction, we have the two following remarks:

Remark 5. (1) T(A) is well-formed, (2) A T 1 , ..., A T k is the families' partition of T(A), where A T i = {A T i (p) : p ∈ V },
for every i ∈ {1, ..., k}, and (3) T(A) is locally mutually exclusive. Remark 6. For every i, j ∈ {1, ..., k} such that i = j, and every process p, the positive part of G T j (p) belongs to the negative part in G T i (p) if and only if A j A A i . Lemma 2. For every i, j ∈ {1, ..., k}, if A T j ≺ T(A) A T i , then A j A A i . Proof. Let A T i and A T j be two families such that A T j ≺ T(A) A T i . Then, i = j and there exist two processes p and q such that q ∈ p.Γ ∪ {p} and Write(A T j (p)) ∩ G-Read(A T i (q)) = ∅. Then, Write(A T j (p)) = Write(A j (p)), and either Write(A j (p)) ∩ G-Read(A i (q)) = ∅, or Write(A j (p)) ∩ G-Read(A (q)) = ∅ where G (q) belongs to the negative part of G T i (q). In the former case, we have A j ≺ A A i , which implies that A j A A i ( A is compatible with ≺ A ). In the latter case, A j ≺ A A (by definition) and A A A i (by Remark 6). Since, A j ≺ A A implies A j A A ( A is compatible with ≺ A ), by transitivity we have A j A A i . Hence, for every i, j ∈ {1, ..., k}, A T j ≺ T(A) A T i implies A j A A i , and we are done.

Lemma 3. T(A) follows an acyclic strategy.

Proof. Let A T i be a family of T(A). The lemma is proven by the following three claims. (1) A T i is correct-alone. Indeed, as A i is correct-alone and for every process p, S T i (p) = S i (p) and ¬G i (p) ⇒ ¬G T i (p), we have that A T i is also correct-alone. (2) A T i is either bottom-up or top-down. Since A follows an acyclic strategy, A i is either bottomup or top-down. Assume A i is bottom-up. By construction, for every process q, S T i (q) = S i (q) so Write(A T i (q)) = Write(A i (q)). Let q.v ∈ G-Read(A T i (p)). -Assume q.v ∈ G-Read(A i (p)). Then q.v ∈ Write(A i (q)) ⇒ q ∈ p.chldrn ∪ {p} (since A i is bottom-up), i.e., q.v ∈ Write(A T i (q)) ⇒ q ∈ p.chldrn ∪ {p}.

for q ∈ p.chldrn; (4) dist l (p) depends on q.L and q.cds for q ∈ p.chldrn, and p.par.dist l ; finally (5) minc(p) depends on p.level, q.cds and q.minc for q ∈ p.chldrn. So, A 1 , A 3 , A 5 are bottom-up and correct-alone and A 2 , A 4 are top-down and correct-alone. The graph of actions' causality is acyclic since A 1 ≺ A 3 , A 1 ≺ A 4 , A 2 ≺ A 5 , A 3 ≺ A 4 , and A 3 ≺ A 5 ; and its height is H = 2. Thus, as in [START_REF] Turau | A distributed algorithm for minimum distance-k domination in trees[END_REF], we have a round complexity in O(H). Moreover, by Theorem 1, the move complexity is in O(∆ 2 .n 4 ), where ∆ is the degree of the tree. The silent algorithm given in [START_REF] Karaata | A self-stabilizing algorithm for finding articulation points[END_REF] finds articulation points in a network endowed with a breadth-first spanning tree, assuming a central unfair daemon. The algorithm computes for each node p the variable p.e which contains every non-tree edges incident on p and some non-tree edges incident on descendants of p once a terminal configuration is reached. Precisely, a non-tree edge {p, q} is propagated up in the tree starting from p and q until the first common ancestor of p and q. Based on p.e, the node p can decide whether or not it is an articulation point. The algorithm can be translated as a single family of actions which is correct-alone and bottom-up. So, it follows that this algorithm is silent and self-stabilizing even assuming a distributed unfair daemon. Moreover, its stabilization time is in O(n 2 ) moves and O(H) rounds.

The algorithm in [START_REF] Devismes | A silent self-stabilizing algorithm for finding cut-nodes and bridges[END_REF] computes cut-nodes and bridges on connected graph endowed with a depthfirst spanning tree. It is silent and self-stabilizing under a distributed unfair distributed daemon and converges within O(n 2 ) moves and O(H) rounds. Indeed, the algorithm contains a single family of actions which is correct-alone and bottom-up.

Conclusion

We have presented a general scheme to prove and analyze silent self-stabilizing algorithms executing on networks endowed with a sense of direction describing a spanning forest. Our results allow to easily (i.e. quasi-syntactically) deduce correctness and upper bounds on both move and round complexities of such algorithms. We have identified a number of algorithms [START_REF] Turau | A distributed algorithm for minimum distance-k domination in trees[END_REF][START_REF] Chaudhuri | Self-stabilizing tree ranking[END_REF][START_REF] Chaudhuri | Improved self-stabilizing algorithms for l(2, 1)-labeling tree networks[END_REF][START_REF] Chaudhuri | An O(n 2 ) Self-Stabilizing Algorithm for Computing Bridge-Connected Components[END_REF][START_REF] Chaudhuri | A note on self-stabilizing articulation point detection[END_REF][START_REF] Karaata | A self-stabilizing algorithm for finding articulation points[END_REF][START_REF] Devismes | A silent self-stabilizing algorithm for finding cut-nodes and bridges[END_REF] where our method applies. In several of those works, the assumption about the existence of a directed spanning tree has to be considered as an intermediate assumption, since this structure has to be built by an underlying algorithm. Now, several silent self-stabilizing spanning tree constructions are efficient in both rounds and moves, e.g., [START_REF] Devismes | Silent self-stabilizing scheme for spanning-tree-like constructions[END_REF]. Thus, both algorithms, i.e., the one that builds the tree and the one that computes on this tree, have to be carefully composed to obtain a general composite algorithm where the stabilization time is kept both asymptotically optimal in rounds and polynomial in moves.

S

  (p) :: p.sub = ( q∈p.chldrn q.sub) + p.in → p.sub ← ( q∈p.chldrn q.sub) + p.in R computes variables res and is defined as follows. R(r) :: r.res = r.sub → r.res ← r.sub For every process p = r, R(p) :: p.res = max(p.par.res, p.sub) → p.res ← max(p.par.res, p.sub)

Figure 1 :

 1 Figure 1: Configurations X 2i+1 and Y 2i+2

  where #m(e, A i , p) is the number of times p executes A i (p) in e, d is the in-degree of GC, and H(A i ) is the height of A i in GC.2

  1: p i+1 executes S(p i+1 ) 2: p 1 executes S(p 1 ) 3: p 1 executes R(p 1 )

The level of p in G is the distance from p to the root of its tree in G (0 if p is the root itself).

The height of Ai in GC is 0 if the in-degree of Ai in GC is 0. Otherwise, it is equal to one plus the maximum of the heights of the Ai's predecessors w.r.t. ≺A.

This study has been partially supported by the ANR projects DESCARTES (ANR-16-CE40-0023) and ESTATE (ANR-16-CE25-0009), and by the Franco-German DFG-ANR project 40300781 DISCMAT.

-Assume that q.v / ∈ G-Read(A i (p)). Then q.v ∈ G-Read(A j (p)) such that G j (p) belongs to the negative part of G T i (p), i.e., A j A A i (Remark 6). Assume, by the contradiction, that q.v ∈ Write(A T i (q)). Then q.v ∈ Write(A i (q)), and since p ∈ q.Γ∪{q} (indeed, q.v ∈ G-Read(A j (p))), we have A i ≺ A A j . Now, as A is compatible with ≺ A , we have A i A A j . Hence, A j A A i and A i A A j , a contradiction. Thus, q.v / ∈ Write(A T i (q)) which implies that q.v ∈ Write(A T i (q)) ⇒ q ∈ p.chldrn ∪ {p} holds in this case. Hence, A T i is bottom-up. By a similar reasoning, if A i is top-down, A T i is top-down too. (3) The graph of actions' causality of T(A) is acyclic. Indeed, by Lemma 2, for every i, j ∈ {1, ..., k}, A T j ≺ T(A) A T i ⇒ A j A A i . Now, A is a strict total order. So, the graph of actions' causality of T(A) is acyclic.

Lemma 4. Every execution of T(A) is an execution of A.

Proof.

A and T(A) have the same set of configurations; every step of T(A) is a step of A; and a configuration γ is terminal w.r.t. T(A) iff γ is terminal w.r.t. A. Theorem 3. If A follows an acyclic strategy, and is silent and self-stabilizing for SP in G under the distributed unfair daemon, then

(1) T(A) is silent and self-stabilizing for SP in G under the distributed unfair daemon, (2) its stabilization time is at most (H + 1) • (H + 1) rounds, and (3) its stabilization time in moves is less than or equal to the one of A. where H is the height of the graph of actions' causality of A and H is the height of the spanning forest.

Proof. By Remark 5, Lemmas 3 and 4, and Theorems 1 and 2.

Using the above theorem, we can apply the transformer on our toy example: T(T E) stabilizes in at most 2(H + 1) rounds and Θ(H • n 2 ) moves in the worst case.

Related Work and Applications

There are many works [START_REF] Turau | A distributed algorithm for minimum distance-k domination in trees[END_REF][START_REF] Chaudhuri | Self-stabilizing tree ranking[END_REF][START_REF] Chaudhuri | Improved self-stabilizing algorithms for l(2, 1)-labeling tree networks[END_REF][START_REF] Chaudhuri | An O(n 2 ) Self-Stabilizing Algorithm for Computing Bridge-Connected Components[END_REF][START_REF] Chaudhuri | A note on self-stabilizing articulation point detection[END_REF][START_REF] Karaata | A self-stabilizing algorithm for finding articulation points[END_REF][START_REF] Devismes | A silent self-stabilizing algorithm for finding cut-nodes and bridges[END_REF] where we can apply our generic results. These works propose silent self-stabilizing algorithms for directed trees or network where a directed spanning tree is available. These algorithms are, or can be easily translated into, well-formed algorithms that follow an acyclic strategy. Hence, their correctness and time complexities (in moves and rounds) are directly deduced from our results. Below, we only present a few of them.

Turau and Köhler [START_REF] Turau | A distributed algorithm for minimum distance-k domination in trees[END_REF] proposes three algorithms for directed trees. Each algorithm is given with its proof of correctness and round complexity, however move complexity is not considered. These three algorithms can be trivially translated in our model, and our results allow to obtain the same round complexities, and additionally provide move complexities. Among those three algorithms, the third one is the most interesting since it uses 5 families of actions, while the two first use 1 and 2 families respectively. So, we only detail this latter. The algorithm computes a minimum connected distance-k dominating set using the five families below: We do not explain here the role of the variables nor their computation using macros, please refer to the original paper [START_REF] Turau | A distributed algorithm for minimum distance-k domination in trees[END_REF]. But from their definition in [START_REF] Turau | A distributed algorithm for minimum distance-k domination in trees[END_REF], we can observe that: (1) L(p) depends on q.L for q ∈ p.chldrn; (2) level(p) depends on p.par.level; (3) cds (p) that depend on p.L and q.cds