Lélia Blin
email: lelia.blin@lip6.fr

Fadwa Boubekeur
email: fadwa.boubekeur@lip6.fr

Swan Dubois
email: swan.dubois@lip6.fr

A Self-Stabilizing Memory Efficient Algorithm for the Minimum Diameter Spanning Tree under an Omnipotent Daemon 1

Keywords: Self-stabilization, Spanning tree, Center, Diameter, MDST, Unfair daemon II

Routing protocols are at the core of distributed systems performances, especially in the presence of faults. A classical approach to this problem is to build a spanning tree of the distributed system. Numerous spanning tree construction algorithms depending on the optimized metric exist (total weight, height, distance with respect to a particular process, . . . ) both in fault-free and faulty environments. In this paper, we aim at optimizing the diameter of the spanning tree by constructing a minimum diameter spanning tree. We target environments subject to transient faults (i.e. faults of finite duration).

Hence, we present a self-stabilizing algorithm for the minimum diameter spanning tree construction problem in the state model. Our protocol has the following attractive features. It is the first algorithm for this problem that operates under the unfair and distributed adversary (or daemon). In other words, no restriction is made on the asynchronous behavior of the system. Second, our algorithm needs only O(log n) bits of memory per process (where n is the number of processes), that improves the previous result by a factor n. These features are not achieved to the detriment of the convergence time, which stays polynomial.

Introduction

Self-stabilization [START_REF] Dijkstra | Self-stabilizing systems in spite of distributed control[END_REF][START_REF] Dolev | Self-stabilization[END_REF][START_REF] Tixeuil | Algorithms and Theory of Computation Handbook, chapter Selfstabilizing Algorithms[END_REF] is one of the most versatile techniques to sustain availability, reliability, and serviceability in modern distributed systems.

After the occurrence of a catastrophic failure that placed the system components in some arbitrary global state, self-stabilization guarantees recovery to a correct behavior in finite time without external (i.e. human) intervention. This approach is particularly well-suited for self-organized or autonomic distributed systems.

In this context, one critical task of the system is to recover efficient communications. A classical way to deal with this problem is to construct a spanning tree of the system and to route messages between processes only on this structure. Depending on the constraints required on this spanning tree (e.g. minimal distance to a particular process, minimum flow, ...), we obtain routing protocols that optimize different metrics.

In this paper, we focus on the minimum diameter spanning tree (MDST) construction problem [START_REF] Ho | Minimum diameter spanning trees and related problems[END_REF]. The MDST problem is a particular spanning tree construction in which we require spanning trees to minimize their diameters. Indeed, this approach is natural if we want to optimize the worst communication delay between any pair of processes (since this latter is bound by the diameter of the routing tree, that is minimal in the case of the MDST).

The contribution of this paper is to present a new self-stabilizing MDST algorithm that operates in any asynchronous environment, and that improves existing solutions on the memory space required per process. Namely, we decrease the best-known space complexity for this problem by a factor of n (where n is the number of processes). Note that this does not come at the price of degrading time performance. Related works. Spanning tree construction was extensively studied in the context of distributed systems either in a fault-free setting or presence of faults.

There is an extensive, literature on self-stabilizing construction of various kinds of trees, including spanning trees (ST) [START_REF] Cournier | A new polynomial silent stabilizing spanning-tree construction algorithm[END_REF][START_REF] Kosowski | A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves[END_REF], breadth-first search (BFS) trees [START_REF] Afek | Self-stabilizing unidirectional network algorithms by power supply[END_REF][START_REF] Burman | Time optimal asynchronous self-stabilizing spanning tree[END_REF][START_REF] Cournier | The first fully polynomial stabilizing algorithm for BFS tree construction[END_REF][START_REF] Dolev | Uniform dynamic self-stabilizing leader election[END_REF][START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF], depth-first search (DFS) trees [START_REF] Collin | Self-stabilizing depth-first search[END_REF][START_REF] Huang | Self-stabilizing depth-first token circulation on networks[END_REF], minimum-weight spanning trees (MST) [START_REF] Korman | Fast and compact self stabilizing verification, computation, and fault detection of an MST[END_REF][START_REF] Blin | Fast selfstabilizing minimum spanning tree construction[END_REF], shortest-path spanning trees [START_REF] Gupta | Self-stabilizing protocol for shortest path tree for multi-cast routing in mobile networks (research note)[END_REF][START_REF] Huang | A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity[END_REF], minimumdegree spanning trees [START_REF] Blin | Self-stabilizing minimum degree spanning tree within one from the optimal degree[END_REF], Steiner Tree [START_REF] Blin | A superstabilizing log (n)-approximation algorithm for dynamic steiner trees[END_REF], etc. A survey on self-stabilizing distributed protocols for spanning tree construction can be found in [START_REF] Gärtner | A survey of self-stabilizing spanning-tree construction algorithms[END_REF].

The MDST problem is closely related to the determination of centers of the system [START_REF] Hassin | On the minimum diameter spanning tree problem[END_REF]. Indeed, a center is a process that minimizes its eccentricity (i.e. its maximum distance to any other process of the system). Then, it is well-known that a BFS spanning tree rooted to a center is an MDST. As many self-stabilizing solutions to BFS spanning tree construction exist, we focus, in the following part on the hardest part of the MDST problem: the center computation problem.

A natural way to compute the eccentricity of processes of a distributed system (and beside, to determine its centers) is to solve first the all-pairs shortest path (APSP) problem. This problem consists in computing, for any pair of processes, the distance between them in the system. This problem was extensively studied under various assumptions. For instance, [START_REF] Holzer | Optimal distributed all pairs shortest paths and applications[END_REF] provides an excellent survey on recently distributed solutions to this problem and presents an almost optimal solution in synchronous settings. Note that there also exist some approximation results for this problem, e.g. [START_REF] Peleg | Distributed algorithms for network diameter and girth[END_REF][START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF], but they fall outside the scope of this work since we focus on exact algorithms. In conclusion, this approach is appealing since it allows to use well-known solutions to the APSP problem, but it yields automatically to a O(n log n) space requirement per process (due to the very definition of the problem).

In contrast, only a few works focused directly on the computation of centers of a distributed system to reduce space requirement as we do in this work.

In a synchronous and fault-free environment, we can cite [START_REF] Korach | Distributed algorithms for finding centers and medians in networks[END_REF] that present the first algorithm for computing directly centers of a distributed system. In a selfstabilizing setting, some works [START_REF] Antonoiu | A self-stabilizing distributed algorithm to find the center of a tree graph[END_REF][START_REF] Bruell | Self-stabilizing algorithms for finding centers and medians of trees[END_REF][START_REF] Datta | Leader election and centers and medians in tree networks[END_REF] described solutions that are specific to tree topologies. The most related work to ours is from Butelle et al. [START_REF] Butelle | A uniform self-stabilizing minimum diameter tree algorithm (extended abstract)[END_REF].

The self-stabilizing distributed protocol proposed in this latter makes no assumptions on the underlying topology of the system and works in asynchronous environments. Its main drawback lies in its space complexity of O(n log n) bits per process, that is equivalent to those of APSP-based solutions.

Our contribution. At the best of our knowledge, the question whether it is possible to compute centers of any distributed system in a self-stabilizing way using only a sublinear memory per process is still open. Our main contribution is to answer positively to this question by providing a new deterministic self-stabilizing algorithm that requires only O(log n) bits per process, which improves the current results by a factor n. Moreover, our algorithm is suitable for any asynchronous environment since we do not make any assumption on the adversary (or daemon) and has a convergence time in O(n 2 ) rounds (that is comparable to existing solutions [START_REF] Butelle | A uniform self-stabilizing minimum diameter tree algorithm (extended abstract)[END_REF]).

Organization of the paper. This paper is organized as follows. In section 2, we formalize the model used afterwards. Section 3 is devoted to the description of our algorithm while Section 4 contains its correctness proof. Finally, we discuss some open questions in Section 5.

Model and Definitions

State model. We model the system as an undirected connected graph G = (V, E) where V is a set of processes and E is a binary relation that denotes the ability for two processes to communicate, i.e. (u, v) ∈ E if and only if u and v are neighbors. We consider only identified systems (i.e. there exists a unique identifier id v for each process v taken in the set [0, n c ] for some constant c).

The set of all neighbors of v, called its neighborhood, is denoted by N v . In the following, n denotes the number of processes of the network.

We consider the classical state model (see [START_REF] Dolev | Self-stabilization[END_REF]) where communications between neighbors are modeled by direct reading of variables instead of an exchange of messages. Every process has a set of shared variables (henceforth, referred to as variables). A process v can write to its own variables only, and read its own variables and those of its neighbors. The state of a process is defined by the current value of its variables. The state of a system (a.k.a. the configuration) is the product of the states of all processes. We denote by Γ the set of all configurations of the system. The algorithm of every process is a finite set of rules. Each rule consists of: <label >:<guard >-→<statement>. The label of a rule is simply a name to refer the action in the text. The guard of a rule in the algorithm of v is a boolean predicate involving variables of v and its neighbors. The statement of a rule of v updates one or more variables of v. A statement can be executed only if the corresponding guard is satisfied (i.e. it evaluates to true). The process rule is then enabled, and process v is enabled in γ ∈ Γ if and only if at least one rule is enabled for v in γ.

A step γ → γ is defined as an atomic execution of a non-empty subset of enabled rules in γ that transitions the system from γ to γ . An execution of an algorithm A is a maximal sequence of configurations = γ 0 γ 1 . . . γ i γ i+1 . . . such that, ∀i ≥ 0, γ i → γ i+1 is a step if γ i+1 exists (else γ i is a terminal configuration). Maximality means that the sequence is either finite (and no action of A is enabled in the terminal configuration) or infinite. E is the set of all possible executions of A. A process v is neutralized in step γ i → γ i+1 if v is enabled in γ i and is not enabled in γ i+1 , yet did not execute any rule in step

γ i → γ i+1 .
The asynchronism of the system is modeled by an adversary (a.k.a. daemon) that chooses, at each step, the subset of enabled processes that are allowed to execute one of their rules during this step (we say that such processes are activated during the step). The literature proposed a lot of daemons depending on their characteristics (like fairness, distribution, ...), see [START_REF] Dubois | A taxonomy of daemons in self-stabilization[END_REF] for a taxonomy of these daemons. Note that we assume an unfair distributed daemon in this work. This daemon is the most challenging since we made no assumption of the subset of enabled processes chosen by the daemon at each step. We only require this set to be non-empty if the set of enabled processes is not empty in order to guarantee progress of the algorithm.

To compute time complexities, we use the definition of round [START_REF] Dolev | Resource bounds for self-stabilizing message-driven protocols[END_REF]. This definition captures the execution rate of the slowest process in any execution.

The first round of ∈ E, noted , is the minimal prefix of containing the execution of one action or the neutralization of every enabled process in the initial configuration. Let be the suffix of such that = . The second round of is the first round of , and so on.

Self-stabilization. Let P be a problem to solve. A specification of P is a predicate that is satisfied by every execution in which P is solved. We recall the definition of self-stabilization.

Definition 1 (Self-stabilization [START_REF] Dijkstra | Self-stabilizing systems in spite of distributed control[END_REF]) Let P be a problem, and S P a specification of P. An algorithm A is self-stabilizing for S P if and only if for every configuration γ 0 ∈ Γ, for every execution = γ 0 γ 1 . . ., there exists a finite prefix γ 0 γ 1 . . . γ l of such that every execution of A starting from γ l satisfies S P .

Presentation of the Algorithm

In this section, we present our self-stabilizing algorithm for the computation of centers of the distributed system, named SSCC (for Self Stabilizing Centers Computation). We organize this section in the following way. First, we give a global overview of our algorithm in Section 3.1. Then, Sections 3.2, 3.3, 3.4, and 3.5 are devoted to the detailed presentation of each module of our algorithm, respectively a leader election module, a token circulation module, an eccentricity computation module, and finally the center computation module.

High-level Description

Our algorithm is based on several layers, each of them performing a specific task. Of course, these layers operate concurrently but, for the clarity of presentation, we present them sequentially in a "down-to-top" order.

The first layer is devoted to the construction of a rooted spanning tree. As we have a uniform model (that is, all processes execute the same self-stabilizing algorithm), there is no a priori distinguished process that may take the role of the root of the system. Therefore, we need first to elect a leader. We use an algorithm that performs such an election and constructs a spanning tree in the same time. To our knowledge, only the algorithm proposed by [START_REF] Datta | An o(n)-time self-stabilizing leader election algorithm[END_REF] corresponds to our criteria regarding daemon, memory requirement and convergence time.

Indeed, Datta et al. [START_REF] Datta | An o(n)-time self-stabilizing leader election algorithm[END_REF] designed a self-stabilizing algorithm to construct a BFS tree rooted at the process of minimum identity. This algorithm self-stabilizes even under the distributed unfair daemon, it uses O(log n) bits of memory per process, and it converges in O(n) rounds. Throughout the rest of the paper, we call the BFS tree constructed by this first layer the Backbone of the system.

The second layer is a token circulation on the Backbone. Along with all existing self-stabilizing algorithms for token circulation, we choose to slightly adapt an algorithm of Petit and Villain [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF]. The aim of this token circulation is to synchronize the temporal multiplexing of variables of the third layer of our algorithm that computes the eccentricity of each process. Indeed, to reduce the space requirement of our algorithm to O(log n) bits per process, all processes compute their eccentricities using the same variables, but one at a time and in a sequential fashion. To avoid conflicts, we manage this mutual exclusion by a token circulation. In more details, we distinguish, for each process, the forward token circulation (that is, the process gets the token from its parent in the Backbone) and the backward token circulations (that is, the process gets back the token from one of its children in the Backbone).

A process starts the execution of the third layer of our algorithm (that is, computation of process eccentricity) only on the forward token circulation. On a backward token circulation, the process sends the token to the following process in the Backbone in a DFS order, without performing any extra task. A process v computes its eccentricity in the following way. When it receives the forward token, v starts a self-stabilizing BFS tree construction rooted at itself. We denote this BFS by BFS(v). Once the construction of BFS(v) is done, the leaves of this tree start a feedback phase that consists in propagating back to v the maximum depth of a process in BFS(v) (which is exactly the eccentricity of v).

Once process v has collected its eccentricity, it releases the token to the following process in the Backbone.

Finally, the fourth layer aim is the center determination. The minimum eccentricity (computed for each process by the third layer) is collected all the time from the leaves of the Backbone to its root. Then, the root propagates this minimum eccentricity to all processes along the Backbone. The processes with the minimum eccentricity become centers. Also, among the centers, we elect the one with the highest identity to be the root of the minimum diameter spanning tree. We claim that each layer of this algorithm stack is self-stabilizing and that their composition self-stabilizes to a minimum diameter spanning tree of the system under the distributed unfair daemon within O(n 2 ) rounds. As each layer of our algorithm needs at most O(log n) bits per process, we obtain the desired space complexity.

Leader Election and Spanning Tree Construction

The first layer of our algorithm executes a self-stabilizing algorithm from Datta et al. [START_REF] Datta | An o(n)-time self-stabilizing leader election algorithm[END_REF] that elects the process of smallest identity in the system and constructs a BFS spanning tree rooted at this leader. This algorithm works under the distributed unfair daemon, uses O(log n) bits of memory per process, and stabilizes within O(n) rounds.

Since we use this algorithm as a black box, we do not need to present it formally here. The interested reader is referred to the original paper [START_REF] Datta | An o(n)-time self-stabilizing leader election algorithm[END_REF]. Remember that we call Backbone the BFS tree built by this layer of our algorithm. For the remainder of the presentation, we denote the parent of any process v in the Backbone by p v , the set of children of v in the Backbone by child(v), and the set of neighbors of v in the Backbone by N Backbone (v). That is, if the Backbone is defined by the 1-factor {(v, p v ), v ∈ V }, then we have child(v) = {u ∈ V : p u = v} and N Backbone (v) = child(v) ∪ {p v }. We also define the predicate BRoot(v) over variables of this layer. This predicate is true if and only if the process v is the root of the Backbone.

It is important to note that the construction of the backbone has higher priority than the other layers of our algorithm (that is, token circulation, eccentricity computation, and centers determination). In other words, if a process v has a neighbor with a different root in the Backbone or a neighbor with an incoherent distance in the Backbone, v cannot execute a rule related to any other layer. This priority is needed for our algorithm to operate under an unfair daemon.

Token Circulation

The second layer of our algorithm is a slight adaptation of a self-stabilizing token circulation algorithm by Petit and Villain [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF]. The (eventually unique) token circulates infinitely often over the Backbone in a DFS order. This algorithm operates under the distributed unfair daemon, it uses O(log n) bits of memory per process and converges in O(n) rounds.

This algorithm uses only one variable for each process v:

next v ∈ {⊥, done, N v }.
This variable stores the state of the process on the current token circulation.

The value ⊥ means that the process has not already been visited by the token during the current circulation. When next v points to a child of v in the Backbone, that means that v has been already visited during the current circulation by the token and that v sent the token to its child pointed by next v . The value done means that the process and all its children in the Backbone have already been visited by the token during the current circulation. In other words, the token is held by the first process v with next v = ⊥ along the path issued from the root of the Backbone following (non-⊥ and non-done) next variables.

Refer to Figure 1 for an illustration. We define a total order over the values of variable next by extending the natural order > over identities with the following assumption: for any process v, we have done id v ⊥.

The formal presentation of this layer is provided in Algorithm 1, the presentation of functions and predicates used by this algorithm is postponed in the detailed description (see subsection 3.3.1). This algorithm consists of two rules.

The first one, R ErToken , is used to perform the convergence towards a unique token and the reset of the next variables at the completion of a token circulation while the second one, R Backward , performs the backward circulation of the token.

Note that the forward circulation rule is left to the next layer of our protocol (see below for more explanations on the relationship between these two layers).

Algorithm 1 Token circulation for process v

RErToken : ErValues(v) ∨ ¬BRoot(v) ∧ (nextp v = v) ∧ (nextv ∈ child(v) ∪ {done}) → nextv := ⊥; RBackward : ¬ErValues(v) ∧ (BackNd(v) ∨ BackR(v)) ∧ (RBFS Next(v) = id(Next(v))) → nextv := Next(v);
We modify the original algorithm of [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF] in the following way. When a process v receives the token, this latter is blocked by v until the third layer of our protocol computes the eccentricity of this process. This is done by the construction of a BFS tree rooted at v and by the gathering of the maximum distance between v and any other process in the system (refer to Section 3.4 for more details on this layer). This is the reason why the forward token circulation is not performed by a rule of Algorithm 1 but by the rule R EndBFS in Algorithm 2

(that described the third layer of our algorithm). Communication between these two layers on the state of the token is performed using the predicate TokenD(v).

When the token circulation layer gives the token to process v, this predicate becomes true, that allows the eccentricity computation layer to start. Once the eccentricity of process v is computed, this latter updates next v (see R EndBFS in Algorithm 2) that perform the forward token circulation (exactly as in the original algorithm of [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF]).

We also slightly modify the backward token circulation to ensure the convergence of the eccentricity computation layer. If the process v wants to send the token in a backward circulation to a neighbor u, v has to wait in the case where u is currently computing its own eccentricity (this situation is possible if u wrongly believes to have the token). We perform this waiting using a vari-able RBFS u dedicated to the BFS construction (see Section 3.4 for the definition of this variable). This variable stores the identity of the root of the BFS tree construction in which u is currently involved. Then, v postpones its backward circulation to u until RBFS u is equal to u. If u wrongly believes to have the token, it can detect it locally and to correct this error within a finite time (see Section 3.4), that ensures us that the token is never infinitely blocked by v.

The composition between the backbone construction layer and the token circulation layer of our algorithm must withstand the unfairness of the daemon.

Indeed, we have to ensure that the daemon cannot choose exclusively processes enabled only for the token circulation (recall that we assume that the backbone construction has priority over the token circulation) since this may lead to a starvation of the backbone construction. To deal with this issue, we choose to block the token circulation at process v if v has a neighbor that do not belong to the backbone or if v detects an inconsistency between distances in the backbone (refer to the definition and the use of predicate ErValues). Since, before the stabilization of the backbone, the overlay structure induced by variables p v for all v ∈ V may be composed only of subtrees or cycles, we can ensure the starvation-freedom of the backbone construction. Indeed, the daemon cannot activate infinitely the token circulation rules of processes in a given subtree because at least one of them has a neighbor that does not belong to the same subtree, which blocks the token at this process. Similarly, the daemon cannot activate infinitely the token circulation rules of processes in a given cycle because the token detects an inconsistency with distances in the backbone and then gives the priority to the backbone construction.

Detailed description of the Token Circulation

We start by the detailed description of the rule rule R ErToken . Remember that the rule R ErToken is used to perform the convergence towards a unique token but also to reset the next variables to ⊥ at the end of each token circulation. by the token. So, if the token is not equal of one of these variables (e.g. towards a neighbor of v that do not belong to child(v)) then an error is detected.

R ErToken : ErValues(v) ∨ ¬BRoot(v) ∧ (next p v = v)∧ (next v ∈ child(v) ∪ {done}) -→ next v := ⊥; (1) 10
⊥ ⊥ ⊥ D D D D ⊥ ⊥ D ⊥ D ⊥ (a) Normal configuration ⊥ ⊥ ⊥ D D v D D ⊥ ⊥ D ⊥ D ⊥ (b) Error in process v
ErValues(v) ≡ next v ∈ child(v) ∪ {⊥, done} (2)
The second part of the guard of rule R ErToken is dedicated to detecting an other inconsistency of the variables dedicated to the token circulation. Indeed, if a process v is not the root of the Backbone and its variable next v points toward one of its children that mean the token is kept by one of these descendants, so its parent must point toward itself (see Figure 2(b)). Finally, this rule also detects the case where the token already explores the whole subtree rooted to the parent of the process and then set its next variable to ⊥ to prepare the next token circulation. Indeed, in this case, we have:

next v = done and next p v = done
and the execution of the rule reset next v to ⊥.

The rule R Backward performs the backward circulation of the token. Remem-ber that the forward circulation rule is left to the next layer of our protocol.

R Backward : ¬ErValues(v) ∧ (BackNd(v) ∨ BackR(v))∧ (RBFS Next(v) = id(Next(v))) -→ next v := Next(v); (3)
The rule is activated if and only if the process v is not in error (see predicate ¬ErValues(v)). To explain this rule, we need to explain first the function Next(v). This function returns the next neighbor of v to which send the token (in a round-robin fashion on identities) or done is the whole subtree rooted at the process was already explored. Note that this function also allows the root of the tree to initiate the reset of next variables to ⊥ when it locally detects the termination of a token circulation.

Next(v) =        u if ∃u ∈ child(v), idu = min{idw | w ∈ child(v) ∧ (idw nextv)} ⊥ if BRoot(v) ∧ nextv ∈ child(v) ∧ (∀u ∈ child(v), nextv idu ∨ nextv = idu) done otherwise (4)
The predicates BackR(v) and BackNd(v) used in the guard of R Backward (v denotes respectively the root of the Backbone and another process) are basically used to detect when the token has finished its circulation in the subtree rooted at the process currently pointed by next v (indicated by the done value).

BackR(v) ≡ BRoot(v) ∧ (next v = u) ∧ (next u = done) ∧ PermR(v) (5) BackNd(v) ≡ ¬BRoot(v) ∧ (next p v = v) ∧ (next v ∈ child(v))∧ (next Next(v) = done) ∧ PermNd(v) (6)
These predicates make respectively use of PermR(v) and PermNd(v). These latter are used to ensure that the process u returned by the application of the function Next(v) satisfies next u = ⊥ (to avoid the sending of the token on a subtree in an illegal state).

PermR(v) ≡ (Next(v) = ⊥) ∨ (next Next(v) = ⊥) (7) PermNd(v) ≡ (Next(v) = done) ∨ (next Next(v) = ⊥) (8)
The communication between the token circulation and the eccentricity computation is performed using the predicate TokenD(v). When the token circulation layer gives the token to process v, this predicate becomes true, that allows the eccentricity computation layer to start. Once the eccentricity of process v is computed, this latter updates next v that performs the forward token circulation (exactly as in the original algorithm of [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF]).

TokenD(v) ≡ (next v = ⊥)∧ (BRoot(v) ∧ PermR(v))∨ (¬BRoot(v) ∧ (next p v = v) ∧ PermNd(v) (9)

Eccentricity Computation

The third layer of our algorithm is devoted to the computation of the eccentricity of each process. Recall that the token circulation performed by the second layer eventually ensures that at most one process computes its eccentricity at a time (that allows us to re-use the same variables). Roughly speaking, the eccentricity of each process is computed as follows. First, the process starts the construction of a BFS spanning tree rooted at itself. Once done, we gather the maximum distance in this tree (namely, the eccentricity of its root) from its leaves. Then, the process obtains its eccentricity and releases the token.

This algorithm works under the distributed unfair daemon, uses O(log n) bits of memory per process, and stabilizes within O(n) rounds (for the computation of the eccentricity of one process).

For the clarity of the presentation, let us denote by r a process that obtains the token at a given time (that is, TokenD(r)=true from this time up to the release of the token by this process). Then, our algorithm starts the construction of BFS(r) (the BFS spanning tree rooted at r). The first step is to inform all processes of the identity of r in order to synchronize their eccentricity computation algorithms. We do that by broadcasting the identity of r along the Backbone (we perform this broadcast by re-orienting temporarily the Backbone towards r) Then, we use a classical BFS spanning tree construction borrowed from [START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF] that consists, for each process, to choose as its parent in the tree the process among its neighbors that proposes the smallest distance to the root (obviously, the process updates then its own distance to be consistent with the one of its new parent).

The delicate part is to collect the maximum distance to the root after the stabilization of BFS(r) (and not earlier). As we already said, this gathering is made by a wave from the leaves to the root of BFS(r). Each leave of BFS(r) propagates to its parent its own eccentricity value while other processes propagate to their parent the maximum between the eccentricity values of their children in BFS(r). Due to the asynchrony of the system, some difficulties may appear during this process. Indeed, if we collect an eccentricity value in a branch of BFS(r) whereas this branch is not yet stabilized (that is, some processes may still join it), we can obtain a wrong eccentricity for the process r. In this case, r may release the token earlier than expected. To prevent that, we manage the gathering of the maximum distance in the following way. When a process v changes its distance in BFS(r), this process "cleans" its eccentricity variable (that is, it erases the current value of this variable and replaces it with a specific value). Then, all processes on the path of BFS(r) between r and v clean their eccentricity variables in an upward process. In other words, we maintain at least one path in BFS(r) in which all the eccentricity variables are cleaned until BFS(r) is stabilized. The existence of this path ensures us that r does not obtain its eccentricity and release the token precociously.

We are now in measure to present formally our eccentricity computation algorithm. First, recall that, in order to broadcast the identity of the process that the algorithm currently computes the eccentricity, we need to re-orientate the Backbone to root it at the process r with TokenD(r)=true. We call this oriented tree Backbone(r). For this purpose, we introduce the function p next(v)

for each process v. This function returns the identity of the neighbor of v that belongs to the path of Backbone from v to r. More precisely, p next is defined as follow:

p next(v) =        p v if TokenD(v) = f alse ∧ next v ∈ {⊥, done} ⊥ if TokenD(v) = true next v otherwise (10)
We define also the function chNext(v) that returns the set of children of v in Backbone(r), i.e. neighbors u of v satisfying p next(u) = v.

Our algorithm uses the following variables for each process v in order to construct BFS(r) and to compute the eccentricity of r:

-Ecc v ∈ N ∪ {⊥} is the eccentricity of process v;

-RBFS v ∈ N is the identity of the root in BFS(r);

-PBFS v ∈ N ∪ {⊥} is the identity of the parent of v in BFS(r);
-dBFS v ∈ N ∪ {⊥, ∞} is the distance between v and the root in BFS(r);

-DBFS v ∈ N ∪ {⊥, ↓, ↑} is the maximum distance between the root r and the farthest leaf in the sub-tree of v in BFS(r);

Now, we can present rules of the third layer of our algorithm. These rules make use of some predicates and functions whose descriptions are postponed in subsection 3.4.1. For the clarity of presentation, we split the rules of our algorithm in two sets. The first one (refer to Algorithm 2) contains rules enabled for a process that holds the token (that is, a process v such that TokenD(v) = true) while the second one (refer to Algorithm 3) described rules for a process that does not hold the token

We discuss first of rules enabled only when the process holds the token presented in Algorithm 2. Recall that these rules are applied only when the process receives the token in a forward circulation (refer to Section 3.3). Once the process r received the token, its predicate TokenD(r) becomes true. In this state, the process r can apply only three rules.

The rule R StartBFS starts the computation of BFS(r) since r takes a state indicating that it is the root of the current BFS spanning tree. The rule R CleanEcc cleans the eccentricity variable of r when needed (that is, after a fake compu-Algorithm 2 Computation of BFS and eccentricity for a process v such that TokenD(v) = true RStartBFS : ¬RootBFS(v) -→ (RBFSv, dBFSv, DBFSv) := (idv, 0, ⊥)

RCleanEcc(v) : RootBFS(v) ∧ SameBFS(v) ∧ (Down(v) ∨ Bot(v)) -→ DBFSv := DCE(v) REndBFS : RootBFS(v) ∧ SameBFS(v) ∧ ChN(v) -→ Eccv := Dis(v); nextv := Next(v); MinEUPv := MinEcc(v);
tation of eccentricity due to the asynchrony of the system). Finally, the rule R EndBFS is executed when the leaves-to-root propagation of the eccentricity is over. This rule computes the eccentricity of r, releases the token by updating the variable next r of the token circulation layer (see Section 3.3), and updates one variable for communicating the new eccentricity to the centers determination layer (see Section 3.5 for more details on the use of this variable).

We then focus on rules enabled when the process does not hold the token presented in Algorithm 3. The first rule R Tree is dedicated to flood the identity of the root r of the current BFS spanning tree along the Backbone. This flooding is possible since we re-orientate the Backbone (refer to the definition of p next above). In the same time, the rule R Tree also detects some local errors.

As an example, the variable DBFS v of a process (used to collect the eccentricity of r) must not have an integer value if one of the children (in BFS(r)) of this process is not in the same case. The rule R BFS performs the BFS construction in itself. Finally, the rule R Ecc deals with the tricky phase of eccentricity leaves-toroot gathering with the cleaning mechanism explained above. These rules are implemented with the help of predicates and functions defined and detailed in subsection 3.4.1.

Detailed description of eccentricity computation

In this section, we detail the rules of Algorithms

RBFS : GoodBFS(v) ∧ SameBFS(v) ∧ (Best(v) = ⊥) -→ (PBFSv, dBFSv, DBFSv) := (Best(v), dBFS Best(v) + 1, DBFS(v)); REcc : GoodBFS(v) ∧ SameBFS(v) ∧ (∀u ∈ Nv : dBFSu = ∞) ∧(Best(v) = ⊥) ∧ (DBFSv = Dis(v)) -→ DBFSv := Dis(v)
the computation of BFS(v), the variables dedicated to the BFS computation take values corresponding to the root. Remember that RBFS v stores the identity of the root in the current BFS, dBFS v is the distance from the root to v in the current BFS and DBFS v is used to compute the eccentricity of the root of the current BFS. To achieve that, the process v checks if the root of the BFS is itself, if it has not a parent, and if its distance is equal to zero with the following predicate.

RootBFS(v) ≡ (RBFS v , PBFS v , dBFS v ) = (id(v), ⊥, 0) (11)
If not, the rule R StartBFS assigns the variables RBFS v , PBFS v , dBFS v in this way.

R StartBFS : ¬RootBFS(v) -→ (RBFS v , dBFS v , DBFS v ) := (id v , 0, ⊥) (12)
As previously said, the rule R Tree allows the flooding of the identity of the root r of the current BFS spanning tree along the Backbone and the detection of some local errors. To achieve the computation of the current BFS, the first step is to clean all the variables relative to the previous BFS.

R Tree : ¬GoodBFS(v) -→ (RBFS v , PBFS v , dBFS v , DBFS v ) := (RBFS p next(v) , ⊥, ∞, ⊥) (13)
The predicate GoodBFS(v) checks if the root BFS is the same as its neighbors in the Backbone that leads to the token. In others words, RBFS v must be equals to the identity of the process holding the token.

GoodBFS(v) ≡ (RBFS v = RBFS p next v ) (14)
To compute the current BFS and the eccentricity, all processes must consider as root of the BFS the process that keep the token. Hence, all other rules are enabled only when GoodBFS(v) is satisifed. The rule R BFS performs the BFS construction in itself.

R BFS : GoodBFS(v) ∧ SameBFS(v) ∧ (Best(v) = ⊥) -→ (PBFS v , dBFS v , DBFS v ) := (Best(v), dBFS Best(v) + 1, DBFS(v)); (15)
DBFS(v) =    ↑ if DBFS v ∈ N ↓ otherwise (16)
The predicate SameBFS(v) is satisfied when all the neighbors of v are in the same BFS tree (i.e. when all its neighbors have the same root than v).

SameBFS(v) ≡ (∀u ∈ N v , (RBFS u = RBFS v )) (17)
The rule R BFS makes use of the function Best(v) that returns a neighbor of v with a better distance than it if such a neighbor exists, ⊥ otherwise.

Best(v) =        p = min{id(u) | dBFS u = min{dBFS w | w ∈ N v }} if (p = PBFS v ) ∨ (dBFS v = dBFS p + 1) ⊥ otherwise (18)
If the process v has a better parent p in the current BFS, v changes its variables relative to the BFS according to p by executing the rule R BFS .

The rule R Ecc deals with the tricky phase of eccentricity leaves-to-root gath-ering.

R Ecc : GoodBFS(v) ∧ SameBFS(v) ∧ (∀u ∈ N v : dBFS u = ∞) ∧(Best(v) = ⊥) ∧ (DBFS v = Dis(v)) -→ DBFS v := Dis(v) (19)
Due to the asynchrony of the system, the process v can store a fake eccentricity. Let us first describe how our algorithm manage this from a global point of view. We add three values to DBFS v : the values ⊥, ↑, and ↓. The value ⊥ is dedicated to resetting the variable DBFS v in a root-to-leave wave either when the root of the BFS changes or when a fake eccentricity is detected. In our algorithm, a process can compute its eccentricity only when its eccentricity variable and the ones of its ancestors have the value ↓ and all its descendants have already computed their eccentricities (inducing a leave-to-root computation of the eccentricities). Hence, the reset wave is followed by a root-to-leave wave that transitions the DBFS v variable forms the value ⊥ to ↓. When a process v detects an inconsistency in eccentricity computation, it puts its variable DBFS v to ↑.

This value is then propagated to the whole system from neighbors to neighbors, suspending the eccentricity computation. When all the neighbors of the root reach the value ↑, the root restarts the reset root-to-leave wave (i.e propagate the value ⊥).

We are now in measure to present in more details predicates and functions used to implement this mechanism. The eccentricity of a process v is the farther distance from it to its descendants. Then, we compute these distances the leaves of the BFS tree to its root. When a process v is a leaf or all its children in the current BFS have computed their farther distances, the process v can compute its farther distance DBFS v . The function Ch bfs(v) returns the set of children of v in the current BFS (i.e. the neighbors u with the same BFS root such that the variable parent of u points to v and the distance of u is the distance of v plus one).

Ch bfs(

v) = {u | u ∈ N v ∧ (RBFS u , PBFS u , dBFS u ) = (RBFS v , v, dBFS v + 1)} ( 20
)
The farther distance of process v is computed thanks to the function MaxD(v)

that returns the largest value between its own current distance and the farther distance provided by its children in the current BFS.

MaxD(v) = max{dBFS v , max{DBFS u | u ∈ Ch bfs(v)}} (21)
We present now predicates designed to check inconsistencies in eccentricity computation. To be considered coherent, a process v must satisfies the following set of properties: (i) all its children in the current BFS tree have already computed their farther distance, (ii) its variable DBFS v must be equal to the farther distance of the current root (computed by the predicate MaxD(v)), (iii) either its parent has not yet computed its farther distance (DBFS PBFSv =↓) or its father has already computed its own farther distance (DBFS PBFSv ∈ N), and (iv) its variable DBFS v is coherent with DBFS PBFSv , (the one of its parent in the current BFS). The three first properties are gathered in the CohD E (v) predicate while the fourth one is captured by the predicate CohD N (v).

CohD E (v) ≡ (DBFS v ∈ N) ∧ (dBFS v = min{dBFS u : ∀u ∈ N v } + 1) ∧(∀u ∈ Ch bfs(v), DBFS u ∈ N) ∧ (DBFS v = MaxD(v)) ∧ (DBFS PBFSv ∈ {↓, N}) (22)
CohD N (v) ≡ (DBFS PBFSv , DBFS v ) ∈ {(⊥, ⊥), (⊥, ↑), (↓, ⊥), (↑, ↑), (↓, ↓)} (23)
As a consequence, a process v is considered coherent (notion described by the predicate CohD(v)) if it satisfies both CohD N (v) and CohD E (v).

CohD(v) ≡ (CohD N (v) ∧ CohD E (v)) ( 24
)
A process is allowed to compute its eccentricity only when all its neighbors have computed their distance from the root in BFS. The predicate Gd(v)

R CleanEcc : RootBFS(v) ∧ SameBFS(v) ∧ (Down(v) ∨ Bot(v)) -→ DBFS v := DCE(v) (30)
Finally, the rule R EndBFS is executed by the root of the BFS when the leavesto-root propagation of the eccentricity is over. This termination is checked by the predicate ChN(v). This predicate is satisfied once all the children of the root have computed their farther distance.

ChN(v) ≡ (∀u ∈ N v , DBFS u ∈ N) (31)
The execution of this rule computes the eccentricity of r (with the help of the function Dis(v)), releases the token by updating the variable next r of the token circulation layer (see Section 3.3), and updates one variable for communicating the new eccentricity to the centers determination layer (see Section 3.5 for more details on the use of the variable MinEcc(v)).

R EndBFS : RootBFS(v) ∧ SameBFS(v) ∧ ChN(v) -→ Ecc v := Dis(v); next v := Next(v); MinEUP v := MinEcc(v); (32)

Centers Computation

The fourth and last layer of our algorithm aims to identify the centers of the system. As each process computes its own eccentricity with the three first layers of our algorithm, it remains only to compute the minimal one. In this goal, we use the Backbone (oriented towards the leader elected by the first layer). First, the root gathers the minimal eccentricity in the system in a leaves-to-root wave.

Then, the root floods the Backbone with it in a root-to-leaves wave containing this minimum eccentricity. This algorithm works under the distributed unfair daemon, uses O(log n) bits of memory per process, and stabilizes within O(n)

rounds.

This layer makes use of the following variables. The variable Ecc v (maintained by the third layer, refer to Section 3.4) stores the eccentricity of the process v. The variable MinEUP v is used to collect the minimal eccentricity in the leave-to-root wave while the variable MinE v is used to store the minimal eccentricity of the system and to broadcast it in the root-to-leaves wave. Moreover, we add a variable Center v that represents the center of the graph, Center v is true if and only if MinE v = (Ecc v , id v ), otherwise Center v is f alse. We define the following

MinEcc(v) = min{(Ecc v , id v ), min{MinEUP u | u ∈ child(v)}}
note that MinEcc(v) returns the minimum eccentricity and among the nodes with the minimum eccentricity the one with minimum identity.

Algorithm 4 Computation of the minimum eccentricity for process v

R MinEUp : MinEUP v = MinEcc(v) -→ MinEUP v := MinEcc(v); R MinERoot : BRoot(v) ∧ (MinE v = MinEUP v ) -→ MinE v := MinEUP v ; Center v := IsCenter(v); R MinEDown : ¬BRoot(v) ∧ (MinE v = MinE p v )) -→ MinE v := MinE p v ; Center v := IsCenter(v);
The function IsCenter(v) returns true if the node v is the center of the graph, f alse otherwise. Remember that, among the centers node we choose the one with the minimum identity.

IsCenter(v) =    true if MinE v = (Ecc v , id v ) f alse otherwise (33)
Formal presentation of this algorithm is done in Algorithm 4. The rule R MinEUp manages the leaves-to-root gathering of minimal eccentricity while rules R MinERoot and R MinEDown ensures its root-to-leaves propagation (respectively for the root of Backbone and for other processes).

Once this algorithm stabilizes, each process knows its eccentricity (thanks to the third layer) and the minimal eccentricity in the system (thanks to the fourth layer). Then, it is trivial for a process to decide if it is a center or not. As we assume that processes have unique identifiers, it is easy to elect the center with the minimal identity in the case where the system admits more than one center in order to construct a single minimum diameter spanning tree (note that this phase requires O(log n) bits of memory per process and stabilizes within O(n) rounds).

In conclusion, the composition of these four layers provides us a self-stabilizing algorithm for centers computation or minimum diameter spanning tree construction under the distributed unfair daemon that needs O(log n) bits of memory per process and stabilizes within O(n) rounds.

Proof of the Algorithm

As our algorithm is composed of several layers, one would be tempted to use some existing generic tool to ease its proof. Unfortunately, none of the existing methods of self-stabilizing algorithms composition is suitable in our case. Indeed, we cannot use methods that restrict the power of the adversary since we consider a fully asynchronous environment (e.g. the fair composition of [START_REF] Dolev | Self-stabilization of dynamic systems assuming only read/write atomicity[END_REF][START_REF] Dolev | Self-stabilization of dynamic systems assuming only read/write atomicity[END_REF] that assumes a central and/or fair daemon or the parallel composition of [START_REF] Dolev | Parallel composition of stabilizing algorithms[END_REF] that works only with a fair daemon). Some other methods are relevant only to specific composition that are not used by our algorithm (e.g. the crossover composition of [START_REF] Beauquier | Cross-over composition -enforcement of fairness under unfair adversary[END_REF] -composition of a daemon transformer with another algorithm-, the dependency graph composition of [START_REF] Arora | Convergence of iteration systems[END_REF] -every composed algorithm must converge to a fixed point-, or the adaptive composition of [START_REF] Gouda | Adaptive programming[END_REF] -a variable is used to select only one of the composed algorithms-). Finally, the more relevant methods (e.g. the module composition of [START_REF] Varghese | Compositional proofs of self-stabilizing protocols[END_REF] or the convergence stairs composition of [START_REF] Gouda | Stabilizing communication protocols[END_REF]) are not suitable because they require each layer of the algorithm to converge to a closed predicate, that is not the case of some layers of our algorithm (e.g. the token circulation layer modifies the root of the BFS tree each time this latter is computed by the above layer, hence violating the predicate to which the BFS tree layer converges).

In consequence, we have to come back to a custom proof for our algorithm using classical approaches. In particular, we use the property that, for a selfstabilizing algorithm, the set of legitimate configurations (i.e. configurations satisfying the specification of the problem) is an attractor of Γ for this algorithm.

Given two sets of configurations Γ 2 ⊆ Γ 1 ⊆ Γ, we say that Γ 2 is an attractor of Γ 1 for algorithm A (denoted by Γ 1 Γ 2 ) if any execution of A starting from any configuration of Γ 1 reaches in a finite time a configuration of Γ 2 and if Γ 2 is closed under A.

Some of our proofs are performed by exhibiting potential functions. A potential function is a bounded function that associates to each configuration of the system value that strictly decreases at each application of a rule by the algorithm. Hence, if the minimal value of the function is associated with a legitimate configuration of the system, the existence of such a function is sufficient to prove the convergence of the algorithm. The difficulty is obviously to exhibit the potential function that captures precisely the behavior of the self-stabilizing algorithm. Regarding the BFS spanning tree construction algorithm we use here, [START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF] proposed a potential function but this one is not suitable in our case (because of a too weak characterization of algorithm's effects on configurations and of the use of a a priori knowledge of processes). It is why we propose a more involved potential function for our algorithm to prove the lemma 7.

Theorem 1 The algorithm SSCC is a self-stabilizing algorithm that computes one of the center of the system under the distributed unfair daemon. It uses O(log n) bits of memory per process and stabilizes within O(n 2 ) rounds.

Definition 2 Blocking path: Let v be the process with one token. Define a blocking path of v as a maximal length path in BFS(v) from the root v of the BFS(v) to another process element of BFS(v) such that every process u on this path satisfies DBFS u ∈ N.

Note that, the rules R EndBFS , R CleanEcc , R BFS and R Ecc need the predicate SameBFS to true. The predicate SameBFS(v) is true for v if v and all these neighbors in G share the same root for the BFS (variable RBFS), only the rule R Tree modify this variable. Moreover, when a process v executes the rule R Tree , it puts its variable DBFS v at ⊥. As a consequence if v was in a blocking path it maintains the blocking path and if v was not in a blocking path but its parent is in a blocking path then v reaches the blocking path. Let γ be a configuration, we introduce a potential function denoted by λ as follow Γ × V × V → N be the function defined by:

λ(γ, r, v) =        1 if v belongs to a blocking path of r in γ 1 if v / ∈ SameBFS(r) and v ∈ N r in γ 0 otherwise
Now, we define our potential function Λ: Γ → N as follows:

Λ(γ, r) = v∈V λ(γ, r, v)
Claim 1 Λ(γ, r) > 0 implies the token is blocked in r.

Proof of the claim. The token is released when the process r executes the rule R EndBFS [START_REF] Ho | Minimum diameter spanning trees and related problems[END_REF], but this rule is activatable only if all the neighbors of r are in BFS(r) (see predicate SameBFS(v) [START_REF] Datta | Leader election and centers and medians in tree networks[END_REF]) and all the children of r in the BFS(r)

have already compute the distance maximum in their subtree (see predicate ChN(v) [START_REF] Hassin | On the minimum diameter spanning tree problem[END_REF] in rule R EndBFS ). If it is not the case then the token is blocked and by definition of Λ we have λ(γ, r, v) = 1 so Λ(γ, r) > 0.

Let denoted by T a spanning tree shaped by the variable p v (namely a subspanning tree or the Backbone). Let B a set of enabled process that the scheduler does not want to execute. The process r is the root of T, either a process with a blocked token or a process in B. Let us define Γ Tree as the set of configurations such that for all γ ∈ Γ Tree we have Λ(γ, r) > 0 or r ∈ B and the rule R Tree (13) is enabled by no process.

Claim 2 If Λ(γ, r) > 0 then the activation of R Tree by any process v ∈ V in configuration γ gives a configuration γ such that Λ(γ , r) = Λ(γ, r).

Proof of the claim. Let us consider a configuration γ with Λ(γ, r) > 0 and

A the set of process activated by the rule R Tree [START_REF] Butelle | A uniform self-stabilizing minimum diameter tree algorithm (extended abstract)[END_REF]. More precisely, the rule R Tree [START_REF] Butelle | A uniform self-stabilizing minimum diameter tree algorithm (extended abstract)[END_REF] is enabled when the predicate GoodBFS(v) ( 14) is not true, that means RBFS v = RBFS p next v . We distinguish two cases:

1. Let us consider, v be a neighbor of r, if R Tree is activatable by v that means v / ∈ SameBFS(r) so λ(γ, r, v) = 1, the execution of rule R Tree by v in γ gives DBFS v = ⊥ in γ , so that maintain λ(γ , r, v) = 1. So in a spanning tree without token or with blocked the token this variable

The authors of [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF] assure the uniqueness of the token in a tree. Remark that in the absence of token, it is the root of the tree that assures the creation of a token. In our case, if the root of the subtree is a process in B then no token is created, so in γ ∈ Γ GToken and G 0 there exist sub spanning trees with only one token or no token. Let us consider a γ a configuration in Γ GToken and the graph G 0 . We do not modify the backward token circulation (rule R Backward ). Let T be a sub spanning tree of G 0 , if T has a token then the number of activation of R Backward is limited by the depth of T. Note that, if the root r of T is an element of B the circulation of the token is blocked by r. So w.l.g consider a spanning tree T with a root r ∈ B, the tree T has only one token thanks to the algorithm [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF]. We proof that starting from γ the circulation of the token in T reaches a configuration γ where the circulation of the token is blocked.

The forward circulation is closely linked to the rules R StartBFS and R EndBFS .

When a process receives the token in forwarding circulation, it executes the rule R StartBFS , it releases the token thanks to the rule R EndBFS .

Claim 5 Γ GToken Γ Tree in O(1) rounds and Γ Tree is closed.

Proof of the claim. By claim 3 we obtain that the number of activation of rule R Tree is bounded in a spanning tree T if the token is blocked in the root r or r ∈ B. Let now consider a sub spanning tree T where the token is not blocked, like γ ⊂ Γ Backbone , T has at least one process v with a neighbor u such that u ∈ T, let denote by T the spanning tree such that u ∈ T . Remark that, like γ ⊂ Γ Backbone either T or T have one process in B, w.l.g suppose it is T so the circulation of the token in T if it exists is blocked. Let denoted by r the root of T , by claim 3 we obtain that the system reaches a configuration γ where RBFS u = RBFS r and this value never change. If the token was in a process w in T, w can release the token in process w . All the processes in path between w and v in T execute the rule R Tree , and all put their variable dBFS to ⊥, that result to blocking path between w and v. The process u cannot have RBFS u equal to w because u is not T, so v will never have SameBFS(v) true as a consequence the rule R Tree (15), R Ecc [START_REF] Dijkstra | Self-stabilizing systems in spite of distributed control[END_REF] and R CleanEcc (30) are note enabled for any node in T, moreover the token is blocked. To conclude, the system reaches a configuration was a neighbor of a process u element of a blocking path the process v reaches the blocking path and Λ(γ , r) increases by at least one compare to Λ(γ, r).

Let us define Γ BFS a configuration γ where ∀v ∈ V , dBFS v = d G (r, v) and Λ(γ) > 0. In other words, the rule R BFS is enabled by no process (∀v ∈ V \ {r}

we have dBFS v = min{dBFS u : u ∈ N (v)} + 1).
Claim 7 Starting from a configuration γ ∈ Γ Tree with Λ(γ, r) > 0 the number of activation of R BFS is bounded.

The computation of BFS tree with only one rule is well known, unfortunately to our knowledge all the proofs do not use a potential function, to be consistent we propose a new proof based on potential function. The authors in [START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF] proposed a potential function but this one is not suitable in our case (because of a too weak characterization of algorithm's effects on configurations and of the use of a a priori knowledge of processes). Moreover, the algorithm in [START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF] use 3 rules and the proof is based on the parent of each process, we generalize this proof for our algorithm that uses only one rule for the BFS tree.

Proof of the claim. Let γ a configuration in Γ Tree and A(γ) be the set of all activated processes by rule R BFS in γ. After the activations of processes of A(γ)

the system reaches the configuration γ . Notice that, only the rule R BFS can change the distance on the BFS tree (e.i variable dBFS), to clarify our purpose we denote by dBFS v (γ) the distance on the BFS tree of process v in configuration γ.

To compute a BFS, a process v waits that all its neighbors are in a same tree of it (see SameBFS 17). Moreover, the rule R BFS is activatable only when the distance of process v can be improved (see Best 18), for convenance we introduce

min +1 (v, γ) = min{dBFS u (γ) | u ∈ N v } + 1 that is the result of predicate Best(v).
Let P (γ) be the following potential function: We repeat the same proof until the extension of notCoh. Notice that, during all the process, the scheduler can maintain Λ positive.

P (γ) = (F (γ), S (γ)
To establish the claim, let φ : Γ GoodE → N be the potential function defined as: By lemma 3 we obtain the following corollary:

φ(γ, v, r) :              n 2 if DBFS v =↑ n if DBFS v = ⊥ 1 if DBFS v =↓ 0 if DBFS v ∈ N
Proof. The construction of Backbone and the token circulations use O(log) bits of memory per process (see articles [START_REF] Datta | An o(n)-time self-stabilizing leader election algorithm[END_REF] and [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF]). The computation of the eccentricity uses pointeur variables that use O(log n) bits of memory by process (see variables RBFS and PBFS) and distance variables that use also O(log n) bits of memory by process (see variables Ecc, dBFS and DBFS). So the algorithm SSCC uses O(log n) bits of memory per process.

This complete the proof of theorem 1

Conclusion

In this paper, we present the first self-stabilizing algorithm for the minimum diameter spanning tree construction that tolerates any asynchronous environment (captured by a distributed unfair daemon) and uses O(log n) bits of memory per process. Our algorithm achieves a stabilization time in O(n 2 ) rounds. This contribution improves the existing results by a factor n regarding the memory requirement.

This work opens some challenging questions that follow. These questions are focused on the optimality of memory requirement. The answer depends whether we want to obtain a silent self-stabilizing algorithm or not. A silent self-stabilizing algorithm is a self-stabilizing algorithm such that processes are enabled only on a finite prefix of any execution. As our algorithm is based on a token circulation, it is not a silent self-stabilizing algorithm. The first open question is to decide if our non silent self-stabilizing algorithm is optimal with respect to memory requirement. A recent work [START_REF] Blin | Compact deterministic self-stabilizing leader election -the exponential advantage of being talkative[END_REF], which presents a non silent BFS-based leader election self-stabilizing algorithm requiring O(log log n) bits of memory per process, leads us to think that we can improve the memory requirement of our algorithm. This naturally opens another question about the optimality of a silent self-stabilizing algorithm for minimum diameter spanning tree construction. An appealing way to answer this question is suggested in [START_REF] Blin | On proof-labeling schemes versus silent self-stabilizing algorithms[END_REF]. Using their solution, the question is reduced to provide a proof-labeling scheme for this problem requiring O(log n) bits of memory per process. If such a labeling scheme exists, a straightforward adaptation of our self-stabilizing algorithm would be an optimal silent self-stabilizing algorithm for the minimum diameter spanning tree construction.

Figure 1 :

 1 Figure 1: Illustration of the variable next of the token circulation layer. The gray process is the root of the Backbone. D stands for the value done.

Figure 2 :

 2 Figure 2: Token circulation

2 and 3 .Algorithm 3

 33 The rule R StartBFS is executed only by the process v with TokenD(v) = true. The process v starts Computation of BFS and eccentricity for process v with TokenD(v) = f alse RTree : ¬GoodBFS(v) -→ (RBFSv, PBFSv, dBFSv, DBFSv) := (RBFS p next(v) , ⊥, ∞, ⊥)

2 .Claim 3

 23 Let us consider now, v be not a neighbor of r, if R Tree is activatable by v that meansRBFS v = RBFS p next v so either RBFS p next v = r as a consequence λ(γ, r, v) = λ(γ , r, v) = 0, or RBFS p next v = r so λ(γ, r, v) = 0 and λ(γ , r, v) = 0 as the execution of rule R Tree by v in γ gives PBFS v = ⊥ (v is not in BFS(v) in γ since v has not parent) .We denote by p(r, v) the path in spanning tree T from the root r of T to v and by d(v) the distance between r and v in T. Let ξ be the following potential function Γ × V × V → N be the function defined by:ξ(γ, r, v) = u∈p(r,v)∧RBFSu =RBFS p next(u) (n -d(u))And Ξ the potential function: Γ → N as follows:Ξ(γ, r) = v∈V ξ(γ, r, v)Note that, Ξ(γ, r) = 0 means R Tree is enabled by no process and ∀v ∈ V we have RBFS v = r. Starting from a configuration γ ∈ Γ with Λ(γ, r) > 0 or r ∈ B the number of activation of R Tree is bounded.Proof of the claim. The rule R Tree is based on the predicate GoodBFS[START_REF] Collin | Self-stabilizing depth-first search[END_REF], if its predicate it false (RBFS v = RBFS p next v ) then the rule R Tree is enabled for the process v. The variable p next v is modified by the circulation of the Token.

)Claim 9

 9 (see reference to PBFS in lines 2 and 3 of predicate 26). In an up wave of the computation of the eccentricity, for a ancestors u of v with CohD(u) = true then the ancestor of v are not enabled until v is executed (see reference to Ch bfs in line 4 of predicate 26). The up wave of ↑ a little bit different because this wave does not use all the bfs children but the existence of one neighbor of the process (see line 1 of predicate 26), but line 2 of predicate 26 chess if all the children u of v in the BFS have DBFS u =↓ so the down wave of ⊥ is blocked until the up wave of ↑ is complete. Let us define Γ GoodE the set of configurations γ ∈ Γ BFS where ∀v ∈ V , CohD(v) = true. Starting from a configuration γ ∈ Γ BFS with Λ(γ, r) > 0 and notCoh(γ) = E(γ) then the system reaches a configuration γ ∈ Γ GoodE .Proof of the claim. Our algorithm use down and up waves, if the scheduler want slow down the convergence, it actives the processes v with CohD(v) = f alse one by one and this from the leaves of BFS(r) to the root of BFS(r). We already saw in proof of claim 8, that v and all the descendants of v in BFS(r) have their variable DBFS different of ⊥. So when the scheduler actives v, v puts DBFS v = ⊥ therefore all the children w of v in BFS(r) have now, CohD(v) = f alse. A direct consequence of this is now all w is elements of notCoh(γ) and enabled, so the system reaches a configuration γ with notCoh(γ ) = E(γ ), remark that v is not enabled until its children takes the value ↑. Moreover, CohD(v) is becomes true. So with the same argument, this process is repeated until the leaves of the subtree of v in the BFS(r). When all the descendants u of v have DBFS u = ⊥, a down wave of value ↑ is started until this wave reaches a process w in notCoh.

Corollary 2 ΓClaim 12

 212 and we define the potential function Φ: Γ GoodE → N as follows: Φ(γ, r) = v∈V \{r} µ(γ, v, r) Claim 10 Let γ ∈ Γ GoodE be a configuration where Λ(γ, r) > 0 then the activation of R Ecc by any process v ∈ V in configuration γ gives a configuration γ such that Φ(γ, r) > Φ(γ , r). The proof is direct by definition of rule R Ecc and definition of Φ. Claim 11 Let γ ∈ Γ GoodE be a configuration where Λ(γ, r) > 0 Φ(γ, r) < n then the activation of R Ecc by any process v ∈ V in configuration γ gives a configuration γ such that Λ(γ, r) > Λ(γ , r). Proof of the claim. In a configuration γ ∈ Γ GoodE if Φ(γ, r) < n then all process v have either DBFS v =↓ or DBFS v ∈ N, moreover, if Λ(γ, r) > 0 that means there exist a blocking path only composed by value ↓, and only the leaves of this blocking path are enabled, so at each activation of process v with DBFS v =↓ the function Λ decreases by one. BFS Γ e in O(n) rounds. Let us denote by e * (v) the eccentricity of process v and by E * the minimal eccentricity of the network G. We define Γ Center the set of configurations such that, for all v in V we have Ecc v = e * (v) and MinE v = E * . The centers of the network are the processes with Ecc v = MinE v . Lemma 4 Γ 1-Token Γ Center in O(n 2 ) rounds, and Γ Center is closed.Proof. In configurations Γ e the token is not blocked infinitely.Proof of the claim. Let us suppose that, the scheduler can block the token infinitely in process r, in other words starting for a configuration γ 0 with Λ(γ 0 , v) > 0 the scheduler maintains for all configurations γ > γ 0 that Λ(γ, v) > 0. We saw in the claim 2 the use of rule R Tree cannot decrease Λ, but the scheduler cannot boost indefinitely the rule R Tree (see claim 3). Similarly, we saw in the claim 6 the use of rule R BFS cannot decrease Λ but the scheduler cannot boost indefinitely the rule R Tree (see claim 7). The last rule available if the token is block, it is the rule R Ecc . The proof of claim 8 proof that the scheduler cannot maintain infinitely processes with an error in the DBFS variable (see predicate CohD). As a consequence, the system reaches configurations without error of variable DBFS. To conclude, the claims 9, 10 and claim 11 proof that the application of rule R Ecc decrease the function Λ as a consequence the process r becomes the only process enabled, and the activation of rule R EndBFS[START_REF] Ho | Minimum diameter spanning trees and related problems[END_REF] by r releases the token. Note that, in configuration γ ∈ Γ e we have for all v ∈ V \ {r} has DBFS v = max{dBFS v , max{DBFS u | u ∈ Ch bfs(v)}}, so when r executes R EndBFS , it puts in RBFS r the value e * (r) . Let us define Γ TokDown ⊆ Γ 1-Token the set of configurations where the token circulate downward and Γ TokUp ⊆ Γ 1-Token the set of configurations where the token circulate upward. A direct consequence of claim 12 is the following: Claim 13 Γ e Γ TokDown ∪ Γ TokUp in one round. Proof of the claim. In a configuration γ ∈ Γ e only the process r is enabled by rule R EndBFS . After activation of process r, Ecc r = e * (r) where e * (r) is the eccentricity of process r, and the token is released.

formalizes this configuration.

All these predicates and functions allow us to write the Dis(v) function that is the heart of all waves used by the eccentricity computation. This function returns to the process v the new value of its DBFS v variable depending on the current wave.

The rule R Ecc is responsible for the propagation of the different waves but does not handle their initialization at the root r of the BFS. This is the aim of the rule R CleanEcc . There are two types of waves to initialize: the ⊥ wave and the ↓ wave. They are respectively started when all neighbors v of r satisfy DBFS v =↑ (see predicate Down) and when all neighbors v of r satisfy

The execution of the rule R CleanEcc initiates a wave in both cases and the type of this wave is determined by the function DCE(v) above.

never changes. Let us consider a process v such that ξ(γ, r, v) > 0, and the processes u such that u ∈ p(r, v) and u is enabled by rule R Tree and activated by the scheduler in γ, Moreover u have not ancestor in p(r, v) activates by the scheduler. The process u is involved in ξ(γ, r, v) with a value (n -d(u)). Let γ be the configuration given by the execution of rule R Tree by u, we obtain in Proof. Let be γ 0 ∈ Γ Backbone the initial configuration of the system. Let us denote by B the enabled processes by rules of the construction of the Backbone.

As the scheduler want to block the construction of the Backbone, it does not activate processes in B, as a consequence until the scheduler executes an enabled process of Backbone no round is completed. In γ 0 two types of spanning structures can occur, namely, sub spanning trees and cycles. In a cycle, at least one process is an element of B. So if we consider the graph G 0 the subgraph induced by the processes V \ B then only one type of structure occurs, sub spanning trees. Let us denote by Γ GToken ⊆ Γ the set of configurations in which no process is enabled by rule R ErToken . Then, we have:

rounds and Γ GToken is closed.

Proof of the claim. The algorithm of [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF] assures the convergence and the closure for Γ GToken for each sub-trees.

γ such that Λ(γ , w) > 0 and only the processes in B are enabled, that is the rule involved in the construction of the Backbone. The convergence is given in [START_REF] Datta | An o(n)-time self-stabilizing leader election algorithm[END_REF].

The closure is given by [START_REF] Datta | An o(n)-time self-stabilizing leader election algorithm[END_REF].

Let us denote by Γ 1-Token ⊆ Γ the set of configurations in which there exists exactly one token (i.e. no process is enabled by rule R ErToken ).

Proof. Let us consider γ ∈ Γ Backbone and B denote the enabled processes by rule R ErToken . As the scheduler want to block the convergence toward one token, it does not activate processes in B. The proof mimics the proof of claim 5, the broadcast of the variable RBFS is blocked by the process in B so the circulation of the token if exists, will be blocked. As a consequence, the system reaches a configuration γ such that Λ(γ , w) > 0 and only the processes in B are enabled.

We do not modify the algorithm of [START_REF] Petit | Time and space optimality of distributed depth-first token circulation algorithms[END_REF], the authors proof the closure of the algorithm in their article.

Let us define Γ e as the set of configuration γ ∈ Γ BFS where the every process and

where

Let us denote by K the set {1, . . . , 2n + max{dBFS v (γ 0 )|v ∈ V }}. Note that, by definition all the processes v in f k (γ) for all k ∈ K are enabled by rule R BFS .

Let denote by m the distance such that m = min{k

The comparaison between F (γ) and F (γ ) is by lexical order. We denote by γ the configuration after activation of the processes in A(γ). We can now prove the following result P (γ ) < P (γ) for all configuration γ and A(γ) not empty.

1. ∃v ∈ V such that v ∈ f k (γ), ∀k ∈ K, the only way for a process v to become element of f s (γ ) is to have a neighbor u = min +1 (v, γ ) such that u ∈ f t (γ) and u ∈ A(γ). Let denote by w the neighbor of u such that w = min +1 (u, γ), w.l.g let us consider that t = m, by definition of processes u, v, w we have dBFS v (γ) > m ≤ dBFS w (γ). After activation of u we obtain, dBFS v (γ ) ≤ dBFS u (γ ) = dfs w (γ) + 1. If v ∈ A(γ) we have

after activation of v we achieve that dBFS v (γ ) = m+1 so dBFS v (γ ) ≥ m+1 as a consequence f m is decreased by at least one in γ and the system reaches F (γ ) < F (γ).

∃v ∈

and after activation of v we have dBFS v (γ ) = dBFS u (γ )+1. W.l.g let suppose k = m and let w be the process such that w = min +1 (v, γ ).

(a) Let us prove that if u = w we obtain F (γ ) < F (γ ):

as a consequence f m is decreased by at least one.

ii.

after activation of v and u we obtain dBFS v (γ ) = s+1 ≤ dBFS u (γ ) = dBFS z (γ) + 1 so v ∈ f s+1 (γ ) and f m is decreased by at least one.

iii. u ∈ A(γ) and u ∈ f s (γ)∀s ∈ K so dBFS u (γ) > dBFS z (γ) with z = min +1 (u, γ). After activation of v and u we reach dBFS v (γ ) =

ii. u ∈ A(γ) and w ∈ A(γ) or u ∈ A(γ) and w ∈ A(γ): by definition of u and w we have dBFS u (γ) = m ≤ dBFS w (γ) and we obtain in after activation of the processes that dBFS v (γ ) = m + 1 ≤ dBFS u (γ ) = dBFS w (γ ) + 1 so f m is decreased by at least one.

To conclude this part if ∃v ∈ A(γ) such that v ∈ f k (γ) the function F decreases and as a consequence P (γ ) < P (γ).

∀v ∈

A direct consequence of the first item of this proof is the activation of the processes maintains F (γ ) = F (γ), moreover this activation decreases the distance of v so S(γ ) < S(γ) and P (γ ) < P (γ).

Let E(γ) be the set of enabled processes in γ and notCoh(γ) ⊆ E(γ) a set of processes such that if v in notCoh(γ) implies CohD(v) = f alse (see 24, 22 and 23) and DBFS(v) = ⊥ (otherwise v is not enabled).


Marie-Constance Corsi

Mario Chavez

Denis Schwartz

Laurent Hugueville

Ankit N Khambhati

Danielle S Bassett

Fabrizio De

Vico Fallani

M.-C Corsi

Integrating EEG and MEG information to enhance motor-imagery classification in brain-computer interface

marie.constance.corsi@gmail.com

Fusion approach

Classification fusion enables a significant performance improvement

Fifteen healthy subjects (aged 28.13 ± 4.10 years, seven women) participated to the protocol No artifact removal method applied here to simulate online scenarios.

Methods Results

Semi-automatic procedure to extract features: Focus on motor area contralateral to the imagined movement Nonparametric cluster-based permutation t-test between power spectra of MI and rest epochs Extraction of the N f most discriminant features within the standard frequency bands Fig. 3: AUC distributions across the 15 subjects, for all the modalities, and for different numbers of features within the alpha-band. White circles correspond to the the median values. In all frequency bands, the type of modality significantly affected the AUC values (ANOVA, p < 10 -3 ), whereas the number of features did not have a significant impact (p > 0.05). Inter-subject variability: attributed weights

Fig. 2 :Fig. 1 :

 21 Fig. 2:Classifier fusion approach for a given frequency bin. The variables p i and 𝜆 i stand for the posterior probability and the weight parameter associated with the modality i,

Fig. 4 :

 4 Fig. 4: Contribution of different modalities to the individual performance. Piediagrams show the i values (in percentage) obtained for each modality via the fusion approach.

Acknowledgments

This work was partially supported by French program "Investissements d'avenir" ANR-10-IAIHU-06; "ANRNIH CRCNS" ANR-15-NEUC-0006-02 and by Army Research Office (W911NF-14-1-0679).


Marie-Constance Corsi

Mario Chavez

Denis Schwartz

Laurent Hugueville

Ankit N Khambhati

Danielle S Bassett

Fabrizio De

Vico Fallani

M/EEG integration to enhance motor-imagery-based brain-computer interface performances

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction:

Brain-computer interface (BCI) is a potential tool for rehabilitation and communication. Most of the BCI experiments relies on the electroencephalography (EEG). Despite its clinical applications, BCI faces to both engineering and user-oriented challenges to improve its spreading. In this work, we assess the possibility of integrating electroencephalographic (EEG) and magnetoencephalographic (MEG) signals to enhance the classification performance in motor imagery-based BCI.

Material, Methods and Results:

We performed an offline classification from a dataset which gathers simultaneously recorded M/EEG signals from 15 healthy subjects (aged 28.13±4.10 years, 7 women). We used the one-dimensional two-target box-tasks experiment in which the subjects imagined a movement with the right hand or remained at rest, depending on the position of the target. During the first 5 runs, only the target was displayed (training phase) followed by 6 runs with a provided feedback (testing phase). For each modality (EEG, magnetometers -MAG and gradiometers -GRAD), we extracted the relevant features from training recordings. Then, we performed a classification of the testing data by integrating the classifiers' output from each modality via the Bayesian fusion approach, in which contribution of each modality is modulated via an attributed weight computed from the associated posterior probability. To compare classification performances between the fusion and the single-modality approach, the classification accuracy was estimated with the area under the curve (AUC). Significant changes of event-related de/synchronization appeared in alpha and beta band in all modalities. Results show that modality significantly affects the classification performance (ANOVA, p<0.001). Averages of 0.58±0.07, 0.58±0.09, 0.61±0.10, and 0.66±0.11 were obtained with EEG, MAG, GRAD and fusion classifiers respectively. In 13 subjects, the fusion led to an improvement of the AUC in comparison with single-modality approach, with relative increments ranging from 1.3% to 50.9%.

Discussion:

By using a rather simple classifier, we could include a reduced number of specific features involved in the motorrelated neural mechanisms such as ERD in alpha and beta bands. More sophisticated approaches using the whole feature space, such as support vector machines and Riemannian geometry as well as alternative fusion strategies, but also classification in source space to improve spatial resolution, can be further evaluated. Significance: The proposed fusion method led, in a large majority of subjects, to a reduction in the subjects' mental state misclassifications. Our weighting approach enabled to adapt the modality choice according to the subject and the session. Current searches focused on MEG sensors miniaturization will probably enable a larger diffusion of the integration of M/EEG features to further enhance BCIs performances.