Karine Altisen

Alain Cournier

Stéphane Devismes

Anaïs Durand

Franck Petit

Self-Stabilizing Leader Election in Polynomial Steps *

Keywords: Distributed algorithms, fault-tolerance, self-stabilization, leader election, unfair daemon

We propose a silent self-stabilizing leader election algorithm for bidirectional connected identified networks of arbitrary topology. This algorithm is written in the locally shared memory model. It assumes the distributed unfair daemon, the most general scheduling hypothesis of the model. Our algorithm requires no global knowledge on the network (such as an upper bound on the diameter or the number of processes, for example). We show that its stabilization time is in Θ(n 3 ) steps in the worst case, where n is the number of processes. Its memory requirement is asymptotically optimal, i.e., Θ(log n) bits per processes. Its round complexity is of the same order of magnitude -i.e., Θ(n) rounds -as the best existing algorithm [10] designed with similar settings. To the best of our knowledge, this is the first self-stabilizing leader election algorithm for arbitrary identified networks that is proven to achieve a stabilization time polynomial in steps. By contrast, we show that the previous best existing algorithm designed with similar settings [10] stabilizes in a non polynomial number of steps in the worst case.

Introduction

In distributed computing, the leader election problem consists in distinguishing a single process, so-called the leader, among the others. We consider here identified networks. So, as it is usually done, we augment the problem by requiring all processes to eventually know the identifier of the leader. The leader election is fundamental as it is a basic component to solve many other important problems, e.g., consensus, spanning tree constructions, implementing broadcasting and convergecasting methods, etc.

Self-stabilization [START_REF] Edsger | Self-stabilizing Systems in Spite of Distributed Control[END_REF][START_REF] Dolev | Self-stabilization[END_REF] is a versatile technique to withstand any transient fault in a distributed system: a self-stabilizing algorithm is able to recover, i.e., reach a legitimate configuration, in finite time, regardless the arbitrary initial configuration of the system, and therefore also after the occurrence of transient faults. Thus, self-stabilization makes no hypotheses on the nature or extent of transient faults that could hit the system, and recovers from the effects of those faults in a unified manner. Such versatility comes at a price. After transient faults, there is a finite period of time, called the stabilization phase, before the system returns to a legitimate configuration. The stabilization time is then the worst case duration of the stabilization phase, i.e., the maximum time to reach a legitimate configuration starting from an arbitrary one. Notice that efficiency of self-stabilizing algorithms is mainly evaluated according to their stabilization time and memory requirement.

We consider deterministic1 asynchronous silent self-stabilizing leader election problem in bidirectional, connected, and identified networks of arbitrary topology. We investigate solutions to this problem which are written in the locally shared memory model introduced by Dijkstra [START_REF] Edsger | Self-stabilizing Systems in Spite of Distributed Control[END_REF]. In this model, the distributed unfair daemon is known as the weakest scheduling assumption. Under such an assumption, proving that a given algorithm is self-stabilizing implies that the stabilization time must be finite in terms of atomic steps. However, despite some solutions assuming all these settings (in particular the unfairness assumption) are available in the literature [START_REF] Kumar Datta | Self-stabilizing Leader Election in Dynamic Networks[END_REF][START_REF] Kumar Datta | An O(n)-time Selfstabilizing Leader Election Algorithm[END_REF][START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF], none of them is proven to achieve a polynomial upper bound in steps on its stabilization time. Actually, the time complexities of all these solutions are analyzed in terms of rounds only.

Related Work

In [START_REF] Dolev | Memory Requirements for Silent Stabilization[END_REF], Dolev et al showed that silent self-stabilizing leader election requires Ω(log n) bits per process, where n is the number of processes. Notice that non-silent selfstabilizing leader election can be achieved using less memory, e.g., the non-silent self-stabilizing leader election algorithm for unoriented ring-shaped networks given in [START_REF] Blin | Brief Announcement: Deterministic Self-stabilizing Leader Election with O(log log n)-bits[END_REF] requires O(log log n) space per process.

Self-stabilizing leader election algorithms for arbitrary connected identified networks have been proposed in the message-passing model [START_REF] Afek | Self-Stabilizing Unidirectional Network Algorithms by Power Supply[END_REF][START_REF] Awerbuch | Time Optimal Self-stabilizing Synchronization[END_REF][START_REF] Burman | Time Optimal Asynchronous Self-stabilizing Spanning Tree[END_REF]. First, the algorithm of Afek and Bremler [START_REF] Afek | Self-Stabilizing Unidirectional Network Algorithms by Power Supply[END_REF] stabilizes in O(n) rounds using Θ(log n) bits per process. But, it assumes that the link-capacity is bounded by a value B, known by all processes. Two solutions that stabilize in O(D) rounds, where D is the diameter of the network, have been proposed in [START_REF] Awerbuch | Time Optimal Self-stabilizing Synchronization[END_REF][START_REF] Burman | Time Optimal Asynchronous Self-stabilizing Spanning Tree[END_REF]. However, both solutions assume that processes know some upper bound D on the diameter D; and require Θ(log D log n) bits per process.

Several solutions are also given in the shared memory model [START_REF] Arora | Distributed Reset[END_REF][START_REF] Dolev | Superstabilizing Protocols for Dynamic Distributed Systems[END_REF][START_REF] Kumar Datta | Self-stabilizing Leader Election in Dynamic Networks[END_REF][START_REF] Kumar Datta | An O(n)-time Selfstabilizing Leader Election Algorithm[END_REF][START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF][START_REF] Kravchik | Time Optimal Synchronous Self Stabilizing Spanning Tree[END_REF]. The algorithm proposed by Dolev and Herman [START_REF] Dolev | Superstabilizing Protocols for Dynamic Distributed Systems[END_REF] is not silent, works under a fair daemon, and assume that all processes know a bound N on the number of processes. This solution stabilizes in O(D) rounds using Θ(N log N ) bits per process. The algorithm of Arora and Gouda [START_REF] Arora | Distributed Reset[END_REF] works under a weakly fair daemon and assume the knowledge of some bound N on the number of processes. This solution stabilizes in O(N ) rounds using Θ(log N ) bits per process.

Datta et al [START_REF] Kumar Datta | Self-stabilizing Leader Election in Dynamic Networks[END_REF] propose the first self-stabilizing leader election algorithm (for arbitrary connected identified networks) proven under the distributed unfair daemon. This algorithm stabilizes in O(n) rounds. However, the space complexity of this algorithm is unbounded. (More precisely, the algorithm requires each process to maintain an unbounded integer in its local memory.)

Solutions in [START_REF] Kumar Datta | An O(n)-time Selfstabilizing Leader Election Algorithm[END_REF][START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF][START_REF] Kravchik | Time Optimal Synchronous Self Stabilizing Spanning Tree[END_REF] have a memory requirement which is asymptotically optimal (i.e. in Θ(log n)). The algorithm proposed by Kravchik and Kutten [START_REF] Kravchik | Time Optimal Synchronous Self Stabilizing Spanning Tree[END_REF] assumes a synchronous daemon and the stabilization time of this latter is in O(D) rounds. The two solutions proposed by Datta et al in [START_REF] Kumar Datta | An O(n)-time Selfstabilizing Leader Election Algorithm[END_REF][START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF] assume a distributed unfair daemon and have a stabilization time in O(n) rounds. However, despite these two algorithms stabilize within a finite number of steps (indeed, they are proven assuming an unfair daemon), no step complexity analysis is proposed. Finally, note that the algorithm proposed in [START_REF] Kumar Datta | An O(n)-time Selfstabilizing Leader Election Algorithm[END_REF] assumes that each process has a bit of memory which cannot be arbitrarily corrupted.

Contribution We propose a silent self-stabilizing leader election algorithm for arbitrary connected and identified networks. Our solution is written in the locally shared memory model assuming a distributed unfair daemon, the weakest scheduling assumption. Our algorithm assumes no knowledge of any global parameter (e.g., an upper bound on D or n) of network. Like previous solutions of the literature [START_REF] Kumar Datta | An O(n)-time Selfstabilizing Leader Election Algorithm[END_REF][START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF], it is asymptotically optimal in space (i.e., it can be implemented using Θ(log n) bits per process), and it stabilizes in Θ(n) rounds in the worst case. Yet, contrary to those solutions, we show that our algorithm has a stabilization time in Θ(n 3 ) steps in the worst case.

For fair comparison, we have also studied the step complexity of the algorithm given in [START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF], noted here DLV. This latter is the closest to ours in terms of performance. We show that its stabilization time is not polynomial, i.e., there is no constant α such that the stabilization time of DLV is in O(n α ) steps. More precisely, we show that fixing α to any constant greater than or equal to 4, for every β ≥ 2, there exists a network of n = 2 α-1 × β processes in which there exists a possible execution that stabilizes in Ω(n α ) steps.

Roadmap The next section is dedicated to computational model and basic definitions. In Section 3, we propose our self-stabilizing leader election algorithm. We prove its correctness in Section 4. In the same section, we also study its stabilization time in both steps and rounds. We show that the stabilization time of the self-stabilizing leader election algorithm given in [START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF] is not polynomial in steps in Section 5. We present some experimental results in Section 6. We conclude in Section 7.

Computational model 2.1 Distributed systems

We consider distributed systems made of n processes. Each process can communicate with a subset of other processes, called its neighbors. We denote by N p the set of neighbors of process p. Communications are assumed to be bidirectional, i.e. q ∈ N p if and only if p ∈ N q . Hence, the topology of the system can be represented as a simple undirected connected graph G = (V, E), where V is the set of processes and E is a set of edges representing (direct) communication relations. We assume that each process has a unique ID, a natural integer. IDs are stored using a constant number of bits, b. As commonly done in the literature, we assume that b = Θ(log n). Moreover, by an abuse of notation, we identify a process with its ID, whenever convenient. We will also denote by ℓ the process of minimum ID. (So, the minimum ID will be also denoted by ℓ.)

Locally shared memory model

We consider the locally shared memory model in which the processes communicate using a finite number of locally shared registers, called variables. Each process can read its own variables and those of its neighbors, but can only write to its own variables. The state of a process is the vector of values of all its variables. A configuration γ of the system is the vector of states of all processes. We denote by γ(p) the state of process p in the configuration γ. We denote by C the set of all possible configurations.

A distributed algorithm consists of one program per process. The program of a process p is a finite set of actions of the following form: label :: guard → statement The labels are used to identify actions. The guard of an action in the program of process p is a Boolean expression involving the variables of p and its neighbors. If the guard of some action evaluates to true, then the action is said to be enabled at p. By extension, if at least one action is enabled at p, p is said to be enabled. We denote by Enabled(γ) the set of processes enabled in configuration γ. The statement of an action is a sequence of assignments on the variables of p. An action can be executed only if it is enabled. In this case, the execution of the action consists in executing its statement.

The asynchronism of the system is materialized by an adversary, called the daemon. In a configuration γ, if there is at least one enabled process, then the daemon selects a non empty subset S of Enabled(γ) to perform an (atomic) step: ∀p ∈ S, p atomically executes one of its actions enabled in γ, leading the system to a new configuration γ ′ . We denote by → the relation between configurations such that γ → γ ′ if and only if γ ′ can be reached from γ in one (atomic) step. An execution is then a maximal sequence of configurations γ 0 , γ 1 , . . . such that γ i-1 → γ i , ∀i > 0. The term "maximal" means that the execution is either infinite, or ends at a terminal configuration γ in which Enabled(γ) is empty.

In this paper, the daemon is supposed to be distributed and unfair. "Distributed" means that while the configuration is not terminal, the daemon should select at least one enabled process, maybe more. "Unfair" means that there is no fairness constraint, i.e., the daemon might never permit an enabled process to execute, unless it is the only enabled process.

Rounds

To measure the time complexity of an algorithm, we also use the notion of round [START_REF] Dolev | Uniform Dynamic Self-Stabilizing Leader Election[END_REF]. This latter allows to highlight the execution time according to the speed of the slowest process. If a process p is enabled in a configuration γ i but not enabled in the next configuration γ i+1 and does not execute any action between γ i and γ i+1 , we said that p is neutralized during the step γ i → γ i+1 . Neutralization of p is caused by the following situation: at least one neighbor of p changes its state between γ i and γ i+1 , and this change makes the guards of all actions of p false. The first round of an execution e, noted e ′ , is the minimal prefix of e in which every process that is enabled in the initial configuration either executes an action or becomes neutralized. Let e ′′ be the suffix of e starting from the last configuration of e ′ . The second round of e is the first round of e ′′ , and so forth.

Self-Stabilization

Let A be a distributed algorithm. Let E be the set of all possible executions of A. A specification SP is a predicate over E.

A is self-stabilizing for SP if and only if there exists a non-empty subset of configurations L ⊆ C, called legitimate configurations, such that:

• Closure: ∀e ∈ E, for each step γ i → γ i+1 ∈ e, γ i ∈ L ⇒ γ i+1 ∈ L.
• Convergence: ∀e ∈ E, ∃γ ∈ e such that γ ∈ L.

• Correction: ∀e ∈ E such that e starts in a legitimate configuration γ ∈ L, e satisfies SP . Every configuration that is not legitimate is called illegitimate. The stabilization time is the maximum time (in steps or rounds) to reach a legitimate configuration starting from any configuration.

Self-Stabilizing Leader Election

We define SP LE the specification of the leader election problem. Let Leader : V → N be a function defined on the state of any process p ∈ V in the current configuration that returns the ID of the leader appointed by p. An execution e ∈ E satisfies SP LE if and only if:

1. For all configuration γ ∈ e, ∀p, q ∈ V , Leader(p) = Leader(q) and Leader(p) is the ID of some process in V .

2. For all step γ i → γ i+1 ∈ e, ∀p ∈ V , Leader(p) has the same value in γ i and γ i+1 .

An algorithm A is silent if and only if every execution is finite [START_REF] Dolev | Memory Requirements for Silent Stabilization[END_REF]. Let γ be a terminal configuration. The set of all possible executions starting from γ is the singleton {γ}. So, if A is self-stabilizing and silent, γ must be legitimate. Thus, to prove that a leader election algorithm is both self-stabilizing and silent, it is necessary and sufficient to show that: (1) in every terminal configuration γ, ∀p, q ∈ V , Leader(p) = Leader(q) and Leader(p) is the ID of some process; (2) every execution is finite.

Algorithm LE

In this section, we present a silent and self-stabilizing leader election algorithm, called LE. Its formal code is given in Algorithm 1. Starting from an arbitrary configuration, LE converges to a terminal configuration, where the process of minimum ID, ℓ, is elected. More precisely, in the terminal configuration, every process p knows the identifier of ℓ thanks to its local variable p.idR; moreover a spanning tree rooted at ℓ is defined using two variables per process: par and level (idR means ID of the root). First, ℓ.par = ℓ and ℓ.level = 0. Then, for every process p = ℓ, p.par points to the parent of p in the tree and p.level is the level of p in the tree.

We present a simple algorithm for the leader election problem in Subsection 3.1. We show why this algorithm is not self-stabilizing in Subsection 3.2. Then, we explain in Subsection 3.3 how to modify this simple algorithm to make it self-stabilizing.

Non Self-Stabilizing Leader Election

We first consider a simplified version of LE. Starting from a predefined initial configuration, it elects ℓ in all idR variables and builds a spanning tree rooted at ℓ.

Initially, every process p declares itself as leader: p.idR = p, p.par = p, and p.level = 0. So, p satisfies the two following predicates:

Self Root(p) ≡ (p.par = p) Self RootOk ′ (p) ≡ (p.level = 0) ∧ (p.idR = p)
Note that, in the sequel, we say that p is a self root when Self Root(p) holds.

From such an initial configuration, our non self-stabilizing algorithm consists in the following single action: J-Action ′ :: ∃q ∈ N p , (q.idR < p.idR) → p.par ← min {q ∈ N p }; p.idR ← p.par.idR; p.level ← p.par.level + 1;

where ∀x, y ∈ V, x y ⇔ (x.idR ≤ y.idR) ∧ [(x.idR = y.idR) ⇒ (x < y)].

Informally, when p discovers that p.idR is not equal to the minimum identifier, it updates its variables accordingly: let q be the neighbor of p having idR minimum. Then, p selects q as 3 joins the tree rooted at 1. However, the new value of 3.idR is not yet propagated to its child 6. new parent (i.e., p.par ← q and p.level ← p.par.level + 1) and sets p.idR to the value of q.idR. If there are several neighbors having idR minimum, we break ties using the identifiers of those neighbors.

Hence, the identifier of ℓ is propagated, from neighbors to neighbors, into the idR variables and the system reaches a terminal configuration in O(D) rounds. Figure 1 shows an example of such an execution.

Notice first that for every process p, p.idR is always less than or equal to its own identifier. Indeed, p.idR is initialized to p and decreases each time p executes J-Action ′ . Hence, p.idR = p while p is a self root and after p executes J-Action ′ for the first time, p.idR is smaller than its ID forever.

Second, even in this simplified context, for each two neighbors p and q such that q is the parent of p, it may happens that p.idR is greater than q.idR -an example is shown in Figure 1c, where p = 6 and q = 3. This is due to the fact that p joins the tree of q but meanwhile q joins another tree and this change is not yet propagated to p. Similarly, when p.idR = q.idR, p.level may be different from q.level + 1. According to those remarks, we can deduce that when p.par = q with q = p, we have the following relation between p and q: GoodIdR(p, q) ≡ (p.idR ≥ q.idR) ∧ (p.idR < p) GoodLevel(p, q) ≡ (p.idR = q.idR) ⇒ (p.level = q.level + 1)

Fake IDs

This previous algorithm is not self-stabilizing. Indeed, in a self-stabilization context, the execution may start in an arbitrary configuration. In particular, idR variables can be initialized to arbitrary natural integer values, even values that are actually not IDs of (existing) processes. We call such values fake IDs. The existence of fake IDs may lead the system to an illegitimate terminal configuration. Refer to the example of execution given in Figure 2: starting from the configuration in 2a, if processes 3 and 4 move, the system reaches the terminal configuration given in 2b, where there are two trees and the idR variables elect the fake ID 1. In this example, 2 and 5 can detect the problem. Indeed, predicate Self RootOk ′ is violated by both 2 and 5. One may believe that it is sufficient to reset the local state of processes which detect inconsistency (here processes 2 and 5) to p.idR ← p, p.par ← p and p.level ← 0. After these resets, there are still some errors, as shown on Figure 3 Unfortunately, this additional action does not ensure the convergence in all cases, see the example in Figure 4. Indeed, if a process resets, it becomes a self root but this does not erase the fake ID in the rest of its subtree. Then, another process can join the tree and adopt the fake ID which will be further propagated, and so on. In the example, a process resets while another joins its tree at lower level, and this leads to endless erroneous behavior, since we do not want to assume any maximal value for level (such an assumption would otherwise imply the knowledge of some upper bound on n). Therefore, the whole tree must be reset, instead of its root only.

To that goal, we first freeze the "abnormal" tree in order to forbid any process to join it, then the tree is reset top-down. The cleaning mechanism is detailed in the next subsection. Figure 4: The first process of the chain of bold arrows violates the predicate Self RootOk ′ and resets by executing R-Action ′ , while another process joins its tree. This cycle of resets and joins might never terminate.

Cleaning Abnormal Trees

To introduce the trees, we define what is a "good relation" between a parent and its children. Namely, the predicate KinshipOk ′ (p, q) models that a process p is a real child of its parent q = p.par. This predicate holds if and only if GoodLevel(p, q) and GoodIdR(p, q) are true. This relation defines a spanning forest: a tree is a maximal set of processes connected by par pointers and satisfying KinshipOk ′ relation. A process p is a root of such a tree whenever Self Root(p) holds or KinshipOk ′ (p, p.par) is false. When Self Root(p) ∧ Self RootOk ′ (p) is true, p is a normal root just as in the non self-stabilizing case (see 3.1). In other cases, there is an error and p is said to be an abnormal root:

AbRoot ′ (p) ≡ Self Root(p) ∧ ¬Self RootOk ′ (p) ∨ ¬Self Root(p) ∧ ¬KinshipOk ′ (p, p.par)
These are the two possible errors identified in the Subsection 3.2. A tree is called an abnormal tree (resp. normal) when its root is abnormal (resp. normal).

We now detail the different predicates and actions of Algorithm 1.

Algorithm Variable status Abnormal trees need to be frozen before to be cleaned in order to prevent them from growing endlessly (see 3.2). This mechanism (inspired from [START_REF] Blin | An improved snap-stabilizing PIF algorithm[END_REF]) is achieved using an additional variable, status, that is used as follows. If a process is clean (i.e., not involved into any freezing operation), then its status is C. Otherwise, it has status EB or EF and no neighbor can select it as its parent. These two latter states are actually used to perform a "Propagation of Information with Feedback" [START_REF] Ernest | Echo Algorithms: Depth Parallel Operations on General Graphs[END_REF][START_REF] Segall | Distributed Network Protocols[END_REF] into the abnormal trees. Therefore, status EB means "Error Broadcast" and EF means "Error Feedback". From an abnormal root, the status EB is broadcast down in the tree. Then, once the EB wave reaches a leaf, the leaf initiates a convergecast EF -wave. Once the EF -wave reaches the abnormal root, the tree is said to be dead, meaning that there is no process of status C in the tree and no other process can join it. So, the tree can be safely reset from the abnormal root toward the leaves. Notice that the new variable status may also get arbitrary initialization. Thus, we enforce previously introduced predicates as follows.

≡ {q ∈ N p | q.par = p} RealChildren p ≡ {q ∈ Children p | KinshipOk(q, p)} p q ≡ (p.idR ≤ q.idR) ∧ [(p.idR = q.idR) ⇒ (p ≤ q)] M in p ≡ min {q ∈ N p | q.status = C} Predicates Self Root(p) ≡ p.par = p Self RootOk(p) ≡ (p.level = 0) ∧ (p.idR = p) ∧ (p.status = C) GoodIdR(s, f ) ≡ (s.idR ≥ f.idR) ∧ (s.idR < s) GoodLevel(s, f ) ≡ (s.idR = f.idR) ⇒ (s.level = f.level + 1) GoodStatus(s, f ) ≡ [(s.status = EB) ⇒ (f.status = EB)] ∨[(s.status = EF ) ⇒ (f.status = C)] ∨[(s.status = C) ⇒ (f.status = EF )] KinshipOk(s, f ) ≡ GoodIdR(s, f ) ∧ GoodLevel(s, f ) ∧ GoodStatus(s, f ) AbRoot(p) ≡ [Self
A self root must have status C, otherwise it is an abnormal root:

Self RootOk(p) ≡ Self RootOk ′ (p) ∧ (p.status = C)
To be a real child of q, p should have a status coherent with the one of q. This is expressed with the predicate GoodStatus(p, q) which is used to enforce the KinshipOk(p, q) relation:

GoodStatus(p, q) ≡ [(p.status = EB) ⇒ (q.status = EB)] ∨[(p.status = EF ) ⇒ (q.status = C)] ∨[(p.status = C) ⇒ (q.status = EF )]
KinshipOk(p, q) ≡ KinshipOk ′ (p, q) ∧ GoodStatus(p, q)

Precisely, when p has status C, its parent must have status C or EB (if the EB-wave is not propagated yet to p). If p has status EB, its parent must be of status EB because p gets status EB from its parent and its parent will change its status to EF only after p gets status EF . Finally, if p has status EF , its parent can have status EB (if the EF -wave is not propagated yet to its parent) or EF .

Normal Execution Remark that, after all abnormal trees have been removed, all processes have status C and the algorithm works as in the initial version. Notice that the guard of J-action has been enforced so that only processes with status C and which are not abnormal root can execute it, and when executing J-action, a process can only choose a neighbor of status C as parent. Moreover, remark that the cleaning of all abnormal trees does not ensure that all fake IDs have been removed. Rather, it guarantees the removal of all fake IDs smaller than ℓ. This implies that (at least) ℓ is a self root at the end of the cleaning and all other processes will elect ℓ within the next D rounds.

Cleaning Abnormal Trees Figure 5 shows how an abnormal tree is cleaned. In the first phase (see Figure 5a), the root broadcasts status EB down to its (abnormal) tree: all the processes in this tree execute EB-action, switch to status EB and are consequently informed that they are in an abnormal tree. The second phase starts when the EB-wave reaches a leaf. Then, a convergecast wave of status EF is initiated thanks to action EF -action (see Figure 5b). The system is asynchronous, hence all the processes along some branch can have status EF before the broadcast of the EB-wave is done into another branch. In this case, the parent of these two branches waits that all its children in the tree (processes in the set RealChildren) get status EF before executing EF -action (Figure 5c). When the root gets status EF , all processes have status EF : the tree is dead. Then (third phase), the root can reset (safely) to become a self root by executing R-action (Figure 5e). Its former real children (of status EF ) become themselves abnormal roots of dead trees (Figure 5f) and reset, etc. Finally, we used the predicate Allowed(p) to temporarily lock the parent of p in two particular situations -illustrated in Figure 6

(c) It may happen that the EF -wave reaches a node, here process 5, even though the EBwave is still broadcasting into some of its proper subtrees: 5 must wait that the status of 4 and 7 become EF before executing EF -action.

EF -action

EF EB

(d) EB-wave has been propagated in the other branch. An EF -wave is initiated by the leaves.

R-action EF

(e) EF -wave reaches the root. The root can safely reset (R-action) because its tree is dead. The cleaning wave is propagated down to the leaves. to EB. These locks impact neither the correctness nor the complexity of LE. Rather, they allow us to simplify the proofs by ensuring that, once enabled, EB-action remains continuously enabled until executed.

R-action

Correctness and Complexity Analysis

In this section, we first define some concepts which will be used in the proofs (Subsection 4.1). Then, we show in Subsection 4.2 that Algorithm LE is self-stabilizing and silent for the leader election, assuming a distributed unfair daemon. Along the proof, we also establish a bound on its stabilization time in steps, namely O(n 3 ). Finally, we study more precisely the complexity of LE in Subsection 4.3 (in particular, we give its complexity in rounds).

Some definitions

First, we instantiate the function Leader(p) used in the specification of the leader election (Section 2.5).

Definition 1 (Leader). For each process p, for every configuration γ, the value Leader(p) in γ is p.idR.

Note that the value of Leader(p) depends on the current configuration γ. Nevertheless, when it is clear from the context, we omit the mention to γ. This will be also the case for every predicates and notations used in the sequel.

We now recall some definitions and notations from graph theory. A path P, from p k to p 0 is a sequence of processes p k , p k-1 , . . . , p 0 such that p i-1 ∈ N p i , for all i in {1, ..., k}. Nodes p k and p 0 are respectively called the initial and terminal extremity of P. The length of P, denoted by |P|, is equal to k. We call cycle any path p k , p k-1 , . . . , p 0 such that p 0 = p k . The distance between two processes p and q, denoted p, q , is equal to the length of the shortest path between p and q. The diameter of the network, denoted D, is the maximum distance between any two processes.

The rest of the paragraph is dedicated to introducing and justifying the notion of trees induced by the KinshipOk relation. We first show that the predicate KinshipOk is an acyclic relation. To that goal, we define the graph induced by the KinshipOk relation.

Definition 2 (Graph of Kinship Relations).

For some configuration γ, let G kr = (V, KR) be a directed graph such that (p, q) ∈ KR ⇔ ({p, q} ∈ E) ∧ (p.par = q) ∧ KinshipOk(p, q). G kr is called the graph of kinship relations in γ.

We first show that G kr is a DAG (Directed Acyclic Graph). We recall, path and cycle naturally extend to directed graph, i.e., a (directed) path P in G kr is a sequence of processes p k , p k-1 , . . . , p 0 such that for all i in {1, ..., k}, (p i , p i-1 ) ∈ KR.

Lemma 1. Let γ be a configuration. The graph of kinship relations in γ contains no cycle.

Proof. By definition, for all pairs of processes p, q such that KinshipOk(p, q) holds, we have: p.idR ≥ q.idR and p.idR = q.idR ⇒ p.level = q.level + 1. Hence, the processes along any path in G kr are ordered w.r.t. the strict lexical order on the pair (idR, level). The result directly follows.

Hence G kr is a DAG (Directed Acyclic Graph) and even a spanning forest since the condition p.par = q implies at most one successor per process in KR. Below, we define the roots and trees of this spanning forest.

Definition 3 (Root). For some configuration γ, a process p satisfies Root(p) (and is called a root in γ) if and only if Self Root(p)∨AbRoot(p), or equivalently if Self Root(p)∨¬KinshipOk(p, p.par) holds in γ.

Next, we define the paths, called KP aths, that follow the tree structures in G kr , i.e., the paths linking each process to the root of its own tree. Definition 4 (KPath). For every process p, KP ath(p) is the unique path p 0 , p 1 , . . . , p k such that p k = p and satisfying the following conditions:

• ∀i, 1 ≤ i ≤ k, (p i .par = p i-1 ) ∧ KinshipOk(p i , p i-1 ) • Root(p 0 )
Using Definitions 3 and 4, we formally define trees as follows.

Definition 5 (Tree). For some configuration γ, for every process p such that Root(p), we define T ree(p), the tree rooted at p, as follows:

T ree(p) = {q ∈ V | p is the initial extremity of KP ath(q)}
This means, in particular, that we identify each tree with the ID of its root.

We give in Observation 1 an invariant on KPaths when looking at the status of the processes. This property is based on the notion of S-Trace defined below.

Correctness

To prove the self-stabilization of Algorithm LE under an unfair daemon, we first show that any execution is finite (Theorem 1) and then we show that in any terminal configuration, there is a unique leader: for every two processes, p and q, we have Leader(p) = Leader(q) and Leader(p) is the ID of some process (Theorem 2).

Termination of LE

The goal, here, is to show that any execution contains a finite number of steps. We first partition a given execution into a finite number of segments (Lemma 4), see Fig. 7. Then, we prove that each segment contains a finite number of J-actions (Lemma 10). This latter result implies that every execution contains a finite number of J-actions (Corollary 2). Then, we show, in Lemma 11 and Corollary 3, that every execution contains a finite number of other actions. This allows us to conclude in Theorem 1 that every execution contains a finite number of steps.

Abnormal Trees First, we introduce some notions that refine the concept of trees.

Definition 7 (Normal/Abnormal Tree). For every configuration γ and every process p, any tree rooted at p such that ¬AbRoot(p) in γ is called a normal tree. In this case, Self Root(p) ∧ Self RootOk(p) holds in γ, by Definition 3. Any tree that is not normal is simply said to be abnormal.

Definition 8 (Alive/Dead). Let γ be a configuration. A process p is called alive in γ if and only if γ(p).status = C. Otherwise, p is said to be dead. A tree T in γ is called an alive tree in γ if and only if ∃p ∈ T such that p is alive in γ. Otherwise, it is called a dead tree.

Definition 9 (Leave/Join a Tree). Let γ → γ ′ be a step. If a process p is in a tree T in γ, but in a different tree T ′ in γ ′ (namely, the roots of T and T ′ are different), we say that p leaves T and joins T ′ in γ → γ ′ .

Remark 1. No process can join a dead tree.

Lemma 2. No alive abnormal root can be created.

Proof. Let p be a process which is not an alive abnormal root in some configuration γ. This means that p is dead, p is a normal root (Self Root(p) ∧ Self RootOk(p) holds in γ), or p is not a root (KinshipOk(p, p.par) holds in γ).

Let γ → γ ′ be a step. If p executes EB-action in γ → γ ′ (respectively EF -action), then γ ′ (p).status = EB (respectively γ ′ (p).status = EF ) and, consequently, p is dead in γ ′ .

If p executes R-action, the predicate Self Root(p)

∧ Self RootOk(p) holds in γ ′ . So, p is a normal root in γ ′ .
If p executes J-action, let q = M in p in γ. By definition of J-action, γ(p).idR ≤ p (since p is not an abnormal root at γ), γ(q).status = C, and γ(p).status = γ ′ (p).status = C. Also, ¬Self Root(p) holds in γ ′ .

• If q does not move in γ → γ ′ , then γ ′ (p).par = q, γ ′ (q).status = C = γ ′ (p).status, γ ′ (p).level = γ(q).level + 1 = γ ′ (q).level + 1, and γ ′ (p).idR = γ(q).idR = γ ′ (q).idR < γ(p).idR ≤ p. Hence, the predicate KinshipOk(p, p.par) is true in γ ′ . Now, we already know that ¬Self Root(p) holds in γ ′ . Thus, ¬Self Root(p) ∧ KinshipOk(p, q) holds in γ ′ : p is not a root in γ ′ , by Definition 3.

• Assume now that q moves during the step γ → γ ′ . As γ(q).status = C, q can only execute EB-action or J-action in the step. Consequently, γ ′ (q).idR ≤ γ(q).idR. Then, γ ′ (p).idR = γ(q).idR ≥ γ ′ (q).idR and γ ′ (p).idR = γ(q).idR < γ(p).idR ≤ p. So, the predicate GoodIdR(p, q) holds in γ ′ .

If q executes J-action, then γ ′ (p).idR = γ ′ (q).idR. Otherwise, q executes EB-action, so γ ′ (p).idR = γ ′ (q).idR and γ ′ (p).level = γ(q).level + 1 = γ ′ (q).level + 1. Hence, GoodLevel(p, q) holds in γ ′ .

Finally, γ ′ (q).status ∈ {C, EB} and γ ′ (p).status = γ(p).status = C, so the predicate GoodStatus(p, q) holds in γ ′ .

Thus, ¬Self Root(p) ∧ KinshipOk(p, q) holds in γ ′ and, so, p is not a root in γ ′ , by Definition 3.

Assume now that p executes no action in the step γ → γ ′ . The only way for p to become an alive abnormal root is that γ(p).par moves during the step, since the property "alive abnormal root" only depends on p and p.par. Furthermore, as p is not an alive abnormal root, when p is a normal root in γ, it stays so, in γ ′ .

Therefore, let us consider the case when p is not a root in γ and γ(p).par moves. As p changes none of its variables, the only way for it to become an alive abnormal root is to have status C in γ and thus in γ ′ . As GoodStatus(p, p.par) holds in γ, this implies that the status of γ(p).par is either EB or C. Looking at case EB, p is a real child of p.par in γ with status C; hence EF -action is disabled for p.par in γ. Looking at case C, p.par can execute EB-action and can change only its status to EB in γ → γ ′ : GoodStatus(p, p.par) holds in γ ′ and consequently KinshipOk(p, p.par) holds in γ ′ . p.par can also execute J-action in γ → γ ′ . This means that in γ and in γ ′ , p.par has status C, hence GoodStatus(p, p.par) holds in γ ′ . Furthermore, p.par has a smaller value of idR in γ ′ , so GoodIdR(p, p.par) and GoodLevel(p, p.par) are satisfied in γ ′ , and consequently KinshipOk(p, p.par) holds in γ ′ . Lemma 3. No alive abnormal tree can be created.

Proof. Let γ → γ ′ be a step. Let p ∈ V . Assume there is no alive abnormal tree rooted at p in γ. In particular, p is not an alive abnormal root in γ. Then, assume, by contradiction, that T ree(p) exists and is an alive abnormal tree in γ ′ .

• If γ ′ (p).status = EF , then every process in the tree has status EF (Observation 1) and the tree is dead, a contradiction.

• If γ ′ (p).status = C, then p is an alive abnormal root in γ ′ . But no alive abnormal root is created (Lemma 2), a contradiction.

• If γ ′ (p).status = EB. Then, according to the algorithm, there are two possible cases:

γ(p).status = EB:

-If AbRoot(p) holds in γ, then T ree(p) is dead in γ (otherwise, T ree(p) is an abnormal alive tree in γ, a contradiction). By the definition of J-action, no process can join T ree(p) in γ → γ ′ . Moreover, as γ(p).status = EB, no process q in T ree(p) satisfies Reset(q) in γ, by Observation 1. Consequently, no process can leave T ree(p) in γ → γ ′ . So, every process in T ree(p) still have status EF or EB in γ ′ , i.e. T ree(p) is still dead in γ ′ , a contradiction.

-If ¬AbRoot(p) holds in γ, then p does not satisfy Self Root(p). Indeed, the predicate Self RootOk(p) implies that p.status = C in γ, a contradiction. So, let q = γ(p).par ∈ N p . ¬AbRoot(p) in γ implies that q.status = EB and the predicate KinshipOk(p, q) holds in γ. This latter also implies that p ∈ RealChildren q in γ. Now, p ∈ RealChildren q and p.status = EB in γ implies that q is disabled in γ. Moreover, as γ ′ (p).status = EB, p does not execute any action in γ → γ ′ . So, the predicate ¬AbRoot(p) still holds in γ ′ , a contradiction. γ(p).status = C: ¬AbRoot(p) holds in γ (otherwise p is an abnormal alive root in γ).

Then, p executes EB-action in γ → γ ′ to get status EB. So, EBroadcast(p) ∧ ¬AbRoot(p) implies that p.par = p and p.par.status = EB in γ. Let q = γ(p).par. Now, p.par = p and ¬AbRoot(p) implies that KinshipOk(p, q) in γ. So, p ∈ RealChildren q and, as p.status = C and q.status = EB in γ, q is disabled in γ.

Moreover, as γ ′ (p).status = EB, p necessarily executes EB-action in γ → γ ′ which only changes its status to EB. So, ¬AbRoot(p) still holds in γ ′ , a contradiction.

Finite Number of J-actions

To show that every process p executes only a finite number of J-actions, we prove below that p can only execute a finite number of J-actions in each segment of execution -a segment being separated from its follower by the death or the disappearance of some tree.

Definition 10 (Disappear/Die). Let γ → γ ′ be a step and let p be a process such that Root(p) in γ.

• T ree(p) disappears during the step γ → γ ′ if and only if T ree(p) is no more defined in γ ′ -namely Root(p) does not hold in γ ′ .

• T ree(p) dies during the step γ → γ ′ if and only if T ree(p) is alive in γ, yet T ree(p) exists -namely Root(p) holds -and is dead in γ ′ .

γ 0 γ 1 a segment another segment a tree dies or disappears Proof. In the initial configuration, there are at most n abnormal roots (every process) and, consequently, at most n abnormal trees. As no alive abnormal tree can be created (Lemma 3), if an abnormal tree is alive, then it is alive since the initial configuration. So, there is at most n trees that die or disappear and, consequently, there are at most n + 1 segments in the execution.

We now count the number of J-actions processes can execute in a given segment. For that purpose, we first need to prove intermediate lemmas that identify properties on computation steps.

Observation 2. Let γ be a configuration and let p a process such that Reset(p) is true in γ. Then, T ree(p) exists and is dead in γ.

Proof. Let γ be a configuration and let p be a process such that Reset(p) is true in γ. By definition, AbRoot(p) holds in γ, hence T ree(p) is defined in γ. Furthermore, γ(p).status = EF : by Observation 1, every process in T ree(p) has status EF in γ, and we are done.

Lemma 5. Let γ → γ ′ be a step and let p be a process such that p.status ∈ {EB, EF } in γ. Let T be the tree which contains p in γ. First, T is an abnormal tree in γ. Second, if T does not disappear during the step γ → γ ′ , p is still in T in γ ′ unless T was dead in γ.

Proof. Let γ → γ ′ be a step and let p be a process such that p.status ∈ {EB, EF } in γ. We note r the root of the tree containing p in γ. As S-T race(KP ath(p)) ∈ EB * EF * , by Observation 1, the status of r in γ is either EF or EB. Hence AbRoot(r) holds in γ: T ree(r) is an abnormal tree in γ.

Assume now that Root(r) holds in γ ′ (the tree does not disappear during the step). If r executes R-action in γ → γ ′ , Observation 2 applies in γ and proves that T ree(r) is dead in γ.

If r does not (or cannot) execute R-action, its only possible action is EF -action. As Root(r) holds in γ ′ , r is still abnormal root in γ ′ . Let then q ∈ KP ath(p) in γ with q = r. By Observation 1, γ(q).status ∈ {EB, EF } also. If γ(q).status = EB, q can only execute EF -action and if γ(q).status = EF , q is disabled, as q = r. Executing EF -action preserves GoodStatus and hence preserves also KinshipOk relations. Therefore, the KP ath from p to r is the same in γ and γ ′ and then p ∈ T ree(r) in γ ′ . Lemma 6. Let p be a process and let γ → γ ′ be a step. If p is an abnormal root of status C in γ, then it is still an abnormal root in γ ′ .

Proof. Let γ → γ ′ be a step and let p be a process such that AbRoot(p) ∧ p.status = C in γ: p can only execute EB-action. Therefore, γ ′ (p).status ∈ {C, EB} and every other variable of p has identical value in γ and γ ′ .

So, if Self Root(p) holds in γ, then Self RootOk(p) is false in γ, and Self Root(p)∧¬Self RootOk(p) still holds in γ ′ .

Otherwise, ¬Self Root(p) holds in γ, i.e., p.par = p. Then, ¬Self Root(p) still holds in γ ′ . Let q ∈ V such that q = γ(p).par and consider the following cases: γ(q).status = EF : Then, ¬GoodStatus(p, q) holds in γ which implies that ¬KinshipOk(p, q) holds in γ. However, p ∈ Children q in γ. So, ¬Allowed(q) holds in γ, and q is disabled. So, γ ′ (p).status ∈ {C, EB} and γ ′ (q).status = EF , which implies that the predicate ¬GoodStatus(p, q) holds in γ ′ . Thus, we have ¬KinshipOk(p, q) in γ ′ . γ(q).status = EB: Then, GoodStatus(p, q) holds in γ. So, AbRoot(p) in γ implies that the predicate ¬GoodIdR(p, q) ∨ ¬GoodLevel(p, q) holds in γ. Now, q can only executes EF -action in γ → γ ′ . So, neither p nor q modify their variables par, idR, or level in γ → γ ′ , and, consequently, ¬GoodIdR(p, q) ∨ ¬GoodLevel(p, q) still holds in γ ′ . So, ¬KinshipOk(p, q) holds in γ ′ .

γ(q).status = C: As AbRoot(p) holds in γ, ¬KinshipOk(p, q) in γ. Thus, ¬Allowed(q) holds in γ because p ∈ Children q and p.status = C in γ. So, q cannot execute J-action in γ → γ ′ . Then, γ(q).status = C and γ(p).status = C implies that GoodStatus(p, q) holds in γ. So, AbRoot(p) in γ implies that ¬GoodIdR(p, q) ∨ ¬GoodLevel(p, q) holds in γ. As p and q can only modify their status during the step γ → γ ′ (q can only execute EB-action in γ → γ ′ ), ¬GoodIdR(p, q) ∨ ¬GoodLevel(p, q) still holds in γ ′ . So, ¬KinshipOk(p, q) holds in γ ′ .

In any cases, ¬KinshipOk(p, q) holds in γ ′ . As the predicate ¬Self Root(p) holds in γ ′ , AbRoot(p) holds in γ ′ .

Lemma 7. Let γ be a configuration and let p be a process such that p.status ∈ {EB, EF } in γ. Let T be the tree which contains p in γ. Let γ R be the first configuration, if any, after γ, such that p executes an R-action γ R → γ R+1 . Assume γ R exists, then T is dead in γ R or has disappeared (at least once) between γ and γ R .

Proof. Let γ be a configuration and let p be a process such that p.status ∈ {EB, EF } in γ. We note r the root of the tree which contains p in γ. Let γ = γ 0 γ 1 ... be an execution starting at γ. Let γ R be the first configuration, if any, in this execution such that p executes an R-action during the step γ R → γ R+1 .

For every configuration γ x , x ∈ {0, ..., R -1}, the status of p is EB or EF . Hence, Lemma 5 applies iteratively in γ x : either T ree(r) disappears during the step γ x → γ x+1 , or, if not, p ∈ T ree(r) in γ x+1 . Hence, in γ R , either T ree(r) has disappeared or, if not, p ∈ T ree(r).

When p ∈ T ree(r) in γ R , by assumption, p executes an R-action between γ R and γ R+1 . Hence, AbRoot(p) holds in γ R and thus p = r. Furthermore, Observation 2 applies and proves that T ree(r) is dead in γ R . Lemma 8. Let p be a process and let γ → γ ′ be a step. Let T be the tree that contains p in γ. If EBroadcast(p) holds in γ, then T is an abnormal alive tree in γ and, if T has not disappeared in γ ′ , p still belongs to T in γ ′ .

Proof. Let γ → γ ′ be a step. Let p be a process such that EBroadcast(p) holds in γ. We note r the root of the tree which contains p in γ.

If AbRoot(p) holds in γ, then p = r is the root of an alive abnormal tree, since γ(p).status = C. Furthermore, if T ree(p) exists in γ ′ , p ∈ T ree(p) in γ ′ , trivially.

Otherwise, ¬AbRoot(p), p.par.status = EB, and KinshipOk(p, p.par) holds in γ. Applying Lemma 5 to γ(p).par, we have that γ(p).par belongs to an abnormal alive tree in γ and so does p: T ree(r) is an alive abnormal tree.

Furthermore, first note that γ(p).par = γ ′ (p).par (p can only change its status to EB in γ → γ ′ : either p do not move or executes EB-action). So, still by Lemma 5, in γ ′ , if T ree(r) exists in γ ′ , γ ′ (p).par belongs to T ree(r) in γ ′ , since T ree(r) is not dead in γ (γ(p).status = C).

As KinshipOk(p, p.par) holds in γ, we have that p ∈ RealChildren q in γ. Since γ(p).status = C, q is disabled in γ (because of p) and, as p can only modify its status to EB in γ → γ ′ , we still have p ∈ RealChildren q in γ ′ , i.e., p and q belong to the same abnormal tree, T ree(r), in γ ′ . Corollary 1. Let γ be a configuration and let p be a process such that EBroadcast(p) holds in γ. Let T the tree which contains p in γ. Let γ R be the first configuration, if any, since γ, such that p executes an R-action γ R → γ R+1 .

Assume γ R exists, then T is an alive abnormal tree in γ but it is dead in γ R or has disappeared (at least once) between γ and γ R .

Proof. Let γ be a configuration and let p be a process such that EBroadcast(p) holds in γ. We note r the root of the tree which contains p in γ. Lemma 8 applies in γ: T ree(r) is an alive abnormal tree in γ.

Let γ = γ 0 γ 1 ... be an execution starting at γ. Let γ R be the first configuration, if any, in this execution such that p executes an R-action during the step γ R → γ R+1 . We assume that γ R exists. Then at some step, γ i → γ i+1 , p executes a EB-action, with i < R.

Lemma 8 applies iteratively from γ 0 and to γ i : either T ree(r) has disappeared in γ 1 (and so between γ 0 and γ i+1 ), or p stays in T ree(r) in γ 1 (and so between γ 0 and γ i+1 ), and so on.

If T ree(r) has not yet disappeared in γ i+1 , then p ∈ T ree(r) in γ i+1 and γ i+1 (p).status = EB. Here, Lemma 7 applies and proves that T ree(r) has disappeared in γ R or p is in T ree(r) in γ R . Lemma 9. Let p be a process. Let s be a segment of execution. Between any two executions of J-action by p in s, p can only execute J-actions.

Proof. Let s = γ 0 γ 1 . . . be a segment of execution and p ∈ V . Consider two executions of J-action by p during s: one in γ i → γ i+1 and the other in γ j → γ j+1 , with i < j. Assume by contradiction that p executes an action different from J-action between γ i+1 and γ j . Let γ k → γ k+1 be the first step between γ i+1 and γ j during which p executes some other action: this is a EB-action. Let γ l → γ l+1 be the last step between γ i+1 and γ j during which p executes some other action: this is a R-action (hence k < l). Now, Lemma 1 applies since in γ k , EBroadcast(p) holds, and in some step later γ l → γ l+1 , p executes a R-action. This proves that in γ k , some abnormal tree is alive and that in γ l , this tree is dead or has disappeared. Hence γ k and γ l are not in the same segment, a contradiction. Lemma 10. In a segment of execution, there are at most (n-1)(n-2)/2 executions of J-action.

Proof. Let p ∈ V . First, p only executes J-actions between two J-actions in the same segment (Lemma 9). So, using the guard of J-action, it follows that the value of the p.idR always decreases during any sequence of J-actions which means that p cannot set p.idR two times to the same value during the segment.

Let A be the set of processes q such that q.status = C at the beginning of the segment. Let B the set of processes q such that q executes an R-action in the segment. A ∩ B = ∅. Indeed, pick a process q ∈ A ∩ B. q switches from status C at the beginning to status EB, and then to status EF since some step later, it executes R-action. Hence, there exists a configuration γ b in the segment such that EBroadcast(q) is true and another γ r , later on such that R-action occurs: hence Corollary 1 applies and proves that the tree of q in γ b is abnormal alive and that it dies or disappears some step before γ r . This contradicts the definition of segment. Hence, |A| + |B| ≤ n. Now, p.idR can only be assigned to [START_REF] Afek | Self-Stabilizing Unidirectional Network Algorithms by Power Supply[END_REF] values which are present in variables idR of processes in A at the first configuration of the segment and (2) to ID of processes in

B. Let f : V → N such that ∀p ∈ A ∪ B, if p ∈ A, f (p) = x,
where x is the value of p.idR at the beginning of the segment; otherwise, f (p) = p. Let p 0 , . . . p k-1 (with k ≤ n) be the set of processes in A ∪ B in ascending order of f . p i changes at most i times of idR. Hence, in a given segment, the number of executed J-actions, noted ♯J-action, satisfies the following inequality:

♯J-action ≤ k-1 i=0 i ≤ n-1 i=0 i = (n -1)(n -2) 2
By Lemmas 4 and 10, in any execution, there are at most n + 1 segments, where processes execute at most (n -1)(n -2)/2 J-actions. Moreover, by definition, there are at most n steps outside segments (more precisely, the steps where at least one abnormal tree dies or disappears) where some J-actions may be executed. Hence, follows:

Corollary 2. In any execution, there are at most n 3 2n 2 + n 2 + 1 steps containing J-actions.

Other Actions Below, we show an upper bound on the number of executions of other actions.

Lemma 11. In any execution, each process can execute at most n R-actions.

Proof. First, by definition, there are at most n abnormal alive trees in the initial configuration.

Let ♯AbT be that number. Moreover, ♯AbT can only decrease, by Lemma 3.

Let p be a process. We first show that when p executes R-action for the first time, ♯AbT ≤ n-1. Then, we show that after every subsequent execution of a R-action by p, ♯AbT necessarily decreases. Hence, we will conclude that p cannot execute R-action more than n, because ♯AbT cannot be negative.

Consider the first step γ i → γ i+1 where p executes R-action. Using Observation 2, T ree(p) exists and is dead in γ i . Hence, there are at most n -1 abnormal alive trees in γ i .

Consider the jth execution of R-action by p, with j > 1. After the (j -1)th R-action of p, the status of p is C. So, between the (j -1)th and the jth R-action, the status of p thus switches from C to EB and from C to EF , so that p can switch its status from EF to C when executing its jth R-action. Hence, meanwhile there exists a configuration γ b such that EBroadcast(q) is true and another γ r , later on such that p executes its jth R-action in γ r → γ r+1 : Corollary 1 applies and proves that the tree to which p belongs in γ b is abnormal alive and that tree dies or disappears some step before γ r , and we are done.

Let p be a process. p necessarily executes R-action between two executions of EF -action (resp. EB-action). Hence, we have the following corollary.

Terminal Configurations

We now show that in a terminal configuration, there is one and only one leader process, known by all processes, i.e., for every two processes, p and q, we have Leader(p) = Leader(q) and Leader(p) is the ID of some process.

Lemma 12. In a terminal configuration, every process has status C.

Proof. By contradiction, consider a terminal configuration γ where some process p satisfies p.status = C. Then two cases are possible:

1. p.status = EB. By Observation 1, ∃q ∈ V such that q.status = EB∧(∀q ′ ∈ RealChildren q , q ′ .status = EB) ∧ p ∈ KP ath(q). If RealChildren q = ∅, then q can executes EF -action. Otherwise, there are two cases. If ∀q ′ ∈ RealChildren q then, q ′ .status = EF and q can execute EF -action. Otherwise, there is q ′ ∈ RealChildren q such that q ′ .status = C and then q ′ can execute EB-action. Hence, in both cases, γ is not terminal, a contradiction.

2. p.status = EF . By Observation 1, ∃q ∈ V such that q.status = EF ∧ (Root(q)∨ (KinshipOk(q, q.par) ∧ q.par.status = EF ) ∧ q ∈ KP ath(p).

If Root(q), then AbRoot(q) ∨ Self Root(q). Now, q.status = EF implies that AbRoot(q) holds. So, in all cases, q.status = EF ∧ AbRoot(q) holds. If Allowed(q) holds, then R-action is enabled at q, a contradiction. Otherwise, ∃r ∈ Children q such that ¬KinshipOk(r, q)∧ r.status = C. So EB-action is enabled at r, a contradiction.

If ¬Root(q), either q.par.status = C, AbRoot(q) holds and we obtain a contradiction as in the case where Root(q) holds, or q.par.status = EB and using the same argument as in case 1, we can deduce that some process is enabled, a contradiction.

Hence, all cases, γ is not terminal, a contradiction.

Theorem 2 (Correctness). In a terminal configuration, ∀p, q ∈ V, Leader(p) = Leader(q) and Leader(p) is the ID of some process.

Proof. Let γ be a terminal configuration. Assume first, by contradiction, that there are at least two leaders. As G is connected, ∃p, q ∈ V such that Leader(γ(p)) = Leader(γ(q)) and q ∈ N p . Now, assume without loss of generality that:

Leader(γ(p)) = γ(p).idR < γ(q).idR = Leader(γ(q)) By Lemma 12, p.status = q.status = C. Then, either EBroadcast(q) is true and q can execute EB-action or q can execute J-action. Hence γ is not terminal, a contradiction. Assume now that the leader is not one of the processes, i.e., is a fake ID. Let p ∈ V such that its level is minimum. Notice that γ(p).status = C by Lemma 12. If Self Root(p) holds in γ, γ(p).idR = p. So, AbRoot(p) holds and p can execute EB-action. Otherwise, there is q ∈ N p such that γ(p).par = q. As the level of p is minimum, γ(p).level ≤ γ(q).level. So, AbRoot(p) holds and p can execute EB-action. Hence, γ is not terminal, a contradiction. Using Theorem 2, there is exactly one root in a terminal configuration (the leader elected). So the graph of kinship relations in a terminal configuration contains exactly one tree. Hence, we can conclude: Remark 2. In a terminal configuration, G kr is a spanning tree rooted at the leader.

Theorems 1 and 2 establish the self-stabilization, silence, and step complexity of Algorithm LE. Moreover, note that idR and level can be stored in Θ(log n) bits. Hence, we can conclude: Theorem 3. Algorithm LE is a silent self-stabilizing leader election algorithm working under a distributed unfair daemon. Its step complexity is at most n 3 2 + 2n 2 + n 2 + 1 steps. Its memory requirement is Θ(log n) bits per process.

Complexity Analysis

In this section, we study the complexity of Algorithm LE in rounds and we make a worst-case analysis of its stabilization time both in steps and rounds.

For any process p, p can only set p.idR to its own ID or copy the value of q.idR, where q is one of its neighbors. So, we have the following remark: Remark 5. No fake ID is created during any step.

Lemma 16. In a clean configuration, if the idR of a process p is ℓ, p is disabled forever.

Proof. Let γ be a clean configuration. Let p be a process with γ(p).idR = ℓ. By Remark 4, only J-action can be enabled in γ. Moreover, its guard reduces to ∃q ∈ N p , (q.idR < p.idR). But Lemma 15 ensures that this cannot be true, hence p is disabled in γ. Then, by Lemma 13 and Remark 5, this will be true forever. Proof. Consider any execution e that starts from a clean configuration. In the following, we denote by ρ i the first configuration of the ith round in e. We show by induction on the distance d ≥ 0 between the processes and ℓ that ∀p ∈ V such that p, ℓ ≤ d, ρ d (p).idR = ℓ.

Base case: If p, ℓ = 0, p = ℓ. Notice that if the predicate GoodIdR(p, p.par) holds in ρ 0 , it would implies that p.idR < p which is false by Lemma 15. So KinshipOk(p, p.par) cannot hold in ρ 0 . Hence, Self Root(p) ∧ Self RootOk(p) holds in ρ 0 (by Remark 3) and ρ 0 (p).idR = p = ℓ.

Induction step: Assume the property holds at some d ≥ 0. If p, ℓ = d + 1, ∃q ∈ N p such that q, ℓ = d. By induction hypothesis and by Lemma 16, q.idR = ℓ and q is disabled forever since ρ d .

If p.idR = ℓ in ρ d , it remains so forever (Lemma 16). If p.idR = ℓ in ρ d then q.idR < p.idR (Lemma 15). Then, J-action is enabled at p in ρ d and remains enabled until p executes it (Lemma 14). As there is no fake ID smaller than ℓ (Lemma 15), p.idR = ℓ after p executes J-action, i.e., after at most one round. Hence, p.idR = ℓ in ρ d+1 .

As D ≥ max { p, ℓ , p ∈ V }, in at most D rounds, the system reaches a configuration where ∀p ∈ V, p.idR = ℓ. By Corollary 4, this configuration is terminal.

Dirty Configurations

In the previous paragraph, we proved that, starting from a clean initial configuration, the system reaches a terminal configuration in at most D rounds. But what happens if the initial configuration is dirty, i.e., if there is a process p such that the predicate EBroadcast(p) holds or p.status = C. In this section, we prove that starting from a dirty configuration, the system reaches a clean configuration in at most 3n rounds. More precisely, we show that a dirty configuration contains abnormal trees that are "cleaned" in at most 3n rounds. The system will be in a clean configuration afterwards. Lemma 17. In an dirty configuration, there exists at least one abnormal root.

Proof. Let γ be a dirty configuration. Then, ∃p ∈ V such that p.status = C ∨ EBroadcast(p). We search for an abnormal root.

1. If p.status ∈ {EB, EF }, using Observation 1, there is q ∈ KP ath(p) such that q.status ∈ {EB, EF } ∧ Root(q). Then, AbRoot(q) ∨ Self Root(q) holds in γ. Now, Self Root(q) ∧ q.status ∈ {EB, EF } implies AbRoot(q). Hence, in all cases, AbRoot(q) holds.

2. If EBroadcast(p) holds, Lemma 8 applies and we are done.

We have just shown that there are abnormal roots (and so abnormal trees) in dirty configurations. Below, we prove that these abnormal trees will disappear after three waves of "cleaning". After the first wave, an abnormal tree becomes dead (Theorem 5), after the second wave any abnormal root gets the status EF (Theorem 6) and finally after the third wave there is no more abnormal trees (Theorem 7), hence the system is in a clean configuration.

The following technical lemma is used in the proof of Theorem 5.

Lemma 18. When EB-action is enabled at a process p, it remains enabled until p executes EB-action.

Proof. Assume that EB-action is enabled at a process p in a configuration γ, but p did not execute EB-action during the step γ → γ ′ . Notice that p does not execute any action during this step, as guards are mutually exclusive. As EB-action is enabled in γ, γ(p).status = C and then, γ ′ (p).status = C. First, assume that the predicate AbRoot(p) holds in γ. If Self Root(p) ∧ ¬Self RootOk(p) holds in γ and, as these predicates only depends on the local state of p and as p does not execute any action during the step, it also holds in γ ′ : the action is still enabled in γ ′ . Otherwise, ¬Self Root(p) ∧ ¬KinshipOk(p, p.par) holds in γ. These predicates only depends on the local state of p and its parent. Now, Allowed(p.par) does not hold in γ because of p, so p.par cannot execute R-action nor J-action during γ → γ ′ . Then, either p.par executes EF -action, changes its status to EF and then, GoodStatus(p, p.par) is false in γ ′ , or p.par executes EB-action and changes its status to EB. In these two cases, EBroadcast(p) holds in γ ′ . Now, assume p.par.status = EB. p.par can only execute EF -action and change its status to EF . Then, the predicate GoodStatus(p, p.par) is false in γ ′ , which implies that EBroadcast(p) holds in γ ′ . Theorem 5. In at most n rounds, the system reaches a configuration where every abnormal tree (if any) is dead.

Proof. Consider any execution e = γ 0 , . . .. ∀i > 0, we denote by γ R i the last configuration of the ith round and so the first configuration of the i + 1th round of e. Moreover, let γ R 0 = γ 0 be the initial configuration. We show by induction on the length of the KP aths that, ∀i ≥ R d (d ≥ 1), ∀p ∈ V , if p is in an abnormal tree and |KP ath(p)| ≤ d in γ i , then p is dead in γ i .

Base Case: If p is in an abnormal tree and |KP ath(p)| = 1, p is an abnormal root. As no alive abnormal root is created (Lemma 2), if p is alive, it is an alive abnormal root since γ R 0 and if predicate (p.status = C ∧ AbRoot(p)) becomes false in some configuration, then it remains false forever. Hence, it is sufficient to show that any alive abnormal root is no more an alive abnormal root after one round (that is, from γ R 1 ).

By definition, EB-action is enabled at p in γ R 0 and p executes EB-action during the first round (using Lemma 18). Hence, p is dead at the end of the first round, and we are done. ). So, γ j+1 (p).par = p. So, let q ∈ N p such that γ j+1 (p).par = q. By definition, |KP ath(q)| = d in γ j+1 . By induction hypothesis, γ j+1 (q).status ∈ {EB, EF }. Now, p.status = C and |KP ath(p)| > 1 in γ j+1 , so p is not an abnormal root in γ j+1 . Hence, γ j+1 (q).status = EB (by Observation 1) and, consequently, γ j (q).status ∈ {C, EB}.

Induction Hypothesis: Let d ≥ 1. Assume that ∀i ≥ R d , ∀p ∈ V ,
• If γ j (q).status = EB, then p does not execute any action during the step γ j → γ j+1 (otherwise, γ j+1 (p).status = C or γ j+1 (p).par = q). Hence, γ j (p).status = γ j+1 (p).status = C. By hypothesis, "p.status = C ∧ |KP ath(p)| ≤ d + 1" is false in γ j , so we have |KP ath(p)| > d + 1 in γ j . Now, γ j (p).status = C and γ j (q).status = EB, so S-T race(KP ath(p)) = EB + C in γ j (Observation 1) and p is the only process in its KP ath that can execute an action in γ j → γ j+1 . Hence, for every q such that q ∈ KP ath(p) in γ j , q ∈ KP ath(p) in γ j+1 , and then |KP ath(p

)| > d + 1 in γ j+1 . So p.status = C ∧ |KP ath(p)| ≤ d + 1
is false in γ j+1 , a contradiction. • If γ j (q).status = C, then q is in an alive abnormal tree in γ j (indeed, q executes EB-action in γ j → γ j+1 , and so Lemma 8 applies). As q is alive in γ j , we have |KP ath(q)| > d in γ j by induction hypothesis. Moreover, q is not an abnormal root (there is no more alive abnormal root after the first round, see the base case). Hence, the status of its parent in γ j is EB. Now, |KP ath(q)| > d and S-T race(KP ath(q)) = EB + C in γ j (Observation 1). So, q is the only one in its KP ath that executes an action in γ j → γ j+1 and this action is EB-action, that maintains the KinshipOk relation. n ≥ max {|KP ath(p)|, ∀p ∈ V }. Hence, any process in an abnormal tree becomes dead in at most n rounds.

Lemma 19. If EF -action is enabled at a process p, it remains enabled until p executes EF -action.

Proof. Let γ → γ ′ be a step. Assume by contradiction EF -action is enabled at a process p in γ and is not enabled in γ ′ , but p did not execute EF -action during the step γ → γ ′ . Notice that p does not execute any action during this step, as guards are mutually exclusive. As EF eedback(p) holds in γ, γ(p).status = γ ′ (p).status = EB. As EF eedback(p) does not hold in γ ′ and no process can execute J-action and choose a process of status EB as parent, ∃q ∈ RealChildren p such that γ(q).status = EF and γ ′ (q).status = EF . Now, because γ(q).status = EF , q can only execute R-action. However, as q ∈ RealChildren p , KinshipOk(q, p) holds in γ and then q is not a root. So, q cannot execute any action and change its status during γ → γ ′ , a contradiction.

Theorem 6. Let γ be a configuration containing abnormal trees and where all abnormal trees are dead. In at most n rounds from γ, the system reaches a configuration where the status of all abnormal roots is EF .

Proof. Consider any execution e = γ 0 , . . . starting from a configuration that contains abnormal trees and where all abnormal trees are dead. ∀i > 0, we denote by γ R i the last configuration of the ith round and so the first configuration of the i + 1th round. Moreover, let γ R 0 = γ 0 be the initial configuration.

Claim 1: ∀p ∈ V , ∀i ≥ R 0 , if γ i (p).status = EB, then ∀j ≥ i, γ j (p).status = EB.

Assume by contradiction that γ j (p).status = EB and γ j+1 (p).status = EB, with γ j → γ j+1 . Then, p.status = C in γ j and EB-action is enabled at p in γ j . So, p is in an alive abnormal tree in γ j (Lemma 8), a contradiction to Lemma 3.

In any configuration γ, we denote by M axLengthKP ath(p) = max{|KP ath(q)|, q ∈ V ∧ p ∈ KP ath(q)}. Again in γ, we define

L(p) = M axLengthKP ath(p)-|KP ath(p)| and EBL(p, k) ≡ p.status = EB ∧ L(p) = k. Claim 2: ∀i ≥ R 0 , if EBL(p, k i ) holds in γ i , then ∀j ≥ i, ∀k j < k i , ¬EBL(p, k j ) holds in γ j . If j = i, EBL(p, k j ) is false for k j < k i because L(p) cannot have two different values in a same configuration. Assume now j > i. The case k i = 0 is direct. Assume k i > 0.
Assume by contradiction that EBL(p, k i ) holds in γ i and EBL(p, k j ) holds in γ j with j > i and k j < k i . So, γ i (p).status = γ j (p).status = EB and there are two cases:

• p.status = EB in all the configurations between γ i and γ j . Consider the step γ i → γ i+1 . Let q be any process such that p ∈ KP ath(q) in γ i . So, KP ath(q) = q 0 . . . q i . . . q k where q i = p and q k = q, and S-T race(KP ath(q)) = EB + EF * in γ i .

There is a unique process in KP ath(q) that can execute an action in γ i → γ i+1 (the only one of status EB with children of status EF ). If it executes an action, it is EF -action which maintains KinshipOk relation. Hence, ∀q ′ ∈ KP ath(q) in γ i , q ′ ∈ KP ath(q) in γ i+1 . We can apply this latter property to every process r such that p ∈ KP ath(r) and |KP ath(r)| = M axLengthKP ath(p) in γ i : p ∈ KP ath(r) in γ i+1 and the value of |KP ath(r)| in γ i+1 is greater than or equal to the value of |KP ath(r)| in γ i . So, EBL(p, k i+1 ) holds with k i+1 ≥ k i . Applying the same argument on step γ i+1 → γ i+2 , etc., until step γ j-1 → γ j , we obtain that EBL(p, k j ) is true in γ j with k j ≥ k i , a contradiction.

• There is a configuration between γ i and γ j where p.status = EB. So, ∃x, i < x < j, such that γ x (p).status = EB and γ x+1 (p).status = EB. This contradicts Claim 1.

We show by induction that

∀i ≥ R d with d ≥ 1, ∀p ∈ V , ∀k ≤ d -1, EBL(p, k) is false in γ i .
Base case: There are three cases:

1. If L(p) = 0 in γ R 0 and γ R 0 (p).status = EB, then EF -action is enabled at p in γ R 0 , p executes EF -action during the first round, by Lemma 19 and p gets status EF . By Claim 1, p.status remains different from EB forever and EBL(p, 0) is false in γ i , ∀i ≥ R 1 .

2. If γ R 0 (p).status = EB, p.status = EB forever (Claim 1) and then EBL(p, 0) is false forever.

3. If EBL(p, k) holds in γ R 0 with k > 0, EBL(p, 0) is false forever (Claim 2).

Induction hypothesis: ∀i ≥ R d with d ≥ 1, ∀p ∈ V , ∀k ≤ d -1, EBL(p, k) is false in γ i .
Induction step: There are four cases: Lemma 20. If all abnormal trees are dead and R-action is enabled at a process p, then R-action remains enabled at p until p executes it.

Proof. Let γ be a configuration, where all abnormal trees are dead. Assume, by contradiction, that R-action is enabled at a process p in a configuration γ and is not enabled in the next configuration γ ′ , but p did not execute R-action during the step γ → γ ′ . Notice that p does not execute any action during this step, as guards are mutually exclusive. As R-action is enabled in γ and p does not execute an action during the step, γ(p).status = γ ′ (p).status = EF .

If Self Root(p) ∧ ¬Self RootOk(p) holds in γ, it also holds in γ ′ because p does not execute an action between γ and γ ′ and these predicates only depends on the local state of p.

Otherwise ¬Self Root(p) ∧ ¬KinshipOk(p, p.par) holds in γ. Let q = p.par. If q does not execute an action between γ and γ ′ , p is still an abnormal root. Otherwise, three cases are possible:

• ¬GoodIdR(p, q) holds in γ.

1. If γ(p).idR < γ(q).idR. If q executes EB-action or EF -action during the step, the idR of q does not change, so γ ′ (p).idR < γ ′ (q).idR, and then AbRoot(p) holds in γ ′ . Otherwise q executes R-action or J-action. Then γ ′ (q).status = C, so ¬GoodStatus(p, q) and AbRoot(p) holds in γ ′ .

If γ(p)

.idR ≥ p, the idR is not modified during the step, so γ ′ (p).idR = γ(p).idR ≥ p and AbRoot(p) holds in γ ′ .

• ¬GoodLevel(p, q) holds in γ so γ(p).idR = γ(q).idR but γ(p).level = γ(q).level + 1. First, if q executes EB-action or EF -action, its idR and its level do not change, so γ ′ (p).idR = γ ′ (q).idR and γ ′ (p).level = γ ′ (q).level+1, so AbRoot(p) holds in γ ′ . Otherwise, q executes R-action or J-action and consequently γ ′ (q).status = C. So ¬GoodStatus(p, q) and AbRoot(p) holds in γ ′ .

• ¬GoodStatus(p, q) holds in γ. Then γ(q).status = C, and q can only execute EB-action or J-action between γ and γ ′ . If q executes EB-action, then EBroadcast(q) holds in γ, so q is in an abnormal tree (Lemma 8). But, by hypothesis, all abnormal trees are dead in γ, so γ(q).status = C, a contradiction. If q executes J-action then γ ′ (q).status = C, so ¬GoodStatus(p, q) and AbRoot(p) holds in γ ′ .

Thus, γ ′ (p).status = EF and AbRoot(p) holds in γ ′ and, consequently, Allowed(p) is false in γ ′ . So ∃q ∈ N p such that q ∈ Children p ∧¬KinshipOk(q, p) holds in γ ′ but γ ′ (q).status = C. Two cases are possible:

• If q /
∈ Children p in γ, then q executes J-action during the step γ → γ ′ and M in q = p. But γ(p).status = EF , a contradiction.

• Otherwise q ∈ Children p in γ and γ(q).status = C. q executes either EF -action and γ ′ (q).status = EF , or R-action and γ ′ (q).par = p, so q / ∈ Children p in γ ′ , a contradiction.

Definition 13 (Abnormal process). A process p is said to be abnormal if and only if p belongs to an abnormal tree. p is said to be normal, otherwise.

As no process can join a dead abnormal tree (Remark 1) and, by Lemma 3, no alive abnormal tree can be created, we have the following remark: Remark 6. In a configuration where every abnormal tree is dead, the number of abnormal processes can only decrease. Theorem 7. Starting from a configuration where every abnormal tree is dead and the status of their roots is EF , there is no more abnormal processes in at most n rounds.

Proof. Let γ 0 be a configuration where all abnormal trees are dead and the status of their roots is EF . By Observation 1, all abnormal processes have status EF in γ 0 . So, from γ 0 , no process can be ever an abnormal process with a status different of EF (such a process can only execute R-action, then it is a normal process forever, by Lemma 3). Then, by definition, the number of abnormal processes in γ 0 is at most n. Moreover, by Remark 6, it is sufficient to show that in any configuration γ k reachable from γ 0 , if the number of abnormal processes is not null, then at least one of them becomes normal within the next round.

So, let assume that some process p is abnormal in γ k . Then, γ k (p).status = EF . By Observation 1 and Lemma 20, the initial extremity r of KP ath(p) is an abnormal process (of status EF ) and executes R-action within the next round. After executing R-action, r is normal (actually, r becomes a self root), and we are done.

By definition, the root of a normal tree has status C. So, by Observation 1, we have: Remark 7. Every process has status C in a configuration containing no abnormal processes. Moreover, this configuration is clean.

Using Lemma 17 and Theorems 5 to 7, we can conclude: Theorem 8. In at most 3n rounds, the system reaches a clean configuration.

Then, using Theorems 4 and 8 we get: Theorem 9 (Round Complexity). In at most 3n + D rounds, the system reaches a terminal configuration.

0, n-2 0, j-2 0, 3 0, 2 0, 1 (a)
The initial configuration. {p 2 , p j } is the "last" edge to p 2 (j = k + 3).

0, n-2 0, j-2 0, 3 0, 2 3, 0 (d)
0, n-2 0, j-2 0, 3 4, 0 2, 1 (e)
p 3 executes J-action and p 4 simultaneously executes R-action.

1, 0 0, n-k-2 2, 1 2, 1 2, 1 2, 1 (f)
In n -3 rounds, the cleaning is finished.

2 1 n . . . j . . . 5 4 3 2, 0 1, 0 1, 1 1, n-k-2 2, 1 2, 1 2, 1 (g
) In n -k -2 rounds, processes n to k -3 joins T ree(1). 2 1 n . . . j . . . 5 4 3 1, n-k-1 1, 0 1, 1 0, n-k-2 2, 1 2, 1 2, 1 (h)
Processes p 2 and p k-2 simultaneously execute J-action.

2 1 n . . . j . . . 5 4 3 1, n-k-1 1, 0 1, 1 0, n-k-2 1, n-k 1, n-k 1, n-k (i)
In one round, the system reaches a terminal configuration where p 1 is the leader. Lower Bound on the Worst Case Stabilization Time in Rounds. We now show that the bound proposed in Theorem 9 cannot be improved. To see this, we exhibit a construction that gives, ∀n ≥ 4, ∀D, 2 ≤ D ≤ n -2, a network of n processes whose diameter is D from which there is a possible synchronous execution that lasts exactly 3n + D rounds. (Recall that every synchronous execution is possible under the distributed unfair daemon.)

We consider a network G = (V, E) composed of n processes V = {p 1 , . . . , p n } such that p i has ID i, for i ∈ {1, . . . , n}. Figure 8a shows the system in its initial configuration. In details, processes p 1 , p n , . . . ,p 2 form a chain, i.e., {p 1 , p n } ∈ E and {p i , p i-1 } ∈ E, ∀i ∈ {3, . . . , n}.

We add k edges to p 2 , with 2 ≤ k ≤ n -2, as follows:

If k = n -2, {p 2 , p 1 } ∈ E and for ∀i ∈ {4, . . . , n}, {p 2 , p i } ∈ E, Otherwise ∀i ∈ {4, . . . , k + 3}, {p 2 , p i } ∈ E.
Notice that the diameter of the network is nk and can be adjusted by adding or removing some edges to p 2 . We assume the following initial configuration:

• p i .idR = 0, ∀i ∈ {1, . . . , n},
• p 1 .level = n -1 and p 1 .par = p n ,

• p 2 .par = p 2 and p 2 .level = 0,

• p i .level = i -2 and p i .par = p i -1, ∀i ∈ {3, . . . , n}.
We consider a synchronous daemon, i.e., in a configuration γ, every process in Enabled(γ) is selected by the daemon to execute an action. So, in this case, every round lasts exactly one step.

The execution is then as follows:

• p 2 , p 3 , p 4 , . . . , p n , p 1 sequentially execute EB-action: n rounds. (See Figure 8b.)

• p 1 , p n , p n-1 , . . . , p 2 sequentially execute EF -action: n rounds. (See Figure 8c.)

• p 2 and p 3 sequentially execute R-action: 2 rounds. (See Figure 8d.)

• For i = 4, . . . , n, simultaneously p i and p i-1 respectively executes R-action and J-action, in particular, p i-1 joins T ree(p 2 ): n -3 rounds. (See Figures 8e and8f.)

• p 1 executes R-action and p n executes J-action simultaneously: 1 round.

• For i = n, . . . , k +3, i executes J-action to join T ree(1): n-k -2 rounds. (See Figure 8g.)

• p 2 and p k+2 simultaneously execute J-action to join T ree(1): 1 round. (See Figure 8h.)

• p 3 , . . . , p k+1 simultaneously execute J-action and then the configuration is terminal: 1 round. (See Figure 8i.)

Hence, the execution lasts exactly 3n + (nk) = 3n + D rounds. Using Theorem 9 we can conclude:

Theorem 10. In the worst case, the round complexity of LE is exactly 3n + D rounds. Lower Bound on the Worst Case Stabilization Time in Steps. We show that the bound given in Theorem 1 can be asymptotically matched, i.e., we give an example of possible execution that stabilizes in Ω(n 3 ) steps, for every n ≥ 4.

We consider a network G = (V, E) composed of n processes V = {p 1 , . . . , p n } such that p i has ID n + i, ∀i ∈ {1, . . . , n}. Figure 9a shows the network in this initial configuration. In details, there are 2n-3 edges: {p i , p i+1 } for i ∈ {1, . . . , n-2} and {p i , p n } for i ∈ {1, . . . , n-1}. (Notice that the diameter of this network is 2.) The initial configuration is as follows:

• p i .idR = i, ∀i ∈ {1, . . . , n -1}, and p n .idR = 2n.

• p i .par = p i , p i .level = 0 and p i .status = C, ∀i ∈ {1, . . . , n}.

We consider the following execution:

• For i = n -1, n -2, . . . , 1, we clean T ree(p i ) the following way:

1. If i ≤ n -2, for j = n -2, n -1, . . . , i, (a) For k = j + 1, j + 2, . . . , n -1, p k joins T ree(p j ). Case 1 lasts n-1-i j=1 j = (n -i -1)(n -i)/2 steps.
2. p i , p i+1 , . . . , p n-1 sequentially execute EB-action: ni steps.

3. p n-1 , p n-2 , . . . , p i sequentially execute EF -action: ni steps.

4. p i , p i+1 , . . . , p n-1 sequentially execute R-action: ni steps.

Figures 9e to 9h show the cleaning of T ree(p n-3 ).

• After all abnormal trees have been cleaned, processes p n-1 to p 2 join T ree(p 1 ) similarly as Case 1:

n-2 j=1 j = (n -1)(n -2)/2 steps (Figure 9j).

• p n executes J-action to join T ree(p 1 ): 1 step (Figure 9k).

Hence, the complete execution lasts:

3 + n-2 i=1 3(n -i) + (n -i -1)(n -i) 2 + (n -1)(n -2) 2 + 1 = n 3 6 + 3 2 n 2 - 8 3 n + 2 steps
So, there exists an execution in Ω(n 3 ). Using Theorem 3, we can conclude:

Theorem 11. In the worst case, the step complexity of LE is in Θ(n 3 ) steps.

Step Complexity of Algorithm DLV

In this section, we study the step complexity of the algorithm given in [START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF], called here DLV. 2 Below, we show that its stabilization time is not polynomial in steps. First, we give the code of algorithm DLV and an informal explanation of its main principles in Subsection 5.1. Then, we give in Subsection 5.2 an example of a class of network in which there is a possible execution that stabilizes in Ω(n 4 ) steps. Finally, in Subsection 5.3, we generalize the previous example to a class of network where there is a possible execution that stabilizes in Ω(n α ) for any α ≥ 4.

Algorithm 2 Algorithm DLV [START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF] ≡ p.leader, p.level + 1 BestN brKey(p) ≡ min{q.key | (q ∈ N p ) ∧ (SuccKey(q) < Self Key(p)) ∧(q.color = 2)} T rueChldrn(p) ≡ {q ∈ N p | (q.parent = p) ∧ (q.key = SuccKey(p))} F alseChldrn(p) ≡ {q ∈ N p | (q.parent = p) ∧ (q.key = SuccKey(p))} Recruits

Actions

J (priority 1) :: Join(p, q) → p.key ← SuccKey(q); p.parent ← q; p.color ← (a) 7 can execute C2 action and get color 2.

Overview of DLV

The formal code of Algorithm DLV is given in Algorithm 2. This algorithm uses priorities. Each of its actions is given with priority number. When an enabled process is selected by the daemon, it only executes its enabled action with the lowest priority number. Algorithm DLV elects the process of minimum ID, ℓ, and builds a breadth-first spanning tree rooted at ℓ. To ensure that every process knows which one is elected, it maintains a variable leader in which is saved the alleged leader. Variables parent and level are used to define the tree. The key of a process p is the combination of its two variables p.leader and p.level. Notice that the keys are ordered using the classical lexical order.

Let p be a process. Let q be its neighbor of smallest key (BestN brKey(p)). Suppose the key of process p is not the immediate successor of the q's key or p.parent = q. p may execute action J to modify its key and its parent pointer accordingly. Notice that, contrary to our algorithm, p can execute action J and change its parent when there is a neighbor with the same leader but with a level smaller than p.level -1, in order to build a breadth-first spanning tree. Note also that the execution of Action J is constrained by the use of a color, whose goal will be explained later.

As in LE, Datta et al define a "good relation" between a process p and its parent: IsT rueChld(p). This ensures that the key of p is the successor key of its parent and that its leader is smaller than its own ID. Then, a maximal set of processes linked by parent pointers and satisfying the IsT rueChld relation defines a tree. The root of a tree can be a true root (IsT rueRoot(p)), i.e., the key of p is a self key ( p, 0 ). In this case, the tree is said to be normal. Otherwise, the root is a false root (IsF alseRoot(p)), i.e., neither a true root nor a true child, and the tree is said to be abnormal.

Color waves

The main difference between DLV and LE is the way to deal with these abnormal trees. Instead of using a status and a three-waves cleaning, DLV uses color waves. More precisely, each process has a variable color, whose value is either 1 or 2. A process can only choose as parent a neighbor of color 2 and after executing action J, the process gets color 1.

A process can change its color, by executing actions C1 or C2, if it has the same color than its parent (it is trivially satisfied for every true root) and if all of its true children have the other color (see Figure 10). There is an additional constraint to change a color to 1: as a process cannot recruit when it has color 1, a process p of color 2 must not change its color while it can recruit processes (while Recruits(p) = ∅).

To add a new level in the tree, the leaves must change their color to 2. Then, the goal is to propagate up in the tree a first wave of actions C1 initiated by the parents of the leaves, so that a second wave of actions C2 can be initiated by the leaves. To ensure that, the root should absorbed a (previous) wave. But, only a true root can absorb a color wave. Indeed, the priorities on actions prevent a false root to change its color (before it resets) and, so, to absorb a color wave.

Therefore, the colors of the processes in an abnormal tree eventually alternate, i.e., the parents and their true children do not have the same color, and no more process can join the tree: the tree is color locked. Then, the false root eventually resets by executing action R, and so forth. Once all abnormal trees have been removed, ℓ is a true root and regularly absorb color waves allowing then the leaves of its tree to recruit processes.

Finally, in O(n) rounds, ℓ is elected and a breadth-first spanning tree rooted at ℓ is built. Notice that the color waves might never end. So, an additional mechanism allow to ensure the silence by using a Boolean variable done and action U D. When a process p believes that the construction of the final tree is finished (because it cannot recruit processes anymore) and all its true children q (if any) have set their variables q.done to true, p.done is set to true. Moreover, a true root r cannot change its color once r.done holds. In this case, we said that r is color frozen. Thus, after the completion of the final tree construction, the value true is propagated up in the tree into the done variables, and in O(D) rounds, the system reaches a terminal configuration.

Example of execution Figure 11 shows an example of execution of DLV (for sake of simplicity, we do not consider the done variables and actions U D in this example). In the initial configuration (Configuration a), the leader of process 7 is 1, the only fake id. Moreover, 5 has already chosen 7 as parent. Then, in step a → b, 2 and 3 execute action J and choose 7 (of color 2) as parent. Note also that 5 has the same color than its parent (7), has no true child, and cannot recruit any other process. So 5 executes action C1 and gets color 1 in b → c. No more process can join the tree rooted at 7 and the tree is color locked (7 is a false root and cannot change its color), so 7 resets during c → d. In Configuration d, 2, 3 and 5 are false roots. In d → e they execute action R in turns. Then, in e → f, processes 4, 5, 6, 7, and 8 execute action J to choose 2 as parent. In Configuration f, 3 cannot join the tree rooted at 2 because all its neighbors have color 1. 2 changes its color to 1 by executing action C1 in f → g. Then, processes 4, 5, 6, 7, and 8 get color 2 by executing action C2 in g → h. Finally, 3 is allowed to execute action J and joins the tree rooted at 2 in h → i.

Example in Ω(n 4 ) steps

First, we show an execution of DLV that last Ω(n 4 ) steps.

Network and initial configuration

We consider a network made of n = L × β processes with L = 8 and β ≥ 2: p (1,1) , p (1,2) , . . . , p (1,β) , p (2,1) , p (2,2) , . . . , p (2,β) , . . . , p (8,1) , p (8,2) , . . . , p (8,β) such that the ID of p (i,j) is (i -1)β + j, ∀i ∈ {1, . . . , 8}, ∀j ∈ {1, . . . , β}. Notice that 0 is a fake ID smaller than every ID in the network.

Figure 12a shows the structure of the network and the initial configuration. In details, the processes form β columns: ∀i ∈ {2, . . . , 8}, ∀j ∈ {1, . . . , β}, {p (i-1,j) , p (i,j) } ∈ E.

There are also three complete bipartite subgraphs: ∀j, j ′ ∈ {1, . . . , β}, j ′ = j, {p (4,j) , p (5,j ′ ) } ∈ V, {p (6,j) , p (7,j ′ ) } ∈ E and {p (7,j) , p (8,j ′ ) } ∈ E These bipartite subgraphs split the network in four layers: We choose the following initial configuration.

• For i ∈ {1, . . . , 8}, for j ∈ {1, . . . , β}, p (i,j) .leader = 0, p (i,j) .level = i and p (i,j) .done = false

• For j ∈ {1, . . . , β}, -p (1,j) .parent = p (1,j)

p (5,j) .parent = p (4,1)

p (7,j) .parent = p (6,1)

p (8,j) .parent = p (7,1)

-For i ∈ {2, 3, 4, 6}, p (i,j) .parent = p (i-1,j)

• For i ∈ {1, . . . , 8}, p (i,1) .color = (i mod 2) + 1

• For j ∈ {2, . . . , β}, -p (8,j) .color = 1

-For i ∈ {1, . . . , 7}, p (i,j) .color = 2

Overview of the execution We first give an illustrative execution to understand the Ω(n 4 ) lower bound.

We start with Configuration a of Figure 12. Starting from this configuration, all the processes of the first column and of the last line successively reset. We obtain configuration b. This costs at least β steps (since the reset of the last line can be sequential). Then, all processes p (8,.) can join p (7,2) (which has the fake id 0 as leader). This leads to Configuration c. Then, we can reset p (7,2) and the last line (at least β steps). Again processes p (8..) can join p (7,3) and we can reset, etc., until we reset p (7,β) and the last line to obtain Configuration d. Overall, this costs at least β 2 steps.

From Configuration d, we can rebuilt the tree on p (6,2) . The tree is shown in Configuration e, and we can reset the processes following the order given by the arrow in Configuration e. We obtain Configuration f. Again we can start the succession of buildings and resets bottom-up just as before, but this time, until resetting a tree rooted at p (5,β) (Configuration g). This costs at least β 3 steps.

From Configuration g, we can rebuild a tree on the second column until reaching Configuration h . This latter is similar to the first one, Configuration a. The only difference is that the main tree is now rooted at p (1,2) instead of p (1,1) . We can repeat the same scheme on each column. This leads to an execution of at least β 4 steps. Execution in details Now, let see the details of the execution. We consider an unfair daemon which selects the enabled processes according to the function Daemon given in Algorithms 3 and 4. In this algorithm, top(i) (respectively bottom(i)) is the number of the first line (respectively last line) of layer i. More precisely:

top(i) = L -2 i-1 + 1 bottom(i) = top(1) if i = 1 top(i -1) -1 if i > 1
In Build(layer, column), all the processes of lines top(layer) to 8 execute line by line action J. Notice that every process of line top(layer) chooses the process p (top(layer)-1,column) as parent.

In Reset(layer, column), all the processes on column column from the one on line top(layer+ 1) to the one on line bottom(layer + 1) execute action R (except for layer 1 where all the processes of line 8 also execute action R). Then, Reset(layer -1, i) and Build(layer -1, i + 1) are called for each column i = 1, . . . , β -1. Finally, Reset(layer -1, β) is executed.

We count how many times processes p (8,.) executes action R:

• Each process p (8,.) executes once action R on line 15 of Algorithm 3 in function Reset(layer, column), when layer = 1: at least β processes execute action R. Hence, action R is executed β 4 times by the processes of line 8. Now, β = n/8. Hence we can conclude:

Theorem 12. For every β ≥ 2, there exists a network of n = 8 × β processes in which there exists a possible execution that stabilizes in Ω(n 4 ) steps.

Generalization to an example in Ω(n α ) steps

We note E 4 the graph built for the example in Ω(n 4 ) steps and shown in Figure 12a. Then, starting from E α-1 (α ≥ 5), we can build E α , a graph for which there exists an execution in Ω(n α ) steps. The construction is based on the same principle as in Subsection 5.2, by adding a layer.

If E α-1 has Lβ processes p (i,j) (1 ≤ i ≤ L, 1 ≤ j ≤ β), then E α has L ′ = 2L lines of β processes q (i ′ ,j ′ ) (1 ≤ i ′ ≤ L ′ , 1 ≤ j ′ ≤ β).
The construction principle is as follows:

1. We increase the level and the ID of the Lβ processes of E α-1 as follows: ∀i ∈ {1, . . . , L}, ∀j ∈ {1, . . . , β}, q (i+L,j) = p (i,j) . The ID of q (i+L,j) becomes (i + L -1)β + j and q (i+L,j) .level = i + L. The value of variables color and done do not change. If i = 1, the parent remains the same. Otherwise, see step 3.

2. At the top of E α-1 , we add L lines of β processes. These new processes satisfy:

• ∀i ∈ {1, . . . , L}, ∀j ∈ {1, . . . , β}:

q (i,j) .id = (i -1)β + j q (i,j) .leader = 0 -q (i,j) .level = i -q (i,j) .done = false

• ∀i ∈ {2, . . . , L}, ∀j ∈ {1, . . . , β}, {q (i-1,j) , q (i,j) } ∈ E and q (i,j) .parent = q (i-1,j)

• ∀j ∈ {1, . . . , β}, q (1,j) .parent = q (1,j)

• ∀j ∈ {2, . . . , β}, ∀i ∈ {1, . . . , L}, q (i,j) .color = 2

• ∀i ∈ {1, . . . , L}, q (i,1) .color = (i mod 2) + 1

3. The former first line of E α-1 becomes a new bipartite complete subgraph with the last added line:

• ∀j ∈ {1, . . . , β}, ∀j ′ ∈ {1, . . . , β}, {q (L,j) , q (L+1,j ′ ) } ∈ E

• ∀j ∈ {1, . . . , β}, q (L+1,j) .parent = q (L,1)

Figure 13 shows the structure of the network for E 5 and its initial configuration.

In the execution, the daemon selects processes according to function Daemon(α) (see Algorithm 5) which is the generalization of the algorithm presented in Section 5.2. In E α-1 , processes p (L,.) execute β α-1 times action R. Now, we added a new level of recursion. Then, processes q (L ′ ,.) execute β α times action R. As β = n L ′ , the execution lasts Ω(n α ) steps. Hence, we obtain: Theorem 13. For every α ≥ 4, for every β ≥ 2, there exists a network E α of n = 2 α-1 × β processes in which there exists a possible execution that stabilizes in Ω(n α ) steps.

Algorithm 5 Generalization of the algorithm of the daemon for E α . for i = 1 . . . β, (i + +) do 3:

Reset(α -1,i); ⊲ See Algorithm 3 4:

if i < β then 5:

Build(α -1,i+1); ⊲ See Algorithm 4 6: end if 7:

end for 8: end function

We proved that for E α of size n = L × β (β ≥ 2, α ≥ 4 and L = 2 α-1 ), the execution in Algorithm 5 stabilizes using at least β α steps. For a fixed size n of network, the value β α may vary, depending on e.g. L. For instance, for L = n/2, we have that α = log 2 n and β = 2 which implies that β α = n. At the opposite of the interval of L (second example), when L = 8, we have α = 4 and β = n × 2 -3 . Hence, in this case, β α = 2 × n 4 . Both costs obtained in those examples are polynomial. But, between them, the function reaches higher values: the following corollary shows that the highest value of β α is reached for L = n 2 and is non-polynomial. Proof. We show below that for every α ≥ 4, for every β ≥ 2, there exists a network of size n = 2 α-1 × β for which there exists an execution which stabilizes in Ω 2n

Experimentations

We ran simulations to empirically evaluate and compare the average stabilization times of our algorithm LE and Algorithm DLV in terms of steps and rounds.

Probabilistic Daemon We use an event-driven homemade simulator dedicated to the locally shared memory model. In this simulator, we use a probabilistic daemon. To enforce asynchronism (i.e., to maximize interleavings between actions at different processes), we implemented the daemon as follows: at each step, the probability that an enabled process is selected by the daemon follows an exponential distribution on the number of consecutive steps where the node was enabled yet not selected.

UDG In our experiments, we consider a particular family of random graphs: the Unit Disk Graphs (UDGs) [START_REF] Mark | Broadcast Scheduling Algorithms for Radio Networks[END_REF]. Such graphs are generated as follows. First, nodes are deployed on a square plane uniformly at random. Then, two nodes are neighbors if and only if their Euclidean distance is smaller than a pre-defined radius. UDGs are commonly used to model wireless sensor networks. Indeed, sensors are motionless and equipped with radio. In this case, the pre-defined radius represents the range of radio antenna.

Arbitrary Initial Configuration

In each experiment, the initial configuration is randomly generated. First, each process selects its unique ID in {1, ..., 2n} uniformly at random. Then, the initial value of each idR variable (resp. leader variable in Algorithm DLV) is chosen in {1, ..., 2n} uniformly at random. So, with probability 1 2 , the initial value of idR (resp. leader in Algorithm DLV) is a fake id. Moreover, the way IDs and idR (resp. leader in Algorithm DLV) are set allows the existence of fake IDs lower than the lowest "real" ID of the network.

Then, the initial value of each par pointer is chosen among the ID of the node and the IDs of its neighbors uniformly at random. The initial value of each level variable is chosen in {0, ..., n -1} uniformly at random. Finally, the initial value of all other variables (i.e., status in LE, and color and done in DLV) are chosen uniformly at random in their respective (finite) domain.

Average Stabilization Time in Rounds

In this subsection, we study the stabilization time in rounds. To that goal, we generated a pool of 220 UDGs. Each of those contains n = 1000 nodes. However, we make varying the diameters from 4 and 24 (20 graphs per diameter). We repeatedly executed each algorithm (LE and DLV) on each graph with arbitrary initializations until obtaining a confidence interval smaller than 2% of the average stabilization time.

Results are shown on Figure 14. We can remark that the average stabilization time in rounds of LE is far from the analytical worst case (i.e., 3n + D rounds). Actually, we never observed an execution whose stabilization time matches the worst case. The average stabilization time in rounds of the two algorithms is sub-linear in n. However, in our experiments, our algorithm outperforms DLV. Finally, we draw the diameter in the Figure to show that the observed average stabilization time in rounds of LE is of the order of magnitude of the diameter D.

Average Stabilization Time in Steps

In this subsection, we study the average stabilization time in steps. To that goal, we generated a pool of 110 UDGs with diameter fixed to 14, yet where the number of nodes varies from 100 to 1000 (10 graphs per size). We repeatedly executed each algorithm (LE and DLV) on each graph with arbitrary initializations until obtaining a confidence interval smaller than 2% of the average stabilization time in steps.

Results are shown on Figure 15. Again, we can remark that the average stabilization time in steps of LE is far from the analytical worst case (i.e., Θ(n 3 ) steps). Again, we never observed an execution whose stabilization time matches the worst case. Again, in our experiments, LE outperforms DLV, even though their respective average stabilization times in steps are of the same order of magnitude. Finally, we draw the size n of the network in the Figure to show that the observed average stabilization times in steps of both solutions do not depend on n.

Conclusion

We proposed a silent self-stabilizing leader election algorithm, called LE, for bidirectional connected identified networks of arbitrary topology. Starting from any arbitrary configuration, LE converges to a terminal configuration, where all processes know the ID of the leader, this latter being the process of minimum ID. Moreover, as in most of the solutions from the literature, a distributed spanning tree rooted at the leader is defined in the terminal configuration.

LE is written in the locally shared memory model. It assumes the distributed unfair daemon, the most general scheduling hypothesis of the model. Moreover, it requires no global knowledge on the network (such as an upper bound on the diameter or the number of processes, for example). LE is asymptotically optimal in space, as it requires Θ(log n) bits per process, where n is the size of the network. We analyzed its stabilization time both in rounds and steps. We showed that LE stabilizes in at most 3n + D rounds, where D is the diameter of the network. We also proved that for every n ≥ 4, for every D, 2 ≤ D ≤ n -2, there is a network of n processes in which a possible execution exactly lasts this complexity.

Finally, we proved that LE achieves a stabilization time polynomial in steps. More precisely, its stabilization time is at most n 3 2 + 2n 2 + n 2 + 1 steps. Then, we showed for every n ≥ 4, that there exists a network of n processes in which a possible execution exactly lasts n 3 6 + 3 2 n 2 -8 3 n+2

  Initial configuration. Self Root(p) ∧ Self RootOk ′ (p) holds for every process p.

  4, 5, 6, and 7 have executed J-Action ′ . Note that J-Action ′ was not enabled at 2 because it is a local minimum.

  2, 3, and 4 have executed J-Action ′ .

  6 has executed J-Action ′ . The configuration is now terminal, ℓ = 1 is elected, and a tree rooted at ℓ is available.

Figure 1 :

 1 Figure 1: Example of execution of the non self-stabilizing algorithm. Process identifiers are given inside the nodes. x, y means idR = x and level = y. Arrows represent par pointers. The absence of arrow means that the process is a self root.

  Illegitimate initial configuration, where 2 and 5 have fake idR.

  4 executed J-Action ′ . The configuration is now terminal.

Figure 2 :Figure 3 :

 23 Figure 2: Example of execution that does not converge to a legitimate configuration.

  the tree. 3 leaves it.

  the tree. 4 leaves it.

  Its children become themselves abnormal roots of dead trees and can execute R-action: 2 and 8 can clean because their status is EF and their parent has status C.

Figure 5 :

 5 Figure 5: Schematic example of the cleaning mechanism. Trees are filled according to the status of their processes: white for C, dashed for EB, gray for EF .

  9 are abnormal roots. If 4 executes R-action before 9 executes EB-action, the kinship relation between 4 and 9 becomes correct and 9 is no more an abnormal root. Then, EB-action is no more enabled at 9.

  an abnormal root and M in 4 is 6. If 4 executes J-action before 9 executes EB-action, the kinship relation between 4 and 9 becomes correct and 9 is no more an abnormal root. Then, EB-action is no more enabled at 9.

Figure 6 :

 6 Figure 6: Example of situations where the parent of a process is locked.

Definition 6 (Observation 1 .

 61 S-Trace). For some configuration γ, for a sequence of processes p 0 , p 1 , . . . , p k , we define: S-T race(p 0 , p 1 , . . . , p k ) ∈ {C, EB, EF } * as the sequence (p 0 .status).(p 1 .status) . . . (p k .status) in γ. For any configuration, we have: ∀p ∈ V, S-T race(KP ath(p)) ∈ EB * C * ∪ EB * EF * . Proof. Let p be a process. If |KP ath(p)| = 1, Observation 1 trivially holds. For |KP ath(p)| ≥ 2, assume by contradiction that S-T race(KP ath(p)) / ∈ EB * C * ∪ EB * EF * . Then, ∃s, f ∈ KP ath(p) such that s.par = f and S-T race(f, s) ∈ {C.EB, C.EF, EF.EB, EF.C}. In all cases, ¬GoodStatus(s, f ) holds which in turns implies that ¬KinshipOk(s, f ). This contradicts Definition 4.

Figure 7 :

 7 Figure 7: Segments of execution

Figure 7 illustratesLemma 4 .

 74 Figure 7 illustrates Definition 11. We now show that the number of segments is finite.Lemma 4. There are at most n + 1 segments in any execution.

Corollary 3 .

 3 In any execution, a process can execute EB-action and EF -action at most n times, each.By Corollaries 2, 3, and Lemma 11:Theorem 1 (Convergence). Every execution contains at most n 3 2 + 2n 2 + n 2 + 1 steps.

Corollary 4 .Theorem 4 .

 44 A clean configuration where ∀p ∈ V, p.idR = ℓ, is terminal. In a clean configuration, the system reaches a terminal configuration where ∀p ∈ V, p.idR = ℓ in at most D rounds.

  Hence, |KP ath(q)| > d in γ j+1 and consequently, |KP ath(p)| > d + 1 in γ j+1 , a contradiction. Hence, ∀p ∈ V , if (p.status = C ∧ |KP ath(p)| ≤ d + 1) is false in some configuration γ i with i ≥ R d , then (p.status = C ∧ |KP ath(p)| ≤ d + 1) remains false forever. Now, EB-action is continuously enabled ∀p such that p is alive |KP ath(p)| = d + 1 in γ R d (by induction hypothesis and Lemma 18). So, p becomes dead during the round and, ∀j ≥ R d+1 , γ j contains no alive process p such that |KP ath(p)| ≤ d + 1.

  In n rounds, the EB-wave reaches p 1 .

  In n rounds, p 2 gets status EF .

p 2 and p 3

 3 sequentially execute R-action.

Figure 8 :

 8 Figure 8: An example in 3n + D rounds

  p n-1 executes J-action and joins T ree(p n-2 ) p n-1 executes J-action and joins the normal tree T ree(p n-2 ) p n-2 executes J-action and joins the abnormal tree T ree(p n-3 ) p n-1 executes J-action and updates its idR to n -3.

  In nine steps, the abnormal tree rooted in p n-3 is cleaned In one step, the system reaches a terminal configuration where p 1 is leader.

Figure 9 :

 9 Figure 9: An example in Ω(n 3 ) steps

  (p) ≡ {q ∈ N p | q.key > SuccKey(p)} Predicates IsT rueRoot(p) ≡ p.key = Self Key(p) IsT rueChld(p) ≡ (p.key = SuccKey(p.parent) ∧ (p.leader < p) IsF alseRoot(p) ≡ ¬IsT rueRoot(p) ∧ ¬IsT rueChld(p) Done(p) ≡ (Recruits(p) = ∅) ∧ (∀q ∈ T rueChldrn(p), q.done) ColorF rozen(p) ≡ IsT rueRoot(p) ∧ p.done Guards Join(p, q) ≡ (IsF alseRoot(p) ∨ (SuccKey(q) < p.key)) ∧ (q.color = 2) ∧(q.key = BestN brKey(p)) ∧ (F alseChldrn(p) = ∅) Reset(p) ≡ IsF alseRoot(p) Color1(p) ≡ (p.color = 2) ∧ ¬ColorF rozen(p) ∧ (p.parent.color = 2) ∧(Recruits(p) = ∅) ∧ (∀q ∈ T rueChldrn(p), q.color = 1) Color2(p) ≡ (p.color = 1) ∧ ¬ColorF rozen(p) ∧ (p.parent.color = 1) ∧(∀q ∈ T rueChldrn(p), q.color = 2) U pdateDone(p) ≡ p.done = Done(p)

  execute C1 action and get color 1.

Figure 10 :

 10 Figure 10: Guards of color actions. The ID is represented inside the node. The label next to a node shows its key. The arrows represent parent pointers. No arrow exits a node if its parent is itself. The filling represents the color: gray for 1 and white for 2.

Figure 11 : 8 • 7 • 6 •

 11876 Figure 11: Example of execution of algorithm DLV.

1 :

 1 function Daemon(α) 2:

Corollary 5 . 1 4

 51 The stabilization time of Algorithm DLV is in Ω 2n log 2 (2n) steps.

1 4 log 2

 12 (2n) steps. Let β, α and L be positive integers such that n = L × β, β ≥ 2, α ≥ 4, and L = 2 α-1 (as for Theorem 13). The value of the function β α reaches its maximum when L = n 2 , β = √ 2n and α = 1 2 (log 2 n + 1). (This can be easily proved by cancellation of the derivative of β α w.r.t. L.) In this case, β α equals (2n)

1 4

 1 log 2 (2n) , and we are done.

* 4 L

 4 Processes of E α-1 = E = 8 new linesE α = E 5 L ′ = 2L = 16

Figure 13 :

 13 Figure 13: Initial configuration of the example in Ω(n 5 ) steps.

Figure 14 :

 14 Figure 14: Average stabilization time in rounds for LE and DLV on UDGs (n = 1000).

  . Again, 3 and 4 can detect the problem. Indeed, predicate GoodIdR(p, p.par) ∧ GoodLevel(p, p.par) is violated by both 3 and 4. In this example, after 3 and 4 have reset, all inconsistencies have been removed. So let define the following action:

	R-Action ′ :: Self Root(p) ∧ ¬Self RootOk ′ (p) ∨ ¬Self Root(p) ∧¬(GoodIdR(p, p.par) ∧ GoodLevel(p, p.par)) → p.par ← p; p.idR ← p; p.level ← 0;

  1 Algorithm LE for every process p Variables p.idR ∈ N, p.par ∈ N p ∪ {p}, p.level ∈ N, p.status ∈ {C, EB, EF }

	Macros
	Children p

  -where p is enabled to switch its status from C

	EB-action		1, 0
				6
	C		2	8	EB
			1, 1	1, 1	C
					EF -action
	(a) When an abnormal root detects an error, it	(b) When the EB-wave reaches a leaf, it exe-
	executes EB-action. The EB-wave is broadcast	cutes EF -action. The EF -wave is propagated
	to the leaves. Here, 6 is an abnormal root be-	up to the root.
	cause it is a self root and its idR is different from
	its ID (1 = 6).
			1, 4	5
	EB	4	9
	C	EF		7

  if p belongs to an abnormal tree and |KP ath(p)| ≤ d in γ i , then p is dead in γ i . Assume by contradiction that the predicate (p.status = C ∧ |KP ath(p)| ≤ d + 1) is false in γ j , but true in γ j+1 (j ≥ i). By induction hypothesis, |KP ath(p)| = d + 1 > 1 in γ j+1 (indeed, p is alive in γ j+1

Induction

Step: We first show that for every p ∈ V , for every

i ≥ R d , if (p.status = C ∧ |KP ath(p)| ≤ d + 1

) is false in configuration γ i , then for every j ≥ i, (p.status = C ∧ |KP ath(p)| ≤ d + 1) is false in configuration γ j .

  1. If L(p) = d and γ R d (p).status = EB, then ∀q ∈ RealChildren p in γ R d , L(q) < d by definition and γ R d (q) .status = EB by induction hypothesis. Now, the trees are dead, so γ R d (q).status = EF . Hence, EF -action is enabled at p in γ R d . By Lemma 19, p executes EF -action during the round and gets status EF . Then, p.status = EB forever (Claim 1), so EBL(p, d) is false at the end of the d + 1th round and remains false forever. 2. If L(p) = d and γ R d (p).status = EB, then, using Claim 1, p.status = EB forever. So, EBL(p, d) is false forever. 3. If L(p) < d, γ R d (p).status = EB by induction hypothesis and we conclude as in case 2. 4. If EBL(p, k) holds in γ R d with k > d, EBL(p, i) is false forever ∀i ≤ d (Claim 2). With d = n, we have ∀i ≥ R n , ∀p ∈ V , ∀k ≤ n -1, EBL(p, k) is false in γ i : hence, in at most n rounds, there is no more process of status EB in abnormal trees, those ones being dead. So, all processes (and in particular the abnormal roots) in abnormal trees have status EF .

  for every process p Variables p.leader ∈ N, p.level ∈ N, p.key = p.leader, p.level , p.parent ∈ N p ∪ {p} p.color ∈ {1, 2}, p.done ∈ B

	Macros Self Key(p) SuccKey(p)	≡ p, 0

We only consider here deterministic algorithms.

DLV stands for "Datta, Larmore, and Vemula."

1,β 2,β 3,β 4,β 5,β 6,β 7,β 8,β * * * * * * * * * * * * * * (b) 1,1 2,1 3,1 4,1 5,1 6,1 7,1 8,1 1,2 2,2 3,2 4,2 5,2 6,2 7,2 8,2 . . . . . . . . . . . . . . . . . . . . . . . . 1,β 2,β 3,β 4,β 5,β 6,β 7,β 8,β * * * * * * * * * * * * * * * * * (c) 1,1 2,1 3,1 4,1 5,1 6,1 7,1 8,1 1,2 2,2 3,2 4,2 5,2 6,2 7,2 8,2 . . . . . . . . . . . . . . . . . . . . . . . . 1,β 2,β 3,β 4,β 5,β 6,β 7,β 8,β * * * * * * * * * * * * (d)Figure12: Intuitive idea of the execution. The leader of a process is 0 if the process is labeled with a star, its own ID otherwise. level is not represented as it is always correct. The plain gray arrows show the processes that successively reset.

(e) 1,1 2,1 3,1 4,1 5,1 6,1 7,1 8,1 1,2 2,2 3,2 4,2 5,2 6,2 7,2 8,2 . . . . . . . . . . . . . . . . . . . . . . . . 1,β 2,β 3,β 4,β 5,β 6,β 7,β 8,β * * * * * * * * * * * * (f) 1,1 2,1 3,1 4,1 5,1 6,1 7,1 8,1 1,2 2,2 3,2 4,2 5,2 6,2 7,2 8,2 . . . . . . . . . . . . . . . . . . . . . . . . 1,β 2,β 3,β 4,β 5,β 6,β 7,β 8,β * * * * * * * * (g) 1,1 2,1 3,1 4,1 5,1 6,1 7,18,1 1,2 2,2 3,2 4,2 5,2 6,2 7,2 8,2 . . .. . . . . . . . . . . . . . . . . . . . . 1,β 2,β 3,β 4,β 5,β 6,β 7,β 8,β * * * * * * * * * * * * * * * * * * * * (h) Figure 12: (continued)

* This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01) funded by the French program Investissement d'avenir and the AGIR project DIAMS.

Stabilization Time in Rounds

Clean Configurations First, we study the "good" cases, i.e., when the system is in a clean configuration (defined below). From such configurations, the execution consists in building a tree rooted at ℓ using J-action only. Once, the tree is built, the system is in a terminal configuration, where every process has elected ℓ.

Definition 12 (Clean configuration). A configuration γ is called a clean configuration if and only if for every process p, ¬EBroadcast(p) ∧ p.status = C holds in γ. A configuration that is not clean is said to be dirty. Remark 3. By definition, in a clean configuration, every process p has status C and either p is a normal root, i.e., Self Root(p) ∧ Self RootOk(p), or (exclusively) KinshipOk(p, p.par) holds.

Remark 4. Notice that in a clean configuration, the only action a process p can execute is J-action, provided that Join(p) holds. Note also that Allowed(p) always holds due to Remark 3. Verifying Join(p) then reduces to: ∃q ∈ N p , (q.idR < p.idR). In this case, the value of p.idR can only decrease.

Lemmas 13 to 16 proves that, starting from a clean configuration, the system reaches in O(D) rounds a terminal configuration (see Theorem 4). We first show the set of clean configurations is closed. Lemma 13. The set of clean configurations is closed.

Proof. Let γ → γ ′ be a step such that γ is a clean configuration. By definition, all processes have status C in γ. So, processes can only execute J-action (Remark 4) in γ → γ ′ , and consequently all processes have status C in γ ′ . Now, ∀p ∈ V, ¬EBroadcast(p) ∧ p.status = C in γ implies that there is no alive abnormal root in γ. By Lemma 2, there is no alive abnormal root in γ ′ too. Now, the fact that all processes have status C and there is no alive abnormal root in γ ′ implies that ∀p ∈ V, ¬EBroadcast(p) ∧ p.status = C in γ ′ , i.e., γ ′ is clean.

Using Lemma 13, we show below that if a process is enabled in a clean configuration -for the only action it can execute, i.e., J-action -it remains enabled until it executes it. Lemma 14. In a clean configuration, if J-action is enabled at p, it remains enabled until it is executed by p.

Proof. Let γ → γ ′ be a step such that γ is a clean configuration. Assume by contradiction that J-action is enabled at p in γ and not in γ ′ , but p did not execute J-action between γ and γ ′ . By Lemma 13, γ ′ is also a clean configuration. So, ¬EBroadcast(p) ∧ p.status = C holds in γ ′ .

But Join(p) must be false in γ ′ . Using Remark 4, this means that there necessarily exists a neighbor of p, say q, such that γ(q).idR < γ(p).idR but γ ′ (q).idR ≥ γ ′ (p).idR = γ(p).idR. This contradicts Remark 4.

Lemma 15. There is no (fake) idR smaller than ℓ in a clean configuration.

Proof. Let γ be a clean configuration. Assume there exists a process of idR smaller than ℓ. Let p be such a process such that p.idR is minimum among all the processes and p.level is minimum among all the processes having idR minimum.

Note that p.idR = p so Self RootOk(p) is false in γ. Hence, using Remark 3, the predicate KinshipOk(p, p.par) holds in γ. Since we take p of minimum idR, p.idR ≤ p.par.idR in γ. GoodIdR(p, p.par) implies that p.idR ≥ p.par.idR, so p.idR = p.par.idR. Now, GoodLevel(p, p.par) implies that p.level = p.par.level + 1, which contradicts the minimality of p.level. Algorithm 3 Algorithm of the daemon. for i = top(layer) . . . bottom(layer), (i + +) do 3:

for j = 1 . . . β, (j + +) do 4:

p (i,j) executes J; 5:

end for 6:

for

if k ≥ top(layer) then 8:

for j = 1 . . . β, (j + +) do 9:

p (k,j) executes C1; steps, establishing then that the worst case is in Θ(n 3 ).

For fair comparison, we studied the step complexity of the previous best algorithm with similar settings (i.e., it does not use any global knowledge and is proven assuming an unfair daemon) given in [START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF] and called here DLV. We showed that for a given α ≥ 3, for every β ≥ 2, there exists a network of n = 2 α × β processes in which there is an execution that stabilizes in Ω(n α+1 ). In other words, the stabilization time of DLV in steps is not polynomial.

Perspectives of this work deal with complexity issues. In [START_REF] Kumar Datta | Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler[END_REF], Datta et al showed that it is easy to implement a silent self-stabilizing leader election which works assuming an unfair daemon, uses Θ(log n) bits per process, and stabilizes in O(D) rounds (where D is an upper bound on D). Nevertheless, processes are assumed to know D. It is worth investigating whether it is possible to design an algorithm which works assuming an unfair daemon, uses Θ(log n) bits per process, and stabilizes in O(D) rounds without using any global knowledge. We believe this problem remains difficult, even adding some fairness assumption.