Christian Glacet
email: christian.glacet@gmail.com

Nicolas Hanusse
email: nicolas.hanusse@labri.fr

David Ilcinkas
email: david.ilcinkas@labri.fr

Colette Johnen
email: johnen@labri.fr

Disconnected components detection and rooted shortest-path tree maintenance in networks $

Keywords: routing algorithm, shortest-path, disconnected network, self-stabilization

Disconnected components detection and rooted shortest-path tree maintenance in networks

Christian Glacet, Nicolas Hanusse, David Ilcinkas, Colette

Introduction

Routing algorithms using the computation of distance/path vectors, like RIP (Routing information protocol) or BGP (Border Gateway Protocol), are based on the construction of shortest-path trees. For any destination r, a shortest-path tree rooted at r is implicitly built by the routing scheme. Because of the dynamics of the network, it may happen that the network is disconnected. Routing to node r is only guaranteed from the nodes that belong to the same component as r, namely V r . For the other nodes, one should remove, in the routing tables, information to reach r in order to prevent routing messages that will anyway never reach r, and thus to save some bandwidth. A legitimate configuration is characterized by the fact that every node that belongs to V r knows a route to r and every node not in V r detects that r is not in its own component. The difficulty of converging toward a legitimate configuration is called, in this context, the count-to-infinity problem [START_REF] Leon-Garcia | Communication Networks[END_REF]: for nodes that do not belong to V r , some control messages keep on being exchanged infinitely in order to find a path to r. At the same time, the updates of routing tables for nodes belonging to V r should be done as quickly as possible.

In practice, the most standard techniques consist in exchanging distance/path vectors periodically and in using some timers in order to guess if a node is still within V r . However, the convergence is usually only guaranteed under some assumptions (i) on the asynchrony of the network and/or (ii) on some known upper bound on the diameter or the size of the network. The convergence towards a legitimate configuration can be often provided by self-stabilizing algorithms, for which the correctness is guaranteed for any initial configuration.

However, solutions of the literature dedicated to the maintenance of a BFS tree or shortest paths are mainly for connected networks. Using them, we still face the countto-infinity problem in the disconnected components.

In the routing context, it is not always required to store information for every node. In compact routing schemes [START_REF] Abraham | Compact name-independent routing with minimum stretch[END_REF][START_REF] Gavoille | On the communication complexity of distributed name-independent routing schemes[END_REF], only some shortest-path trees completely spanning the connected components are built and need to be maintained. Given a set of roots r 1 , r 2 , . . . , r k , we aim at providing silent1 self-stabilizing algorithms that both maintain a shortest-path tree toward each r i , for nodes of V ri , and detect the nodes that no longer belong to V ri . In the following, we present an algorithm for a single root but our solution holds for any k. The identifiers of nodes do not need to be unique. Only r i 's identifiers should be different in order to distinguish the different roots. Thus, for k = 1, our self-stabilizing algorithm works in anonymous networks in the semi-uniform model: all nodes except one, the root, perform the same distributed algorithm.

In the asynchronous setting, the expressiveness of distributed algorithms is given by the scheduling of distributed processes. A given hypothesis on the scheduling is called a daemon. The highest level of asynchrony is called the unfair daemon since there is no restriction at all on the sequence of actions. In distributed computing, many algorithms works only for some assumption or restriction of daemons and it is always challenging to propose a solution for the unfair daemon. Having a protocol that works without any assumption on the scheduling can be very crucial when dealing with: (i) systems with very high inherent asynchrony (process speeds are not constant and/or processes have very heterogeneous speeds), e.g., ad-hoc networks; (ii) safety-critical systems, i.e., systems with low to no tolerance of (software) failures. In this latter case it is not acceptable to use a software that may crash, even if these crashes would happen under some unlikely scenarios. We will focus on unfair daemon for our study.

The performance of an asynchronous distributed algorithm is often measured by the time complexity expressed as a number of rounds. Informally, a round is the smallest fragment of time for which every distributed process can compute at least one execution step. Thus, rounds intuitively count the number of execution steps of the slowest process. Note that the number of steps is rarely analyzed in the literature. The first paper containing a self-stabilizing BFS construction with a bound on the number of steps was only published in 2009 [START_REF] Cournier | Light enabling snap-stabilization of fundamental protocols[END_REF] (17 years after the first paper presenting a self-stabilizing BFS construction: the Huang and Chen algorithm [START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF] in 1992). Moreover, in this 2009 paper, the algorithm is not silent, meaning that some useless actions can take place forever.

With an extra cost in terms of memory and a convergence time of O(n) rounds for an n-node network, the asynchronous unison allows to transform any self-stabilizing algorithm designed under a weak daemon, the distributed fair daemon, into one dealing with the unfair daemon [START_REF] Boulinier | When graph theory helps self-stabilization[END_REF]. However, there are no guaranteed bounds on the number of steps. Thus, it is always difficult to provide a self-stabilizing algorithm working under the unfair daemon and providing theoretical bounds simultaneously on the number of rounds and the number of steps.

Related works

Self-stabilizing single-destination shortest-path constructions. The single-destination shortest-path problem is to find shortest paths from all vertices in the graph to a single destination vertex r. Edges can have weights and the length of a path corresponds to its sum of weights. The oldest distributed algorithms are inspired by the Bellman-Ford algorithm. In the articles dedicated to self-stabilizing algorithms in asynchronous networks, the difficulty is to find an algorithm that runs under the worst possible scenario. A scenario is a sequence of computational steps which is controlled by an adversary called daemon. In [START_REF] Chandrasekar | A self-stabilizing distributed algorithm for all-pairs shortest path problem[END_REF][START_REF] Huang | A self-stabilizing algorithm for the shortest path problem in a distributed system[END_REF], self-stabilizing algorithms for the single-destination shortest-path problem are presented; both protocols require a central daemon, that is only one process can be executed at each instant. In [START_REF] Huang | A self-stabilizing algorithm for the shortest path problem assuming the distributed demon[END_REF], Huang proves that the algorithms in [START_REF] Chandrasekar | A self-stabilizing distributed algorithm for all-pairs shortest path problem[END_REF][START_REF] Huang | A self-stabilizing algorithm for the shortest path problem in a distributed system[END_REF] also work under the unfair daemon, which is the most general daemon. However, no upper bounds on the time (rounds or number of execution steps) are given. The same author presents an algorithm under the read/write separate atomicity model (Dolev Model) in [START_REF] Huang | A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity[END_REF].

In [START_REF] Arora | Composite routing protocols[END_REF][START_REF] Cobb | Stabilization of general loop-free routing[END_REF][START_REF] Johnen | Route preserving stabilization[END_REF], self-stabilizing algorithms for the single-destination shortest-path problem are presented; these algorithms ensure the loop-free property: after any edge weight changes, even during the rebuilding phase, there is always a path from any node to the destination. More generally, none of these articles provide tight bounds on the complexity of the convergence time in the most general asynchronous model, the unfair daemon, and the presented algorithms are not silent in the disconnected components.

Self-stabilizing breadth-first tree constructions. Whenever edges do not have any weight, shortest-path trees correspond to breadth-first trees. To our knowledge, this restriction does not help to get all the desirable guarantees. Chen et al. present the first selfstabilizing BFS tree construction in [START_REF] Chen | A self-stabilizing algorithm for constructing spanning trees[END_REF] under the central daemon. Huang et al. present the first self-stabilizing BFS tree construction in [START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF] under the unfair distributed daemon. In [START_REF] Chen | A self-stabilizing algorithm for constructing spanning trees[END_REF][START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF], the exact network size has to be known by all nodes. Dolev, Israeli and Moran in [START_REF] Dolev | Self-stabilization of dynamic systems assuming only Read/Write atomicity[END_REF] present the first self-stabilizing BFS spanning-tree construction algorithm under read/write atomicity.

Blin et al. in [START_REF] Blin | Loop-free super-stabilizing spanning tree construction[END_REF] present a universal transformer of self-stabilizing tree construction with any metric on semi-uniform networks to a loop-free super-stabilizing algorithm under the fair daemon. All these cited works assume that the network is a connected graph.

According to our knowledge, only the two following works [START_REF] Cournier | Light enabling snap-stabilization of fundamental protocols[END_REF][START_REF] Cournier | The first fully polynomial stabilizing algorithm for BFS tree construction[END_REF] take interest in the computation of the number of computation steps required by their algorithms. The algorithm in [START_REF] Cournier | Light enabling snap-stabilization of fundamental protocols[END_REF] has an upper bound on the number of steps of O(∆.n 3 ) (∆ being the maximum node degree in the network). The algorithm in [START_REF] Cournier | Light enabling snap-stabilization of fundamental protocols[END_REF] is not silent, so some nodes change infinitely often their state. The silent algorithm in [START_REF] Cournier | The first fully polynomial stabilizing algorithm for BFS tree construction[END_REF] has a convergence time O(D 2 ) rounds having at most O(n 6 ) computation steps. All these cited works assume that the network is a connected graph.

Self-stabilizing routing algorithm. In [START_REF] Bein | Self-stabilizing local routing in ad hoc networks[END_REF], Bein et al. present a self-stabilizing algorithm building local routing tables under the fair daemon (the tables ensure the routing from any node v to its t closest nodes) in O(D) rounds in the connected component, but in O(t) rounds within the disconnected component. Choosing the parameter t correctly helps to tackle the count-to-infinity problem. However, it means that in order to use their solution an upper bound on the network size has to be known. Cobb and Huang [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF] propose an algorithm dedicated to the construction of shortest-path trees defined by any maximizable routing metrics. This algorithm works without any knowledge on the network but the correction is proved only for a restrictive class of asynchronous scenarios, namely the centralized weakly-fair daemon. Unfortunately, no upper bound on the number of execution steps is given.

Leader election algorithms. Another way to tackle our problem is to focus on the problem of leader election, as in [START_REF] Datta | Self-stabilizing leader election in optimal space under an arbitrary scheduler[END_REF][START_REF] Altisen | Self-stabilizing leader election in polynomial steps[END_REF]. It has the advantage of running under the most general daemon, the unfair one, without any knowledge about the network topology. In [START_REF] Datta | Self-stabilizing leader election in optimal space under an arbitrary scheduler[END_REF], for each component, a BFS tree rooted at the selected leader is built within 4n + 11D + 4 rounds. Whereas in [START_REF] Altisen | Self-stabilizing leader election in polynomial steps[END_REF], leader election is performed within 3n + D rounds by building a spanning tree rooted at the leader. In the case of routing, it is obviously preferable to have a shortest-path tree instead of a spanning tree, therefore a realistic candidate for our purpose would be [START_REF] Datta | Self-stabilizing leader election in optimal space under an arbitrary scheduler[END_REF]. Note that D stands for the diameter of the unweighted network.

These algorithms build, in each component, a tree rooted at the node with the smallest identifier. They could be tweaked to get semi-uniform algorithms that perform disconnection detection at the same time. To do so, instead of electing nodes based on their identifier, election would be done based on shared variables (and lexicographical order). Let us call these variables id, and change the algorithm in such a way that every node maintains its variable id equal to its identifier preceded by 0 if its r, or a 1 otherwise. After running this slightly modified election algorithm, every node can detect whether it belongs to the connected component of r by simply observing the first character of the elected node's identifier. This modification would only add a single round to the convergence time. However, it is not clear what would be the convergence time of these two algorithms for weighted networks. Moreover it is an interesting question to investigate whether it is possible to build a shortest-path tree in a smaller number of rounds. Disjunction algorithm. Another potential candidate for our problem would be the algorithm proposed in [START_REF] Datta | Self-stabilizing silent disjunction in an anonymous network[END_REF] to solve the disjunction problem. It is silent and works with the assumption of an unfair daemon. This algorithm has a convergence time of O(n) rounds but unfortunately no precise bound on the step complexity is given.

As a conclusion, there are no self-stabilizing algorithms in the literature that both maintain shortest-path trees and detect disconnected components in the most general scheduling scenario, the unfair daemon, while providing bounds on the number of rounds and the number of execution steps. Table 1 shows a summary of the BFS and shortestpath tree algorithms dealing with disconnected components.

Model

A distributed system S is an undirected graph G = (V, E) where the vertex set V is the set of nodes and the edge set E is the set of communication links. A link {u, v} belongs 4 [START_REF] Bein | Self-stabilizing local routing in ad hoc networks[END_REF] [20]

[21] with a simple [START_REF] Datta | Self-stabilizing silent disjunction in an anonymous network[END_REF]

(v) = {u ∈ V | {u, v} ∈ E}.
Each edge {u, v} has a positive weight denoted w(u, v); this notion is naturally extended to paths: the weight of a path is the sum of its edge weights. In the following, D stands for the hop-diameter of the underlying graph, that is the maximum over all pairs (u, v) of the minimum number of edges in a shortest path from u to v. The weighted distance between the nodes u and v is denoted d(u, v), it is the minimal weight of a path from u to v (+∞ if no such paths exist). Each node v maintains a set of shared variables such that v can read its own variables and those of its neighbors, but it can modify only its variables. The state of a node is defined by the values of its local variables. The union of states of all nodes determines the configuration of the system. The program of each node is a set of rules. Each rule has two parts, the guard and the action. The guard of a v's rule is a Boolean expression involving the state of the node v, and those of its neighbors. The action of a v's rule updates v's state. So, every rule will be graphically described by two braces. The first brace contains the predicates such that their conjunction is the rule guard; and the second brace contains the rule action (i.e. one or several local variable updates).

In a configuration, a rule can be executed only if it is enabled, i.e., its guard evaluates to true. A node is enabled in a given configuration if at least one of its rules is enabled. A configuration is said to be terminal if and only if no node is enabled. In a semi-uniform algorithm, all nodes except one, denoted r, perform the same distributed algorithm. The set V r denotes the connected component of the distinguished node r. In anonymous networks, nodes do not have distinct identifiers. However, we assume that a node can distinguish its neighbors since out-links of every node can be locally numbered.

During a computation step under the daemon S, c i → S c i+1 , one or several enabled nodes in configuration c i are selected by the daemon S. Theses nodes will simultaneously and atomically read their neighbors states and then perform their actions so that the system reaches the configuration c i+1 from c i . An execution e under daemon S is a sequence of configurations e = c 0 , c 1 , • • • , where c i+1 is reached from c i by one computation step under S: ∀i 0, c i → S c i+1 . The centralized daemon selects at each computation step only one node while a distributed daemon selects any non-empty set of enabled nodes. Any daemon that only produces weakly-fair executions, that is executions in which an always enabled node is eventually activated, is called a weakly-fair daemon. There is no requirement on the unfair daemon, it may produce non weakly-fair execution. Finally, we say that an execution e is maximal if it is infinite, or if it reaches a terminal configuration.

Definition 1 (Silent Self-stabilization to L). Let L be a subset of C, called set of legitimate configurations. A distributed system is silent and self-stabilizing under the daemon S to L if and only if the following conditions hold:

• all executions under S are finite; • all terminal configurations belong to L.

Stabilization time. We use the round notion to measure the time complexity. The first round of an execution

e = c 1 , c 2 , • • • is the minimal prefix e 1 = c 1 , • • • , c j ,
such that every node having an enabled rule in c 1 either executes a rule or is neutralized during a computation step of e

1 . A node v is neutralized during a computation step c i → c i+1 , if v is enabled in c i but not anymore in configuration c i+1 .
Let e be the suffix of e such that e = e 1 e . The second round of e is the first round of e , and so on.

The stabilization time is the number of rounds of an execution reaching a legitimate configuration from any initial one.

Definition 2 (Round of a component).

The end of the i + 1-st round in the (connected) component H ⊆ G in a computation e is defined recursively as the configuration of the execution e where every node v ∈ H(V ) that was enabled at the end of the i-th round of e in H have been either activated or neutralized once.

Note that the first round of a component H ⊆ G may be shorter than the (global) first round (when the component is not explicitly given, then the round is assumed to be global, that is for the whole graph). Indeed, some nodes outside of H may be enabled at the beginning of the execution and may take a long time before being activated or neutralized. More generally, the i-th round of a component may end earlier than the (global) i-th round.

Definition 3 (Node convergence).

A node v is said to have converged to its final state s under the daemon S at the configuration c 1 if along all executions under S from c 1 , the node v keeps its state s.

In this paper, we consider a particular problem called the Disconnected Components Detection and rooted Shortest-Path tree Maintenance (DCDSPM) problem. See Fig. 1 for an illustration.

Definition 4 (The DCDSPM problem).

Given a not necessarily connected network with a distinguished node r, the DCDSPM problem consists in converging to a configuration where every node in the connected component of r knows an incident edge on a shortest-path leading to r, and any other node detects that it does not belong to the same connected component as r.

Our contribution

We present an algorithm solving the DCDSPM problem and called FDcD. It shares some ideas with the self-stabilizing silent shortest-path tree algorithm originally presented in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF] under the centralized weakly-fair daemon. The part of our algorithm common with r the algorithm in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF] is the use of a specific status (E/dirty), which is propagated from a node that has detected an anomaly to all nodes in its sub-tree. This technique is a wellknown strategy to destroy illegal branches that was already used, for example, in [START_REF] Huang | Self-stabilizing depth-first token circulation on networks[END_REF] and [START_REF] Johnen | Distributed self-stabilizing depth-first token circulation with constant memory[END_REF]. The technical differences with [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF] are detailed at the end of Section 2.

Our main contribution is an in-depth analysis of FDcD that holds under the most general daemon, the distributed unfair one. More precisely, we show that Algorithm FDcD fully solves the DCDSPM problem. That is, we prove that, on anonymous semiuniform weighted networks, it builds a shortest-path tree rooted at r in V r and explicitly isolates the nodes in all other connected components. No other algorithm solving the DCDSPM problem under the unfair daemon was known prior to this work. Note that our algorithm can easily be adapted to a wider class of routing metrics as shown in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF]. We also prove that Algorithm FDcD converges to a legitimate configuration within less than 2n + D rounds in any n-node weighted graph of hop-diameter D. Thus the time complexity of algorithm FDcD improves the one of [START_REF] Datta | Self-stabilizing leader election in optimal space under an arbitrary scheduler[END_REF] by a factor at least 2 in connected networks. Finally, we present an exponential lower bound on the worst-case number of steps, which also applies to the algorithm presented in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF]. According to our knowledge, this is the first time that a lower bound on the number of computation steps is provided for an algorithm building and maintaining a rooted shortest-path tree. The technique used to get this lower bound is novel and could be used to get lower bounds for other algorithms.

Algorithm FDcD

This section is devoted to the presentation of our algorithm, FDcD (Fast Disconnection Detection). The value of variable st indicates the status of the node: I for isolated (the node has no parent and no children), E for erroneous, and C for correct.

A non-isolated node u (st u = I) has two other meaningful variables: the variable d u containing the shortest weighted distance to r, and the variable parent u containing a pointer to the first out-link on the shortest path to r. Thus, only non-isolated nodes can belong to a branch (i.e. have children and/or a parent).

More formally, a node v is considered to be the child of another node u if v is a neighbor of u, neither u nor v has status I, v points to u (parent v = u), and the known distance to the root via u (d u + ω(u, v)) is not larger than d v . This leads to the following definition of the set children u . For example, in Fig. 5.a, p 1 has the isolated status I, so children

Definition 5 (Children of node u). children

u = {v ∈ Γ(u) | (st u = I) ∧ (st v = I) ∧ (parent v = u) ∧ (d v ≥ d u + ω(u, v))} R r            P root (u) ≡ (st r = C) ∨ (parent r = r) ∨ (d r = 0)    st r ← C parent r ← r d r ← 0
p1 = ∅. Besides, no node u satisfies (d u > d p2 ) ∧ (parent u = p 2 )) so p 2 has no children: children p2 = ∅. Finally, children p3 = {p 4 } because p 4 is the only node u that satisfies (d u > dp 3 ) ∧ (parent u = p 3 ).
We are now ready to provide the full description of the algorithm. The single rule for node r is given in Figure 2. The rules for the other nodes are given in Figure 3. Only nodes with status C may gain new children; and only nodes without children and with the status C may increase the value of their variable d (rule R C ). These two properties ensure that the execution of the rule R C by a node u does not create any anomaly (because a node u doing R C during a computation step has no children and it cannot gain children during this step). A given node u detects an anomaly in the relationship with its parent in four cases:

R C                                     P create (u) ≡ (st u = C) ∧ (children u = ∅) ∧ (∃v ∈ Γ(u) | st v = C) P update (u) ≡ (∃v ∈ Γ(u) | (st v = C) ∧ (d v + ω(u, v) < d u )) P correct (u) ≡ [ (parent u / ∈ Γ(u)) ∨ (d u = d parentu + ω(u, parent u )) ∨ (st parentu = C) ∨ (st u = C) ] ∧ [∃v ∈ Γ(u) | (st v = C) ∧ (d v + ω(u, v) = d u ) ]    st u ← C parent u ← argmin (v∈Γ(u))∧(stv=C) (d v + ω(u, v)) d u ← d parentu + ω(u, parent u ) R E        P error (u) ≡ (st u = C) ∧ (∀v ∈ Γ(u) | (d u < d v + ω(v, u)) ∨ (st v = C)) st u ← E R I        P isolate (u) ≡ (st u = E) ∧ (children u = ∅) ∧ (∀v ∈ Γ(u) | st v = C) st u ← I
• the parent node is not in its neighborhood -(parent u / ∈ Γ(u)) is satisfied; • the value of d u is not coherent with the value of d parentu -(d u = d parentu + ω(u, parent u )) is satisfied; • it, or its parent, has not status C -(st u = C) ∨ (st parentu = C) is
satisfied; • it is not the best out-link for the destination r -P update (u) is satisfied.

Besides, a node v is said to be an alternative parent for node u if it has status C and if:

• v is a better out-link than parent u (i.e. the cost of the path from u to r going through v is smaller than the cost of the path going through parent u ) -P update (u) is satisfied;

• or v is an as good out-link as parent u -(st v = C) ∧ (d v + ω(u, v) = d u )
is satisfied.

Note that the main difference with the algorithm presented in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF] is in the definition of an alternative parent. In their definition, a node is not considered to be an alternative parent in the case described by the second item.

00 00 00 11 11 11 00 00 00 11 [START_REF] Huang | A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity[END_REF] If a correct node u (i.e. with st(u) = C) detects an anomaly in the relationship with its parent, then u is enabled because P update (u), P correct (u), or P error (u) is satisfied. More precisely, P update (u) or P correct (u) is satisfied when u has an alternative parent; P error (u) is satisfied when u does not have an alternative parent.

When a node u detects an anomaly in the relationship with its parent and there is no alternative parent, u takes the status E (rule R E ). Then, u's children have an anomaly in the relationship with their parent, u. Thus the nodes in the sub-tree rooted at u will take the status E or will change sub-tree. When a leaf has the error status it quits its branch: either it becomes isolated (rule R I ) or it joins a "correct" branch (rule R C ). Therefore every erroneous sub-tree is eventually deleted.

A synchronous execution is presented in Fig. 4 (i.e. in each computation step of the execution, all enabled nodes perform their enabled action). The graph has two disconnected components: one containing only r and another one containing the other nodes. During the first step, a node performs the rule R C to decrease the value of its d variable. During the second step, another node performs the rule R C to change branch in the illegal tree. Meanwhile, during the first three computation steps, the E status is propagated from the illegal root to the leaves by the execution of the rule R E . More precisely, during the first step, the illegal root performs this rule; during the second step, the children of the illegal root perform this rule; finally during the third step, the leaves of the illegal tree perform this rule. Then, during the last three computation steps, the I status is propagated backward from the leaves to the illegal root (nodes execute the rule R I ).

Any configuration during the execution of algorithm FDcD induces a BFS tree rooted at node r that spans a subset of V r , a forest rooted at different illegal roots and some isolated nodes.

Definition 6 (Correct state).

A node u is said to be in a correct state if:

st u = C, d u = d(u, r) and, if u is not the root r, parent u ∈ Γ u and d(parent u , r) = d u - ω(u, parent u ).
In Fig. 5.a, nodes on the first line (i.e. p 1 to p 7 ) are neighbors of the root, which is in its correct state. Nodes p 1 and p 2 satisfy P create because they do not have the correct status and they are childless. Nodes p 3 and p 4 can decrease their d value and thus satisfy P update . The distance value of p 5 , p 6 , and p 7 is equal to the final correct value 1, so they do not satisfy P update . However, parent p5 and p 7 have the erroneous status, which implies that P correct (p 5 ) and P correct (p 7 ) are satisfied. Finally, the value of d p6 is not coherent with the value of d parentp 6 ; so P correct (p 6 ) is satisfied. After the computation step where all nodes on the first line perform the rule R c , the configuration shown in Fig. 5.b is reached: all nodes on the first line are in their correct state.

Definition 7 (Legitimate state).

A node u is said to be in a legitimate state if:

• it belongs to V r and is in a correct state; • or it does not belong to V r and it has status I.

Definition 8 (Legitimate configuration).

A legitimate configuration is a configuration where every node is in a legitimate state.

Coming back to the algorithm of [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF], we point out some differences. First of all, the condition for a node to set its status to E/dirty is stronger in our algorithm than in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF]. In [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF], as soon as a node has detected an anomaly or its parent has E/dirty status, then the node can take the E/dirty status. In our algorithm, only a node that cannot find an alternative parent has to take the E/dirty status, if it has detected an anomaly or if its parent has the E/dirty status. Another difference is that the rules of a node are not exclusive in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF]. It means that a node can have several enabled rules at the same time. The algorithm of [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF] is thus not deterministic (even without considering the non-determinism coming from the asynchrony). There is also no discussions about the behavior of the presented algorithm in disconnected graphs and the proofs only concern the case of the fair daemon.

Correctness and convergence time of algorithm FDcD

We start this section by proving that the set of terminal configurations coincides with the set of legitimate configurations. This will be done thanks to the following two lemmas, the first one dealing with the connected components that do not contain node r, if some exist, and the second one dealing with the connected component V r containing root node r.

Correctness Lemma 1. For any connected component H not containing node r, any terminal configuration in H is a legitimate configuration.

Proof. The proof is done by contradiction. So consider that for some connected component H not containing node r, there exists a terminal configuration in which at least one node has not status I.

Further assume that there exists some node that has status C. Consider a node u ∈ H with status C having the smallest distance value d u . By construction, u can apply rule R E , which is in contradiction with the configuration being terminal. Therefore any node that does not have status I must have status E.

Consider now a node u ∈ H that has status E having the largest distance value d u . By construction and from the previous point, this node has no child and no neighbor have status C. Therefore node u can apply rule R I , and we obtain again a contradiction, which concludes the proof of the lemma.

Lemma 2. Any terminal configuration within the connected component V r is legitimate.

Proof. The proof is done by contradiction. Let consider it exists some non-legitimate terminal configuration of the connected component V r .

Further, assume that there exists some node that has status E. Consider a node u of V r with status E having the largest distance value d u . Note that no node v that has status C can be a child of u, otherwise v could apply rule R E or rule R C . Therefore, node u has no child and thus can apply rule R I or rule R C , a contradiction.

Nodes have thus either status C or I. Assume now that there exists some node that has status I. Consider some node u with status I having at least one neighbor with status C. Such a neighbor node must exist because we are considering a connected component without any node with status E, but with at least one node that has status C, namely node r. Obviously, node u can apply rule R C , a contradiction. So every node in V r must have status C. Now consider a node u in V r having the smallest distance value d u among the nodes in V r that are not in a correct state. Then, either it exists some node v with status C in Γ(u) such that d u ≥ d v + ω(u, v), or not. If such a node v exists then node u can apply rule R C . If it does not, then, by definition, it can apply rule R E . In both those cases there is a contradiction, which concludes the proof.

After noticing that any legitimate configuration is a terminal one, we conclude with the following corollary. Corollary 1. The set of terminal configurations coincide with the set of legitimate configurations.

Convergence

We now prove that algorithm FDcD always terminates within 2n + D -2 rounds under a weakly-fair daemon, where D is the hop-diameter of the connected component containing r. Before proceeding with the proof, let us introduce some useful concepts.

Definition 9 (Branch).

A branch is a maximal sequence of nodes v 1 , • • • , v k , for some integer k ≥ 1, such that none of the nodes have status I and, for every i ≤ k, we have v i ∈ children vi+1 . The node v i is said to be at depth k -i. If v k = r but the state of r is not terminal, or simply if v k = r, the branch is said to be illegal, otherwise, the branch is said to be legal.

The first lemma essentially claims that all nodes that are in illegal branches progressively switch to status E within n rounds, in order of increasing depth (illegal branches may vary during the process though). Lemma 3. Fix any integer i ≥ 1, and any connected component H. Starting from the beginning of round i of H, there does not exist any node of H both in state C and at depth less than i -1 in an illegal branch.

Proof. We prove this lemma by induction on i. The base case i = 1 is obvious so assume that the lemma holds for some integer i ≥ 1. Consider any node u of H both with status C and depth i -1 in an illegal branch at the beginning of round i of H. If u = r, then r executes R r during round i of H. Otherwise (u = r), by induction hypothesis, the parent of u is not in state C at that time. Therefore u is enabled at the beginning of round i. During round i, it will either execute rule R E and thus switch to state E, or it will execute rule R C (making it switch branch).

Note that, from the beginning of round i, no node can ever choose a parent which is at depth smaller than i -1 in an illegal branch because those nodes will never be in state C, by induction hypothesis. This is also true for node u if it applies rule R C in round i. Therefore, no node can become in state C at depth smaller than i in an illegal branch. This concludes the proof of the lemma. Root node r does not belong to an illegal branch after the first round. Therefore, after the first round, the number of nodes of an illegal branch cannot be more than n -1. We thus obtain the following corollary.

Corollary 2. For any connected component H, once round n -1 in H has terminated, no node in an illegal branch in H has status C.

The next lemma essentially claims that, within at most n -1 subsequent rounds, the maximal length of an illegal branch progressively decreases until no illegal branches remain.

Lemma 4. Fix any integer i ≥ 0, and any connected component H. Starting from the beginning of round n + i in H, there does not exist any node of H at depth larger or equal to n -i -1 in an illegal branch.

Proof. We prove the lemma by induction on i. The base case i = 0 is obvious so assume that the lemma holds for some integer i ≥ 0. By induction hypothesis, at the beginning of round n + i, no node is at depth larger or equal to n -i -1. Therefore, the nodes at depth n -i -2 in an illegal branch have no children and are thus enabled at the beginning of round n + i. These nodes will thus all be executed within round n + i (they cannot be neutralized as no children can connect to them). We conclude the proof by noticing that, from Corollary 2, once round n -1 has terminated, every node in an illegal tree is in state E, and thus any node in an illegal branch that gets executed from this time will not be anymore in any illegal branch. Corollary 3. For any connected component H, once round 2n -2 in H has terminated, there are no illegal branches in H.

Note that in a connected component that does not contain the root r, there are no legal branches. Since the only way for a node to be in no branch is to have status I, we obtain the following result. Corollary 4. For any connected component H not containing r, after 2n -2 rounds in H, every node v of H has status I.

After 2n -2 rounds, the connected components not containing r are in a legitimate state. In the connected component V r containing r, Algorithm FDcD may need additional rounds so that the correct distances to r are correctly propagated.

In the following lemma, we use the notion of hop-distance to r defined below.

Definition 10 (Hop-distance to the root node r). A node v is said to be at k hops from r if k is the minimum number of edges of a shortest path from v to r.

Lemma 5. Consider any integer i ≥ 0. For any execution of Algorithm FDcD, starting from the beginning of round 2n -2 + i, every node in component V r at most i hops from r is in a correct state.

Proof. Let us prove the lemma by induction on i. Firstly, we need to remark that after one single round, node r has necessary converged to the correct state. So the base case i = 0 holds, as we can assume n to be at least 2. Secondly, at round 2n -2, from Corollary 3, every node either belongs to a legal branch or have status I, thus any node v ∈ V r always stores a distance d such that d ≥ d(v, r), its actual weighted distance to r. By induction hypothesis, every node at at most i hops from r has converged to a correct state before round 2n + i -1. Therefore, at the beginning of round 2n + i -1, every node v at i + 1 hops from r which is not in a correct state has rule R C enabled. Thus, at the end of round 2n + i -1, every node at at most i + 1 hops from r is in a correct state (such nodes cannot be neutralized during this round). Also, these nodes will never change their state since there are no nodes other than their parent that can make them get closer to r than their current parent.

Putting together all the results of this section, we obtain, for algorithm FDcD, the following theorem.

Theorem 1. Under a weakly-fair daemon, Algorithm FDcD always converges to a legitimate state within 2n + D -2 rounds, where D is the hop-diameter of the connected component V r containing node r.

Convergence under an unfair daemon

In this section, we will prove that algorithm FDcD always converges to a legitimate state, even under an unfair daemon. The proof, by contradiction, will go as follows. After noticing that a node activated infinitely often must execute rule R C infinitely many times, we will prove that nodes activated infinitely often must have globally increasing distance values. This means that these nodes will eventually behave as if the nodes activated a finite number of times do not exist. This will lead to a contradiction, as we proved before that a connected component has to become silent after a finite number of rounds. Lemma 6. If at some time a node has been executed k times, then it must have executed rule R C at least k-2 3 many times.

Proof. When a node with status E is enabled, it can either execute rule R C or rule R I . Moreover, a node with status I can only execute rule R C . Thus between two consecutive executions of rule R C by a node, only two other rule executions can happen.

Let us now introduce a useful notation for the next lemmas. Definition 11. A node u is said to execute a rule with (distance) value δ if the distance value d u is equal to δ immediately after this rule execution. Lemma 7. Rule R C cannot be executed infinitely often with the same distance value.

Proof. For the purpose of contradiction, consider any (infinite) execution e of algorithm FDcD in which rule R C is applied infinitely often with the same distance value. Let d min be the minimum such infinitely often used value. Let v be some node applying infinitely often rule R C with distance value d min . Now consider some suffix e of e in which no node with a distance value smaller than d min will ever apply any rule. Note that such a suffix e must exist, by definition of d min .

Let consider the maximal suffix e of e starting when node v has a parent u such that d u = d min -ω(u, v). By definition of e , node u will remain in state C and be the better possible parent within e , therefore node v will not apply any rule in e , contradicting the assumption that node v applies infinitely often rule R C .

We are now ready to conclude about the convergence under an unfair daemon.

Lemma 8. Every execution is finite.

Proof. For the purpose of contradiction, let us assume that there exists an infinite execution e. Let F , resp. F , be the set of nodes executed finitely, resp. infinitely, many times in this execution, and let F be the set of nodes in F that are neighbors of at least one node in F . Note that the set F is necessarily non-empty as it contains at least node r.

Let execution e 1 be a suffix of e in which every node v ∈ F is never executed. In e 1 , only the nodes from F will be executed. Let d max be the maximum distance stored in d v for any node v ∈ F within e 1 . From Lemma 7, if a node executes an infinite number of steps during an execution of algorithm FDcD, then it will necessarily change its distance an infinite number of times. Moreover, distances stored at a given node cannot be negative.

Thus, there exists a suffix e 2 of e 1 such that for any node v in F , d v > d max + ω v , where ω v is the maximum weight of an edge incident to v.

Within e 2 , a node v ∈ F cannot have status C, otherwise any node v that belongs to Γ(v ) ∩ F would apply R C with distance value at most d max + ω(v, v ) which would be in contradiction with the definition of e 2 . Moreover, we have d v > d v , and thus v does not belong to children v .

Looking at the algorithm, one can observe that, if a rule can be applied for a node v ∈ F during e 2 , then it can still be applied after removing the nodes in F from the graph. In other words, the nodes in F can have the same execution in the graph obtained after removing the nodes in F . Now consider any connected component H of F . Notice that r is not a node of H. Since all nodes in H are activated infinitely many times, it means that there are an infinite number of rounds in H, without the nodes reaching a terminal configuration in H. Corollary 4 establishes that every node of H are isolated after at most 2n -2 rounds in H. Then, every node of H are and stays disabled forever, they have reached their terminal state. This concludes the proof of this lemma.

A corollary of this lemma is that any execution is weakly-fair because there are no nodes that are always enabled (at the end of a finite execution, no nodes are enabled). Therefore, the bound on the number of rounds from Theorem 1 also applies in the case of an unfair daemon. We obtain the following main theorem. Theorem 2. Under an unfair daemon, Algorithm FDcD always converges to a legitimate state within a finite number of steps and in at most 2n + D -2 rounds, where D is the hop-diameter of the connected component V r containing node r.

Lower bound on the number of steps

In this section, we prove that the step complexity of our algorithm can be as large as 2 n/2 in some n-node unweighted graphs. This lower bound is based on a family of graphs {G k } k≥1 , defined as follows.

Definition 12 (Graph G k ). For any positive integer k, the graph G k consists of one isolated node r, and k triangles with node sets {a

1 , b 1 , c 1 }, • • • , {a k , b k , c k },
where c i is merged with a i+1 , for 1 ≤ i < k. (See Fig. 6.)

In order to obtain the desired number of steps, we consider a particular initial configuration for each graph G k , called init k . In this configuration, the root node r is correctly initialized: st r = C, parent r = r, and d r = 0. Moreover, we have st a1 = C, parent a1 = a 1 , and d a1 = 1. Finally, all other nodes are in state I. As an illustrative example, the initial configuration of the graph G 3 is presented in Fig. 7. The intuition behind the exponential lower bound is the following. Node a 1 cannot stay in state C and thus eventually switches to state E, and finally to state I when becoming childless. As for node c 1 , it first switches to sate C, having a 1 as parent, then it gains state E when a 1 switches to state E. Node c 1 eventually comes back in state C when becoming childless, but this time choosing b 1 as its parent. The state E then propagates to c 1 via b 1 , both of them eventually switching to state I when becoming childless. To summarize, c 1 is basically doing twice the transition from C to E when a 1 is doing it once. More generally, we will prove that the number of such transitions by node c i+1 is twice the number of such transitions by node c i , yielding to the desired bound.

In order to derive more formally our lower bound on the number of steps, we prove by induction the following property.

Definition 13 (Property P k ). Given a positive integer k, we say that Property P k holds if and only if there exists an execution of our algorithm on G k , starting from the configuration init k , such that the node c i applies exactly 2 i-1 times the sequence of rules

R C , R E , R C , R E , R I , for 1 ≤ i ≤ k.
Lemma 9. For any positive integer k, Property P k holds.

Proof. We prove this lemma by induction on k.

Let us first consider the graph G 1 , in the initial configuration init 1 . The execution of our algorithm proving Property P 1 is defined by the following rule executions: R C by b

1 , R C by c 1 , R E by a 1 , R E by c 1 , R C by c 1 , R E by b 1 , R E by c 1 ,
and finally R I by c 1 . This execution is depicted by the concatenation of Fig. 8 and9.

Fix any positive integer k and assume that Property P k holds. We will prove that Property P k+1 holds as well. Let E k be the desired execution on G k whose existence is proved by the induction hypothesis. We now extend this execution to fit it to the graph G k+1 , with the initial configuration init k+1 , as follows.

As long as any node other than c k is concerned in E k , we can apply the same computation steps in G k+1 . Besides, whenever a rule R C is applied by c k in E k , we ensure that b k+1 and c k+1 (the neighbors that c k has in G k+1 but not in G k ) are in state I and thus do not modify the satisfiability of any predicate from rule R C (it is the case for the first execution of R C by c k and it will be the case by construction for the other executions). Moreover, after each application of R C by c k , the correct status is propagated to the the nodes b k+1 and c k+1 by having them apply rule R C , see Fig. 8.

Similarly, no predicates from R E see their satisfiability changed by the existence of these two nodes when a rule R E is applied by c k in E k . Indeed, by construction, both b k+1 and c k+1 store a greater distance than d, the distance stored by c k , because they have just applied the rule R C based on the value d, and thus have distance value d + 1. Moreover, after each such application of R E by c k , we propagate twice the status E to c k+1 (the first time directly, then through b k+1 ) thanks to the following rule executions: R E by c k+1 , R C by c k+1 , R E by b k+1 , and R E by c k+1 . Then, both these nodes switch back to their initial state I in order for the remainder of the execution E k to continue (both nodes apply Rule R I ). The sequence of added rule applications is depicted in Fig. 9. Finally, whenever a rule R I is applied by c k in E k , our construction ensures that b k+1 and c k+1 are in state I and thus do not modify the satisfiability of any predicate from rule R I .

C, d + 1 E, d E, d + 1 I I I E, d + 1 C, d + 2 C, d + 1 E, d E, d E, d E, d C, d + 1 C, d + 1 E, d + 1 E, d E, d + 2 C, d + 2 E, d + 1 E, d
This extended execution is thus well defined and has the required properties, which concludes the proof of this lemma. This technical lemma allows us to obtain the main result of this section.

Corollary 5. For any n ≥ 4, there exists a n-node graph and a particular initial configuration from which our algorithm uses at least 2 n/2 steps to stabilize.

Proof. For even values of n, this follows directly from Lemma 9. For odd values of n, it is sufficient to just add an additional isolated node to the graph G (n-3)/2 . Note that this construction can be used to obtain the same lower bound for the algorithm presented in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF].

Conclusion

Our algorithm is the first self-stabilizing algorithm to simultaneously compute shortestpath trees and discover disconnected components in the most general scheduling scenario, the unfair daemon. We also prove theoretically a linear upper bound on the number of rounds. Our work can be useful to save both memory space and messages in the setting of routing in dynamic networks without any restriction on the behavior of the distributed system.

This work, as many of the works on self-stabilization, considers the powerful model of shared memory with composite atomicity, in which, in a single atomic step, a node can read its own variables and those of its neighbors and can modify its own variables. This model allows for simpler and more elegant algorithms and proofs than other more realistic models, but does not restrict the applicability of the algorithms designed in it. Indeed, there exist general self-stabilizing transformers between this model and more realistic ones. Dolev, Israeli, and Moran proposed in [START_REF] Dolev | Self-stabilization of dynamic systems assuming only Read/Write atomicity[END_REF] a transformer from the composite atomicity model to the more realistic model of read/write atomicity: in one atomic step, a node can read the state of one of its neighboring nodes, or update its own state, but not both simultaneously. Another transformer [START_REF] Afek | Self-stabilization over unreliable communication media[END_REF] permits to go from this model to a message passing model with FIFO but unreliable bidirectional channels of communication. Finally, one can use a further transformer [START_REF] Dolev | Stabilizing data-link over non-fifo channels with optimal fault-resilience[END_REF] to handle unreliable capacity-bounded non-FIFO channels.

Our contribution can lead to some new results: the algorithm can easily be adapted to a wider class of routing metrics as shown in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF] and our exponential lower bound also holds for the algorithm in [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF].

The algorithm FDcD analyzed in this paper is very efficient in terms of number of rounds but might be costly in terms of number of steps. We have to point out that for self-stabilizing algorithms, very few results on the number of steps are known and the majority of analyses are done on restrictive scheduling scenarios.

Thus, the first natural open problem is to design a shortest-path algorithm with a polynomial step complexity while preserving a small round complexity under the unfair daemon, even if the disconnection discovering goal is removed. One has to keep in mind that under the unfair daemon, the combinatorial explosion on the number of state configurations can quickly lead to a large number of cases to be considered. There is some hope that getting a polynomial step complexity could be possible, but such an algorithm is unknown today.

It would also be interesting to experimentally compare this algorithm to (potentially) less robust ones such as [START_REF] Cobb | Stabilization of maximal-metric routing without knowledge of network size[END_REF][START_REF] Datta | Self-stabilizing leader election in optimal space under an arbitrary scheduler[END_REF][START_REF] Datta | Self-stabilizing silent disjunction in an anonymous network[END_REF] for which either the upper bound on the number of execution steps or the behavior under the most general daemon are unknown. In this paper, our focus goes to hard instances: we showed that our algorithm achieves stabilization for any initial state and any sequence of actions. Having experimental results would be very interesting but lies outside the scope of this paper, as it would require significant specific research advances. Indeed, on one hand, random uniform schedulings are very unlikely to behave as worst-case schedulings, and devising realistic probabilistic distributions remains challenging and largely open. On the other hand, it would be interesting to have experimental results for instances in which the number of execution steps tends to be large. Nevertheless, we are not aware of any experimental technique that would permit to compare different algorithms under equivalently hardcase scenarios. It seems very hard to design such experimental routines and proposing one would be a very interesting result on its own. The main difficulty in designing such an experimental protocol is that both the initial states of the processes and the scheduling of hard-(or worst-) case scenarios strongly depend on the algorithm. Thus it is not trivial at all to find a general way of generating hard instances. We therefore believe that these questions are intriguing but challenging open research subjects related to our work.

Acknowledgements

This study was partially supported by the anr project descartes (anr-16-ce40-0023) and by the anr project estate (anr-16-ce25-0009-03).

Figure 1 :

 1 Figure 1: A network where the DCDSPM has been solved. Square nodes are the nodes claiming to be in a different connected component than r.

Figure 2 :

 2 Figure 2: Algorithm FDcD on node r.

Figure 3 :

 3 Figure 3: Algorithm FDcD on node u.

Figure 4 :

 4 Figure 4: A synchronous execution

1 p 2 p 3 p 4 p 5 p 6 p 7 Figure 5 :

 175 Figure 5: An illustration of several R C executions.

3 rFigure 6 :Figure 7 :

 367 Figure 6: The graph G 3

Figure 8 :

 8 Figure 8: Rule applications performed by b k and c k after each application of Rule R C by a k .

Figure 9 :

 9 Figure 9: Rule applications performed by b k and c k after each application of Rule R E by a k .

Table 1 :

 1 Related works on BFS and shortest-path tree algorithms dealing with disconnected components.

	this paper
	modification (cf. Sec. 1.1)

Eventually, the states of all nodes remain unchanged. This notion is also referred as "quiescent" in some contexts.

This study has been carried out in the frame of "the Investments for the future" Programme IdEx Bordeauxcpu (anr-10-idex-03-02).


Vincent Rious

Sophie Plumel

An operational and institutional modular analysis framework of Transmission and System Operator Why Transmission and System Operators are not ideal ones

Transmission and System Operator (TSO) is the power flows externality market designer. And so, not only is TSO a module of power markets but its missions that are related to the management of power flows can also be studied thanks to a modular analysis. An ideal first-best TSO can then emerge as a benchmark for comparison with real TSOs. The governance structure of TSO accounts for the gap between such an ideal first-best and real TSOs. Then, although the economic theory specifies a unique arrangement to reach efficiency, the diversity of transmission governance accounts for the diversity of arrangements to manage power flows. Moreover the comparison between an ideal first-best TSO and two reference TSOs, PJM and NGC, with quite opposite features accounts for heterogeneous results among TSOs.

INTRODUCTION

One knows that Transmission and System Operator (TSO) is a module of power markets (see [15]). In this paper we only focus on the management of power flows and do not deal with balancing issues. As for the management of power flows, a TSO must achieve three main interdependent missions: the short-run power flows externality management, the development of the network (see [START_REF] Brunekreeft | Electricity transmission: an overview of the current debate[END_REF]) and the coordination with neighbouring TSOs to deal with border effects (see [START_REF] Glachant | Un marché européen de l'électricité ou des marchés dans l'Europe? Regards croisés économistes et ingénieur[END_REF]). So the management of power flows by TSO can also be studied thanks to a modular analysis. And an ideal first-best TSO can then be designed by implementing the most efficient solutions for these three missions. Nonetheless, reference TSOs such as PJM and NGC are not ideal TSOs. The governance structure of transmission (or transmission governance) imposes compatibility constraints between the implementations of TSO's missions and accounts for the gap between an ideal firstbest TSO and real TSOs.

We show that a TSO can be studied thanks to a modular analysis framework as for the management of power flows. The modules are its three missions and transmission governance. We also show that transmission governance accounts for the wide diversity of arrangements of TSOs and their inhomogeneous results.

In section 2, we present the three missions of TSO that are operational modules of the analysis framework and their possible implementations. An ideal first-best TSO is designed thanks to the most efficient implementations.

In section 3, we define a last module, transmission governance, and show that it introduces compatibility constraints between the implementations of TSO's missions.

In section 4, the two reference TSOs, PJM and NGC, with quite opposite features are studied thanks to our modular and institutional analysis framework.

A MODULAR ANALYSIS FRAMEWORK

The implementations of the three TSO's missions for the management of power flows are differentiated thanks to their level of internalisation of the power flows externality in price mechanisms. These implementations are presented assuming that the TSO is benevolent and efficient. An ideal first-best TSO is designed as a benchmark thanks to the most efficient implementations.

The short-run power flows externality management

There exist two main solutions with opposite levels of integration between the externality management scheme and the energy market to internalise network externality in energy price.

The nodal pricing is in theory the most efficient method since the power flows externality is internalised in the energy market. It gives an energy price per node indicating where it is preferable to generate or to consume one more megawatt taking into account both network losses and limitations while maximising the social surplus (see [START_REF] Schweppe | Spot Pricing of Electricity[END_REF]). The differential of nodal prices linked to externality generates a merchandise surplus for TSO. The network limitations generate also a social cost.

Under the redispatch scheme, the energy market is cleared "out of the network" at a unique system marginal price (SMP). TSO manages externality apart from the energy market by "constraining on" (and pay P on ) or "off" (and is paid P off by) some generators or consumers. The subsequent redispatch cost is borne by TSO for the short-run operation, and generally socialised to the long-term in the Use of the System (UoS) tariff. Only the redispatched units know that there are network constraints.

Each scheme can be subject to a more or less wide use of local market power by reliability-must-run generators. The redispatch scheme is said to be more sensitive to these issues because the congestion cost is socialised ( [START_REF] Harvey | Nodal and zonal congestion management and the exercise of market power[END_REF]). However, this scheme facilitates the use of standardised forward products on energy markets which may increase liquidity of marketplaces and therefore mitigate oligopolies' market power. There is a balance to find between increasing internalisation externality in energy prices, mitigating local market power and increasing liquidity of power marketplaces.

The development of the network

The development of the network is a two-part TSO's mission. The benevolent TSO invests to make the social cost decrease. And long-term locational network tariffs must complete the short-run signals to guide the location of new network users and to recover the network costs (see [START_REF] Pérez-Arriaga | Guidelines on tariff settings[END_REF]). There is no ideal theoretical solution to define this tariff and to allocate the network charges but only pragmatic ones that internalise more or less network externality.

As for the development of the network, the benevolent TSO arbitrates between on the one hand the social cost noticed from the short-run operation and anticipated from the connection requests and on the other hand the cost of network investments. Other things equal, it is equivalent to a social welfare maximisation (see [START_REF] Pérez-Arriaga | Guidelines on tariff settings[END_REF]).

As for the allocation of network charges, there are three main methods. Accommodation capacities can complete them.

Under the "deep" cost allocation method, "connection assets" and "network upgrades" are attributed to the network users that trigger the investments through a connection tariff. This method is controversial. Costs that are associated to the lumpiness of the transmission line capacity are individually allocated. And it is a one-way internalisation as positive externalities are not rewarded.

Under the "shallow" cost allocation method, the beneficiaries pay only the "shallow" part of the network, that is to say the "direct connection assets" through a connection tariff. The "network upgrades" are socialised among all or part of the network users through a UoS tariff. The network users are then only incited to be near the core of the network.

Under the "zonal" allocation method, the connection tariff is the same one as in a shallow allocation method but the UoS tariffs are spatially differentiated. Lots of variants are possible. It is an interesting method as positive externality can be internalised at least partly.

The publication of "accommodation capacities" should make the allocation method more auditable to the network users. The "accommodation capacity" of a node is the nodal quantity of new generation or consumption that can be connected to this node without creating new congestion.

The coordination of TSOs

The third TSO's mission is to coordinate with neighbouring TSOs to internalise external loop flows. TSO can then optimally use all interconnected power resources. The coordination between TSOs includes both their externality management schemes and their long-term network developments. The issue of compensation between coordinated parties is not considered here and is still to be tackled by literature.

"Standardisation" and "combination" are the two main ways of coordinating adjacent systems (see [START_REF] Glachant | Un marché européen de l'électricité ou des marchés dans l'Europe? Regards croisés économistes et ingénieur[END_REF]). The coordination by "standardisation" implies that each TSO elects the same implementations for the two previous modules and communicate a minimal set of data on the state of its network (see [START_REF] Cadwalader | Coordinating congestion relief across multiple regions[END_REF] for a coordinated externality management). The coordination by "combination" needs the implementation of standard inter-TSO footbridges to allow the coexistence of different individual schemes.

Standardisation achieves full efficiency while combination is only a second-best. Nevertheless, depending on its cost compared to its benefit, the coordination by combination or no coordination at all may be optimal.

The most efficient type of coordination depends on the topology of both TSOs' networks. The more meshed the networks are, the more efficient the coordination is to deal with border effects (see [START_REF] Costello | Interregional coordination versus RTO mergers: a cost-benefit perspective[END_REF]).

An ideal first-best TSO

The efficient implementation of the modules of this analysis framework constitutes an Ideal first-best TSO (ITSO). An ITSO must send economic signals to the network users to ensure an efficient use of the network. An ITSO efficiently develops the network. And an ITSO must coordinate with its neighbours to internalise the border effects.

To conclude, an ITSO is designed as follow:

Table 1 An ideal first-best TSO

COMPATIBILITY OF TSO'S MODULES

In reality, there is no guaranty that a TSO is benevolent. It may face contradictions between its private agenda and ITSO missions. Transmission governance accounts for the possible gap between real TSOs and the ITSO in such matters. This may generate some compatibility constraints between the implementations TSO's missions.

First, we show that transmission governance mainly relies on Transmission Ownership unbundling and impacts regulation and market design. Lastly, we study three kinds of compatibility constraints between the modules of real TSOs that transmission governance imposes.

Missions of TSO

Ideal first best TSO

Transmission governance

Transmission unbundling from incumbent utilities provides more than a non-discriminatory open access to the network. It is the ground of transmission governance and frames the compatibility constraints of the implementations of TSO's missions.

First, we point out the rationale of unbundling transmission ownership. Second, we see the impact of transmission governance on the regulation of TSO. Third, we see the impact of governmental energy policy, regulation and transmission governance on how power flows externality is considered in market design.

Unbundling transmission ownership

Transmission Ownership unbundling is frequently assumed. However, it is constrained by the possibility of divesting network from incumbents and the wideness of border effects. The divestiture of system operation is widely recognised as a necessary prerequisite in a deregulated process and rather easy to impose: it stands only for few immediate financial stakes although those stakes may prove to be strategic in terms of entry barriers to third party network access. To the contrary, the divestiture of the transmission ownership may be hard to impose in the legal framework. Network ownership in an industrial activity, often held by private companies, to which it provides a riskless regulated revenue is attractive in the context of uncertainty of a power market.

Border effects also influence network unbundling. If transmission ownership and system operation are balkanised and uncoordinated, loop flows create numerous border effects that even an unbundling of both operation and ownership may not be sufficient to deal with. A merger of the divested System Operators (SO) in a third party, an Independent System Operator (ISO) keeps the industrial structure quite unchanged while the horizontal integration internalise border effects. For the rest of this paper, "TOSO" refers to a TSO that owns part or the whole network it operates while "SO" refers to a TSO that owns no network asset and "TSO" is used as a generic term referring without distinction to both.

Incentive regulation

Ownership

unbundling has consequences on the governance and on the incentive regulation of the transmission monopoly.

Regulatory incentives are delicate to be imposed on a SO due to its small financial size.

A self-regulated not-for-profit organisation is an alternative to a for-profit one (see [START_REF] Baker | Governance and regulation of power pools and system operators[END_REF]). Indeed, the participation of transmission owners and network users in such organisation should ensure its neutrality and its de facto regulation if there is no risk of collusion or capture of the organisation by a lobbying group. It is the typical stakeholder participation to the ISO governance in the USA.

On the contrary, the regulator can incentivise a TOSO on its controllable costs to set its monopoly price. The possible financial penalties from the incentive regulation have no severe consequences for the TSO's survival thanks to its tariffs revenues.

To conclude, a SO will be preferably not-for-profit self-regulated because it cannot support an incentive regulation. On the contrary, an incentive regulation is less risky for a TOSO thanks to its tariffs revenues.

Power flows externality and market design

As System Operator, a TSO is also the main architect of the market design as for power flows externality. Then, over transmission governance the consistency of governmental energy policy and political economy may interfere with power flows externality market design.

A TOSO may defend its own financial stakes while designing the market of power flows externality. To the contrary, a SO is theoretically neutral while designing the market of power flows externality thanks to a stakeholder process that is assumed to be balanced. Then, SOs are also less subject to incompatibilities in the construction of a regional market design.

Beside its role of control vis-à-vis the TSO's costs, the regulator may have to take into account tradeoffs due to governmental energy policy ambiguity. For instance, efficient locational signals can penalise wind energy since windfarms are generally far from consumption and so require huge network investments. The regulator may also have to reach an agreement on redistribution of costs and benefits induced by any modification of market rules related to power flows externality.

To conclude, power flows externality market design may be suboptimal depending not only on ownership unbundling but also on inconsistent governmental energy policy and political economy.

Conclusion about transmission governance

The governance of TSOs results in a compromise between its regulation, and market and coordination design. A TOSO can be incentivised but its financial stakes may interfere in market and coordination design while a SO may be easier to coordinate but harder to regulate and incentivise.

Compatibility of modules

Transmission

governance imposes compatibility constraints between the implementations of TSO's missions. We study three kinds of compatibility constraints. First, incentivising easily a TSO is important to ensure an efficient network development. Second, locational signals coordinate the network users with the network accommodation capacity despite network unbundling. Finally, an inter-TSO scheme allows an efficient use of the meshed nature of the transmission network.

Compatibility constraints due to incentive regulation

The TSO faces different incentives in managing and investing depending on the combination of transmission governance and the externality management scheme.

Although the nodal pricing scheme is efficient in inciting the dispatch of the network users and partly their locations, it entices a profit-maximising TSO to underinvest and to oversize the congestion rent (see [START_REF] Joskow | Merchant Transmission Investment[END_REF]). Therefore, a TSO that manages network externality thanks to nodal pricing will require a more demanding regulatory scheme to compensate the counter-incentive effect of the congestion rent.

On the contrary, although a redispatch scheme seems inefficient to deal with short-run externality, it makes the TSO facing directly short-run operation congestion costs. A profit-maximising TSO compares these operation costs with investment costs and so approximates a social welfare maximisation (see 2.2). The regulator can then rather easily check the compatibility between economically efficient investment planning and externality costs.

Whatever the market design, one could compel TSO to calculate the social cost of externality and so to ensure an open access of the regulator to this information. However, one must keep in mind that only a TOSO can be incentivised on the socialised costs. If the TSO is a SO, a nodal pricing appears to be a better option, all the more that it is not-for-profit and so insensitive to congestion rent.

Compatibility constraints due to locational signals

The allocation of network charges can incentivise the location of network users. But, the efficient location of network users may be contradictory with other goals of the governmental energy policy that require huge network investments. As for the externality management scheme, not only does it face compatibility constraints from regulation, but it is also insufficient in emitting long-term locational signals.

Even if nodal prices provide a local value of the network constraints, they do not measure the impact of a new investment on other nodes and are not efficient as long-term locational signals.

Moreover, they do not internalise some externalities, for instance network reliability.

Therefore, a locational network tariff is necessary to deal with the indivisibilities and the externality of the network investments. The zonal allocation method is a pragmatic solution and consists in keeping the non-discriminatory approach of socialisation and in incentivising the connection area of new users.

Public accommodation capacities can make the cost allocation method more auditable to the network users. However, such information can be hard to compute since the accommodation capacities of nodes are interdependent and may vary from a connection request to another. If nodal accommodation capacities are available, they may not be simultaneously feasible.

However zonal tariffs and accomodation capacities may have a limited impact on the location of the network users compared to other constraints, as their primary resources (water, wind, coal, etc…)

Compatibility constraints due to the coordination between TSOs

We saw that transmission governance frames the individual schemes of TSO. As a result, the respective transmission governances frame the coordination between TSOs.

Locational methods are a better choice of standardisation for coordination since they can internalise not only internal but also external loop flows and so border effects. Otherwise, the coordination may require an inter-TSO footbridge if the individual schemes completed by data exchanges are not sufficient.

Therefore, coordination must also be desired by each organisational structure of transmission.

Such a concerted mobilisation is hard to gather (see [START_REF] Glachant | Un marché européen de l'électricité ou des marchés dans l'Europe? Regards croisés économistes et ingénieur[END_REF]). A competent "supra-organisation" (regulator or government) surrounding the parties to be coordinated is necessary at least to incentivise compensation rules associated to the development of coordination, at most to ease the evolution towards a standardised coordination.

STUDY OF PJM AND NGC

NGC and PJM are briefly compared to "an ideal first-best TSO" thanks to our common modular analysis. We focus on the study of compatibility constraints between operational modules.

Comparison of PJM to the ITSO

PJM is often quoted as an example to be followed for the creation of a system operator ruling wide areas.

As for externality management, PJM uses nodal pricing, for congestion management only. Losses must be integrated in its nodal pricing scheme to reach the best practices of externality internalisation of other SOs.

As for the development of the network, PJM must improve its too simplistic criterion that is based on congestion thresholds to evaluate the economic opportunity of its Economic Planned Transmission Facilities. The arbitrage between short-run operation costs and investment costs is made without directly calculating congestion cost but just estimating it ([10]). Moreover, neither losses nor unsupplied energy are taken into account during the decision process. Investment decisions are eventually based on a snapshot, ignoring uncertainty about future flows.

As for the coordination between TSOs, such a wide operator solves an important part of border effects and coordination with neighbours is theoretically fully achievable.

Implementations of PJM's modules are summed up in the following chart: Table 2 Comparison between PJM and an ITSO

Compatibility of the PJM's modules Clarity of regulation

The reform of the power industry in the USA faces up against the dual structure of its regulation with one federal energy regulator, the FERC, and fifty state regulators, the PUCs. The FERC whose jurisdiction is limited to the interconnected wholesale markets leads the deregulation process. The desirability of deregulation differs from state to state. Their jurisdiction surrounds bundled activities and in particular transmission. It makes the deregulation process more difficult for the FERC to implement.

However, even if the FERC cannot impose full transmission unbundling to the power industry, it achieved success in providing non-discriminatory open access to transmission network thanks to unbundling system operation only.

Transmission governance

ISOs control wide areas to internalise wide border effects between the utility areas. Their asset-poor not-for-profit structure imposes a self-regulation. However, an overrepresentation of generators in the governance structure can undermine the costs control of this monopoly.

Considering the numerous border effects between the numerous utility areas (around 400 utilities), the FERC was more concerned about creating operators over wide areas than about divesting transmission ownership that would not have resolved this critical issue. So the ISOs are SOs. Therefore, they cannot support an incentive regulation, all the more that they are generally not-forprofit. As monopolies, ISOs are selfregulated thanks to sophisticated structures of governance to represent fairly each group of stakeholders.

An overrepresentation of the generators questions the fair representation of the market actors in the ISOs ( [START_REF] Boyce | Governance of electricity transmission systems[END_REF]). ISOs may then act under an unclear political pressure from different lobbying groups. In particular, generators prefer congested networks to use local market power.

To conclude, network operators must deal with wide border effects. They can only be implemented as SOs because of the dual regulatory structure. Incentive regulation cannot then be enforced but selfregulation may not ensure enough costs control because of an overrepresentation of the generators.

Compatibility analysis

The governance of PJM dictates the compatibility constraints between the implementations of TSO's missions, as for costs control, the provision of locational signals and the coordination between TSOs.

As for compatibility constraints due to costs control of transmission, self-regulated SOs faced congestion gaming in the late 1990's while using redispatch. In particular, PJM engaged itself in 1998 into implementing nodal pricing. The nodal pricing is the power flows externality management scheme the more appropriated to a SO such as PJM. Its notfor-profit structure makes it indifferent to the counter-incentive effect of the congestion rent. As for the integration of losses in its nodal pricing, it may have been a secondary issue while PJM was focused on extending its area to neighbouring utilities.

Nevertheless As for compatibility constraints due to the provision of locational signals, the "deep cost" do not allow an internalisation of the positive externality of network investments. Accommodation capacities on the PJM system are nevertheless missing for the connection costs to be auditable.

As for compatibility constraints due to the coordination between TSOs, the FERC's Standard Market Design displays a framework that allows a coordination by standardisation between ISOs and similar organisations at least for System Operation.

Comparison of NGC to the ITSO

Despite

its flawed externality management scheme, the operation cost of NGC is under control. The network investments are consistent with the regulation and the need of the wholesale market. Besides, the zonal use of the system tariff has a contrasted impact on the location of the network users. The coordination with its neighbours seems to be a secondary problem because its network topology is little meshed.

Implementations of NGC's modules are summed up in the following chart: Table 3 Comparison between NGC and an ITSO

Compatibility the NGC's modules

Clarity of regulation

The role of the energy regulator OFGEM, and to a lesser extent the European Commission and the DTI in the regulation of NGC and their relations are clear-cut. It has made the full unbundling of transmission network easier to reach.

Despite the principles of subsidiarity and of independence of the regulator vis-à-vis the government, there are few public divergences between these organisations. Great Britain is often referred as a reference of power deregulation in Europe.

Clear regulatory relations allow discretionary decisions about the industrial structure and particularly full transmission unbundling in order to ensure competition and a non-discriminatory open access to transmission network. NGC is a private independent TOSO that operates the power network of England and Wales.

Transmission governance

The NGC's transmission ownership then allows the regulator OFGEM to use incentive schemes.

The ownership of the network by the System Operator allows an efficient development of the network for two reasons. First, the revenue from the network ownership ensures that the financial penalties in the framework of an incentive regulation will not jeopardise the survival of the TSO. Second, an incentivised TOSO arbitrates between on the one hand short-run operation costs and small-scale investments with short payback and on the other hand small-and largerscale investments all the more that there are economies of scale in network investments ([10]).

To conclude, a profit-maximising TOSO can minimise operation costs and reach a satisfactory network costs under the pressure of well-designed financial regulatory incentives.

Compatibility analysis

The governance of NGC dictates the compatibility constraints as for costs control, the provision of locational signals and the coordination between TSOs, between the implementation of operational modules.

As for compatibility constraints due to costs control of transmission, the governance structure of NGC as a TOSO ([8]). However, at the time of (re)designing the English and Welsh power market, the consumers (producers) that are mainly in the South (North) feared that their bill might increase (revenue might decrease) while the network would earn the rent ( [START_REF] Green | Transmission pricing in England and Wales[END_REF]). A zonal tariff provides a degree of cost causality while it reduces the entry barrier in particular for network demanding generators such as windfarms.

As for compatibility constraints due to the coordination between TSOs, it is of little concerns in the case of NGC. Indeed, the NGC's interconnectors create few loop flows. The France-England interconnector is a DC line whose flow is controllable. It is a separate merchant business out of the scope of the OFGEM ([10]). This is an institutional barrier to reach ideally a coupling between France and Great Britain. The overcapacity of the Scottish generators makes the flow on the Scottish interconnector quite predictable. And their high concentration justifies the Scottish interconnector being administrated rather than auctioned.

CONCLUSIVE REMARK ABOUT PJM AND NGC

There is not really a better way to deviate from an "ideal first-best" TSO since each context is peculiar and the job of TSO is mainly determined by the incumbent topology and capacity of the network and its regulation. The NGC control area is a peculiar case of insularity. Therefore, coordination is only a secondary issue to NGC while the network development is its core activity. In the USA, the ISOs such as PJM are regional coordinators and the network development was only a secondary issue. As the coordination is a solved issue in the PJM area, the network development is becoming of importance to avoid a market balkanisation.

CONCLUSION

Our operational and institutional modular analysis framework shows that the institutional context of TSO induces compatibility constraints between the implementations of its missions.

Our empirical analysis concludes in a quite opposite way than some other drastic views (see for instance [START_REF] Ehrenmann | Inefficiencies in European congestion management proposals[END_REF]). The ideal TSO is still the target to be reached (see [START_REF] Ehrenmann | Inefficiencies in European congestion management proposals[END_REF]) thanks to the relevant institutional ground as they may ease the creation of wide market areas. But suboptimal network management schemes may be relatively efficient regarding the institutional context surrounding their implementation. All the more regulation may limit inefficiency in some cases. Besides, the windows of feasibility of such institutional modifications are short and limited (see [START_REF] Glachant | Un marché européen de l'électricité ou des marchés dans l'Europe? Regards croisés économistes et ingénieur[END_REF]). Therefore, even suboptimal solutions must be deemed and studied because they may be the only ones to be institutionally implemented.

Vincent