Pierre Fraigniaud

Amos Korman

Emmanuelle Lebhar

Local MST Computation with Short Advice

Keywords: Minimum spanning tree, distributed algorithm, local computation

We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m, t)-advising scheme for a distributed problem P is a way, for every possible input I of P, to provide an "advice" (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem P can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (⌈log n⌉, 0)advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T ), and it is known that any (0, t)-advising scheme satisfies t ≥ Ω( √ n). Our main result is the construction of an (O(1), O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m, 0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m, 1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log n to constant.

Introduction

In their seminal paper, Naor and Stockmeyer [START_REF] Naor | What can be computed locally?[END_REF] aimed at determining what can be computed locally, that is at determining what problem in distributed networks can be solved with each node exchanging information with only nodes at bounded distance from it. In particular, they proved that randomization does not help for locally checkable problem (LCL) 1 : if there is a local randomized algorithm in O(t) rounds and bounded error probability, then there is a deterministic one in O(t) rounds as well. Despite the limitations induced by the locality constraint, [START_REF] Naor | What can be computed locally?[END_REF] proved that non-trivial LCL problems such as weak-coloring (a basis for a solution to a certain resource allocation problem) can be solved in constant time. This is in contrast with the standard coloring problem for which Linial [START_REF]Locality in distributed graph algorithms[END_REF] showed that, for any fixed c ≥ 1, one cannot c-color properly an n-node ring in less than Ω(log ⋆ n) rounds, i.e., nodes must consider their Ω(log ⋆ n)-neighborhood. More recently, Kuhn et al. [START_REF] Kuhn | What cannot be compute Locally![END_REF] exhibited other problems that cannot be computed within a fixed neighborhood. For instance, minimum vertex cover, and minimum dominating set can basically not be well approximated locally. In time O(k), the approximation factors are at least Ω(n c/k 2 /k), with c > 1/4 and Ω(∆ 1/k /k), respectively, where ∆ is the maximum degree of the graph.

Another framework was recently introduced in [START_REF] Fraigniaud | Oracle size: a new measure of difficulty for communication tasks[END_REF] for investigating tradeoffs between computation time and local knowledge: distributed computing with advice. In this framework, a priori knowledge about the instances of the problem is given to the nodes by an oracle. The oracle O looks at the entire network G and assigns to every node v ∈ V (G) some information, coded as a string of bits O(G, v). The amount of knowledge given to a network G is measured either as the sum (or average) of the lengths of all the strings it assigns to nodes, or as the maximum length of all the strings. Solving a network problem P using oracle O consists in designing an algorithm that is unaware of the network G but solves the problem P for it, as long as every node v of the network G is provided with the string of bits O(G, v). In particular, [START_REF] Fraigniaud | Oracle size: a new measure of difficulty for communication tasks[END_REF] shows that broadcasting in n-node graphs can be performed with O(n) message complexity by simply giving a constant average amount of advice to each node, whereas, to be performed with O(n) message complexity, the wake-up task requires an average of Ω(log n) bits of advice per node. This demonstrates that the framework of advising scheme enables to measure the amount of knowledge required to solve a specific task, and to compare tasks that look very similar at a first glance (in absence of advice, the broadcast and wake-up problems require both Θ(E) messages in E-edge graphs).

An (m, t)-advising scheme for a distributed problem P is a pair (O, A), where O is an oracle, and A is an algorithm using the advices of O for solving P such that the maximum size of the advices is at most m bits, and the problem P can be solved distributively in at most t rounds by A using the advices as inputs. The objective is to establish tradeoffs between the amount of knowledge given to the nodes, and the time required to solve the problem. In this paper, we investigate the local computation of a minimum spanning tree (MST) in an edge-weighted network, in the framework of distributed computing with advice.

Our model is the same as the standard one in [START_REF] Kuhn | What cannot be compute Locally![END_REF][START_REF]Locality in distributed graph algorithms[END_REF], plus a predefined port labeling. We consider networks modeled as n-node edge-weighted connected simple graphs with no self-loops. Nodes of a network G = (V, E) have (non-necessarily distinct) IDs. The deg(u) edges incident to node u ∈ V (G) are locally labeled by deg(u) distinct labels, called port numbers. The port number at u of the incident edge e is denoted by port u (e). Each node u ∈ V (G) knows its ID, and the weight w(e) of each of its deg(u) incident edges e, identified by its port number. As in most previous works aiming at investigating local computation, we assume synchronous distributed computations proceeding in successive rounds in which the local computations times are negligible in front of the communication times, i.e., the complexity of a problem is computed in terms of number of rounds. At each round, every node u acts as follows: (1) it sends through each of its incident edge e = {u, v} a message M e , (2) it receives the message M ′ e sent by the other extremity v of edge e, and (3) it performs local computations based on all data collected since the beginning of the execution of the algorithm. There is no limit on the volume of information that can be transmitted along an edge at each round, i.e., we assume the LOCAL model defined in [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF]. However, all our algorithms send at most O(log n) bits through each edge at each round, and therefore all our upper bounds apply to the CON GEST model [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF] as well.

In the model above, the MST problem requires to compute an upward tree representation of a minimum spanning tree T of the network, i.e. each node u ∈ V (G) of the network G = (V, E) must output the port number of the edge of T leading to its parent, excepted the root r itself that should simply output that it is the root. In addition to its own ID, and the weights of its incident edges, each node u ∈ V (G) is given a bit-string O(G, u) corresponding to the advice given by the oracle O to node u about the network.

In this model, there is a straightforward (⌈log n⌉, 0)-advising scheme (O, A) for MST in which each node is given by O the rank of the edge leading to the root of some MST T . Precisely, for an edge e incident to u ∈ V (G), we define index u (e) = (x u (e), y u (e)) where x u (e) is the rank of the weight w(e) of e among all the weights of the edges incident to u, and y u (e) is the rank of the port number of edge e among all the edges of weight w(e) incident to u. The straightforward (⌈log n⌉, 0)-advising scheme (O, A) selects any MST T , and selects one node r as the root of T . O gives to every node u ∈ V (G), u = r, the bit-string corresponding to the binary representation of the rank r u (e) ∈ {1, . . . , deg(u)} of index u (e), among all the indexes of the edges incident to u, where e is the edge incident to u that leads to the parent of u in T . Then A computes at each node u the port number or the edge having rank r u (e).

On the other hand, it is proved that, in the CON GEST model, (0, t)-advising scheme satisfies t ≥ Ω( √ n) [START_REF] Peleg | A near-tight lower bound on the time complexity of distributed MST construction[END_REF]. In the LOCAL model, of course there is a (0, D + 1)-advising scheme for all graphs of diameter D, and having distinct node IDs2 .

Our results

Our main result is the construction of an (O(1), O(log n))-advising scheme for MST in the CON GEST model. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information.

We also consider the average size of the advices. On one hand, we show that, for any m ≥ 0, any (m, 0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (O(log 2 n), 1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices to constant.

Related works

One can rephrase many recent results of the literature in the framework of advising schemes. For instance, a (⌈log n⌉, 0)-advising scheme, with average advice length O(log log n) bits, is described in [START_REF] Cohen | Labeling schemes for tree representation[END_REF] for computing a spanning tree. It is also easy to extract a (2, 1)-advising scheme for spanning tree (with average advice length 4 3 ) from the proof of the main result in [START_REF] Cohen | Label-Guided Graph Exploration by a Finite Automaton[END_REF]. [START_REF] Fraigniaud | Tree Exploration with an Oracle[END_REF] considers the competitive ratio of the exploration time of a robot unaware of the topology compared to a robot knowing the map of the graph. A (k, α)-advising scheme for exploration uses a robot that is given k bits of advice, and performs exploration in a number of moves at most α times the optimal number of moves. [START_REF] Fraigniaud | Tree Exploration with an Oracle[END_REF] describes a (O(log log D), α)-advising scheme for exploration of diameter-D trees, with α < 2, and prove that, for any ǫ > 0, any (k, 2ǫ)-advising scheme for exploration satisfies k ≥ Ω(log log D).

Regarding the MST problem, the classical algorithm by Gallager, Humblet, and Spira [START_REF] Gallager | A distributed algorithm for minimum-weight spanning trees[END_REF] proceeds in O(n log n) rounds with constant size messages. [START_REF] Chin | An almost linear time and O(n log n + e) messages distributed algorithm for minimum-weight spanning trees[END_REF] improves this result with an algorithm proceeding in O(n log log n) rounds. Yet another improvement was achieved in [START_REF] Gafni | Improvements in the time complexity of two message-optimal election algorithms[END_REF], with an algorithm in O(n log ⋆ n) rounds. [START_REF] Elkin | A Faster Distributed Protocol for Constructing a Minimum Spanning Tree[END_REF] gives an algorithm in O(µ(G) log 3 n + log n • n log ⋆ n/B) rounds in the CON GEST (B) model, where µ(G) is the MST-radius of G. [START_REF] Elkin | An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem[END_REF] considers approximation of MST. It is shown that approximating MST within a factor k takes at least Ω( n kB ) rounds, and

at most O(D + Wmax k-1 • log ⋆ n) rounds,
where D is the diameter and W max is the maximum weight. [START_REF] Peleg | A near-tight lower bound on the time complexity of distributed MST construction[END_REF] presents several lower bounds. In particular, Ω( √ n B ) rounds are required for computing MST in graphs of unweighted diameter O(n δ ), 0 < δ < 1/2, and at least Ω( √ n B log n ) rounds are required for graphs of unweighted diameter O(log n). These results were improved in [START_REF] Lotker | Distributed MST for Constant Diameter Graphs[END_REF] where it is shown that at least Ω(n 1/3 /B) rounds are required for graphs of diameter at most 4, and at least Ω(n 1/4 /B) rounds for graphs of diameter at most 3.

Advising schemes with small average size

In this section, we first prove that the aforementioned straightforward (⌈log n⌉, 0)-advising scheme (O, A) for MST is actually optimal even if one considers not the maximum size of the advices max v∈V (G) |O(G, v)|, but instead the average size of the advices

1 n v∈V (G) |O(G, v)|.
On the other hand, we present an (O(log 2 n), 1)-advising scheme for MST with advices of constant average size.

Lower Bound on the Average Size

Theorem 1 For any n-node graph G, and any m ≥ 0, any (m, 0)-advising scheme for computing an MST of G gives advices of average size Ω(log n). This result holds even if all edge-weights are pairwise distinct.

Proof. Let G n be the network with 2n nodes u 1 , . . . , u n , v 1 , . . . , v n , n ≥ 1, defined as follows. Let K n be the complete graph of n nodes. Let (x 1 , . . . , x n ) be an hamiltonian path of K n . This path is The edge-weights in G n are assigned as follows. We set w({u 1 , v 1 }) = 0. Let ω be any positive integer. For every i,

u 1 u 2 u 3 u n u n-1 v 1 v n u 4 v 2 ...
1 ≤ i ≤ n, let a i = ω 2 -(i + 1)ω + 1 and b i = ω 2 -iω. For all 1 < i ≤ n, w({u i , u i-1 }) and w({v i , v i-1 }) can be any integer in [a i , b i ].
Similarly, for all 1 ≤ i ≤ n -2, and for all j ∈ {i + 2, . . . n}, the weights w({u i , u j }) and w({v i , v j }) can be any integer in [a i , b i ]. Note that these weights are assigned arbitrarily from the ω values in the range a i , . . . , b i . In particular, a node can have incident edges with equal weights. Conversely, if ω ≥ n, then all the incident edges can be assigned different weights.

Clearly, the edge {u 1 , v 1 } has to belong to any spanning tree of G n because it is a cut-edge. In fact, any MST for G n contains all the edges {u i , u i-1 }, and

{v i , v i-1 } for i ∈ {2, . . . n}. Indeed, a k > b i for k ≤ i -1, and therefore w({u i , u i-1 }) < w({u j , u k }), and w({v i , v i-1 }) < w({v j , v k })
for any j ≥ i and any k ≤ i -1 such that (j, k) = (i, i -1). Therefore, a simple induction on i = 2, . . . , n enables to prove that all the edges {u i , u i-1 }, and {v i , v i-1 } belong to any MST for G n . In other words, G n has a unique MST that is the path P = (u n , . . . , u 1 , v 1 , . . . , v n ).

Consider an (m, 0)-advising scheme (O, A), and assume, w.l.o.g., that the root of P chosen by the scheme is in {v 1 , . . . , v n }. Hence A has to return {u i , u i-1 } at node u i . Suppose that the average size of the advices is less than 1 2n n-1 i=2 log(ni) bits. Therefore, there exists i ∈ {2, . . . , n -1} such that |O(G n , u i )| < log(ni). Let w 0 , w 1 , . . . , w n-i-1 be ni integers in [a i , b i ], and let e 0 , e 1 , . . . , e n-i-1 be the ni edges incident to u i with weights in [a i , b i ]. We consider ni possible settings S 1 , . . . , S n-i of the weights for the e j s. For k = 1, . . . , ni, let π k ∈ Σ n-i be such that π k (j) = j + k (mod ni). In S k , we have w(e j ) = w π k (j) for j = 0, . . . , ni + 1. Since u i is given less than log(ni) bits of advice by O, there are two different configurations S k and S k ′ for which A will return the same port number, and thus A will not return {u i , u i-1 } at u i for at least one of these two configurations. Therefore, the average size of the advices is at least

1 2n n-1 i=2 log(n -i) bits, i.e., at least Ω(log |V (G n )|) bits.

Upper Bound on the Average Size

In this section, we present an advising scheme for MST, performing in one round with advices of constant average size. Hence, compared to Theorem 1, this demonstrates that only one round of computation enables to drastically decrease the average advice size. Our scheme is based on Boruvka's algorithm, which provides a decomposition of the MST construction into exponentially growing sets. It is basically a variant of Kruskal's algorithm (cf. [START_REF] Cormen | Introduction to Algorithms[END_REF]). Precisely, our MST construction proceeds in at most ⌈log n⌉ phases, as follows.

MST Construction. Before phase 1, each node is a fragment reduced to a single node. At each phase, fragments are merged to produce larger fragments. Eventually, there remains only one fragment. To perform phase i ≥ 1, one considers only fragment F satisfying |F | < 2 i . These fragments are said active at phase i, and the others are said passive. Every fragment F that is active at phase i selects an incident edge e leading out of F , and of minimum weight. Ties are broken using the port numbers. If ties remain, then they are broken arbitrarilly. The edge e is called the selected edge of F at phase i. The node of F that is incident to e is called the choosing node of F at phase i. All fragments connected together by selected edges at phase i become one new fragment for phase i + 1.

We state the following straightforward lemma for further references.

Lemma 1 After phase i, the size of every fragments is at least 2 i . Thus a fragment F that is active at phase i satisfies 2 i-1 ≤ |F | < 2 i . Hence there are at most n/2 i-1 active fragments at phase i.

Since the graph has no self-loop and no double edge, a node u of a fragment F cannot have more than |F | -1 incident edges whose other extremities are in F . Moreover, since the edges are consumed in order of increasing weights and port numbers, we get the following result: Lemma 2 If e has been selected by fragment F and u ∈ F is the choosing node of e, then index u (e) = (x u (e), y u (e)) satisfies x u (e) + y u (e) ≤ |F |.

In the following, we choose an arbitrary node r of the MST T returned by Boruvska's algorithm to be the root of T . The choice for the root induces an orientation on the edges. We say that a T -edge incident to a node v is up at v if it is the first edge on the shortest path from v to r in T , and down at v otherwise. Figure 2.2 illustrates one phase of Boruvska's algorithm. In this figure, there are three fragments F 1 , F 2 , F 3 . Dashed lines represents edges that are not selected, and the black nodes are the choosing nodes. Labels up and down give the orientation of the selected edges from the point of view of their choosing node. Note that an edge can be up for one of its extremities, and down for the other.

While from Theorem 1 it is not possible to improve the naive advising scheme when no step of computation is allowed, interestingly enough the next theorem shows that a single round of computation enables to lower the average advice length down to a constant.

Theorem 2 For any n-node graph G, there exists an (O(log 2 n), 1)-advising scheme for computing an MST of G, that gives advices of average size c = ⌈log n⌉ i=1 i+1

2 i-2 = O(1).
Proof. The scheme picks an arbitrary node of the MST returned by Boruvska's algorithm to be the root. This induces a direction (up or down) on every selected edge from the point of view of the choosing node. The construction of the advices follows from the phases of Boruvska's algorithm. For each phase 1 ≤ i ≤ ⌈log n⌉, each choosing node u at phase i stores two items of advice:

up down down F 1 F 2 F 3
Figure 2: One phase of Boruvska's algorithm

• index u (e)
where e is the selected edge at phase i corresponding to u; and

• a boolean b stating whether e is up.

The size of this advice is at most i + 1 bits. Indeed, active fragments at phase i have size less than 2 i , and thus from Lemma 2, index u (e) < 2 i . Since there is exactly one choosing node per fragment, and at most n/2 i-1 active fragments at phase i (cf. Lemma 1), this consumes a total of at most (i + 1) • n/2 i-1 bits of advice per phase. The advices possibly received at different phases are concatenated. Every node that was choosing at some phase stores a bit-map indicating the separation between the advices corresponding to different phases. This doubles the size of the advices. Thus, the scheme uses at most 2

⌈log n⌉ i=1 (i + 1) • n/2 i-1 = O(n) bits in total
, that is a constant number of bits per node on average. Given these advices, the rooted MST can be computed as follows: every choosing node u sends a message on each incident edge e for which the corresponding index belongs to its advice. If the bit b associated to the index of e is 1, then u directly learns the index of the port number of its parent, and if b = 0 then u informs the other extremity of e that it is its parent. This algorithm thus runs in at most one round.

Since a node can be a choosing node in all ⌈log n⌉ phases, the maximum length of an advice can be up to ⌈log n⌉ i=1 (i + 1) = O(log 2 n) bits.

An (O(1), O(log n))-Advising Scheme for MST

This section presents our main result, that is, by assigning just a constant amount of advices to each node, it is possible to compute an M ST in any n-node graph in at most O(log n) rounds. Precisely, we prove the following.

Theorem 3 There exists a (m, t)-advising scheme to compute an MST in any n-node graph, with m = 12, and t ≤ 9 ⌈log n⌉.

Proof. Let G = (V, E) be an n-node graph, and let T be the MST of G returned by the variant of Boruvska's algorithm described in Section 2.2, simply called Boruvska's algorithm in the following.

The scheme picks an arbitrary node r to be the root of T . The setting of the advices is done by induction, in ⌈log log n⌉ + 1 phases of Boruvska's algorithm. For the purpose of the scheme, we define the level of a fragment, for each phase, as a value in {0, 1}, as follows. Before any given phase i ≥ 1, each fragment F induces a subtree T F of T . These subtrees are connected by edges of T between fragments. Contracting each subtree T F into a singe node x F , and connecting two nodes x F and x F ′ by an edge if and only if there is an edge of T between the two fragments F and F ′ , results in a "tree of fragments" T i . The node x F corresponding to the fragment F which contains the root r of T becomes the root of T i , and F is given level 0. More generally, a fragment F at phase i is given level 0 if x F occupies an even level in the rooted tree T i , and level 1 if x F occupies an odd level.

The construction of the advices at each node follows the phases of Boruvska's algorithm up to phase ⌈log log n⌉ + 1. For any given phase i, 1 ≤ i ≤ ⌈log log n⌉, our scheme encodes three items of advice inside each active fragment F of phase i: the choosing node of F , the orientation (up or down) of the edge selected by F , and the level of F at phase i. At phase ⌈log log n⌉ + 1, the scheme encodes inside each fragment F the index of the edge of T leading from x F to its parent in T i . We will show how to distribute these bits of advice inside the fragments so that no node has to store more than 12 bits, and so that these bits can be easily extracted by the choosing node of each fragment at each phase.

For every phase i of Boruvska's algorithm, 1 ≤ i ≤ ⌈log log n⌉, and for every active fragment F at phase i, we construct a bit-string A(F ) as follows. Let v 1 , . . . v ℓ be the BFS ordering of the ℓ vertices of F , 2 i-1 ≤ ℓ < 2 i , in the subtree T F , starting from the root r F of T F , i.e. the node of F that is the closest in T to the root r of the tree T . Precisely, the BFS is guided by the indexes of the edges in T F according to the rule: lower index first. Let v j be the choosing node of F , 1 ≤ j ≤ ℓ. Let bin(j) be the binary encoding of j on i bits, let b up be the boolean indicating whether the edge selected by v j in F is up or down, and let b level be a boolean indicating whether the level of F is odd or even. We define A(F ) = b up |b level |bin(j) where "|" denote the concatenation of strings. Hence A(F ) ∈ {0, 1} i+2 . The advice given to the fragment F at phase i is A(F ).

More precisely, the advising scheme assigns bits of A(F ) to nodes of F as follows. Each of the ℓ nodes v 1 , . . . v ℓ of F is given at most c bits of A(F ), where c = 11. The oracle assigns a c-bit string advice(u) to each node u of G as follows. In order to bound the number of bits per node, we use a variable used(u, i) that indicates the number of bits that node u had to store in its advice(u) until phase i (included). We set used(u, 0) = 0 for every u ∈ V (G), and assign the bits of A(F ) as follows:

While there remains k > 0 bits of A(F ) unassigned do Let j be the minimum index in {1, . . . , ℓ} such that cused(v j , i -1) > 0; Concatenate the min{k, cused(v j , i -1)} next unassigned bits of A(F ) to advice(v j ); Update the value of used(v j , i) according to the number of bits added to advice(v j ). End

The following claim guarantees that each string A(F ) can actually be assigned to F during this process. In other words, we prove that it is possible to pack all strings A(F ) for all phases i, 1 ≤ i ≤ ⌈log log n⌉, using at most c bits at each node. Recall that A(F ) ∈ {0, 1} i+2 . Claim 1 For any i, 1 ≤ i ≤ ⌈log log n⌉, for any active fragment F at phase i, we have c

• |F | - v∈F used(v, i -1) ≥ i + 2.
To establish the claim, we note first that the result is clear for i = 1, because |F | = 1, used(v, 0) = 0, and indeed, c ≥ 3. Consider an active fragment F at phase i > 1. F is composed of at most |F |/2 j-1 fragments of phase j for any 1 ≤ j ≤ i -1. By construction, an active fragment F ′ of phase j satisfies |F ′ | < 2 j , and thus consumes at most j + 2 bits. Therefore, the total number of bits that have been consumed in F until phase i -1 is the sum of the j + 2 bits consumed by the active fragments F ′ at phase j, for all F ′ ⊆ F and j < i. Thus:

v∈F used(v, i -1) ≤ i-1 j=1 |F | 2 j-1 • (j + 2) ≤ |F | ∞ j=1 j + 2 2 j-1 = 8|F |. Therefore, c • |F | - v∈F used(v, i -1) ≥ 3|F | ≥ 3 • 2 i-1 ≥ i + 2
because i ≥ 1 and c ≥ 3 + ∞ j=1 (j + 2)/2 j-1 . This complete the proof of Claim 1. At phase ⌈log log n⌉ + 1 of the advices construction, we consider all fragments, not only the active ones. The bit string A(F ) of fragment F consists of the binary representation of the index of the edge of T leading from the node r F to its parent in T , where we recall that r F is the node of F that is the closest in T to the root r of the tree T . Since this index is at most n -1, A(F ) is a string of at most ⌈log n⌉ bits. Since F is a fragment of phase ⌈log log n⌉ + 1, we get |F | ≥ 2 ⌈log log n⌉ ≥ ⌈log n⌉ and therefore A(F ) can be distributed in F , one bit per node. Precisely, we can distribute the bits of A(F ) using again the BFS ordering v 1 , . . . v ℓ of the vertices in F : v i stores the ith bit of A(F ).

To sum up, the oracle O assigns the bit-string O(G, v) = advice(v)|b(v) to node v where advice(v) are advices given in phases 1 to ⌈log log n⌉, and b(v) is the 1-bit advice given at phase ⌈log log n⌉ + 1. Since Claim 1 guarantees that c bits per node suffices to construct the advices up to phase ⌈log log n⌉ and one bit per node is enough to store the advices of phase ⌈log log n⌉ + 1, we conclude that all advices are of length at most c + 1 at the end of the setting of the advices. Since m = c + 1, our scheme does use advices of maximum size m.

The decoding of the advices follows Boruvska's algorithm up to phase ⌈log log n⌉ + 1 for reconstructing the MST T returned by the algorithm. We will insure that, during all phases i = 1, . . . , ⌈log log n⌉ of the decoding process, every node u is permanently aware of the number of bits of advice that has already been consumed. This can be done using a pointer cons(u, i) that specifies how many bits of advice(u) have been decoded until phase i (included).

Initially, cons(u, 0) = 0 for all nodes u. At phase i, every node u sends to the root r F of its fragment F all its unconsumed bits, i.e. those from cons(u, i -1) + 1 to c. In return, u will receive from r F the largest BFS index k such that v k stores some bits of A(F ). Moreover, r F sends the number of bits of advice(v k ) it has consumed. These two informations are stored in a pair of integers denoted by end(F ). Every node u of F receiving end(F ) is able to update its variable cons(u, i).

The decoding process A is precisely described below.

Assume by induction that the claim holds for phases up to phase i -1 ≥ 1, and let us prove that it holds for phase i. At phase i, fragments of phase i are merged into larger fragments. Let F be an active fragment at phase i. By induction, every node u = r F of F knows its parent in T F . Therefore, step (1) of A can be executed. From Claim 2, the edge e selected by v j at step ( 5) is the edge selected by Boruvska's algorithm for fragment F . If b up is true, i.e., e is up, then v j is actually the root r F of F , and e is the edge leading to its parent in the new fragment (cf. Step ( 6)). If b up is false, i.e., e is down, then, by Step (6), v j informs the other extremity of e, say w j , that e is the edge leading to its parent in the new fragment. Node w j is actually the root r F ′ of a fragment F ′ one level below F in T i . Receiving a message from v j , node w j learns its parent in the new fragment. A root of a fragment that did not acquire a parent at phase i remains root, possibly of a larger fragment resulting from merges at phase i. This proves the claim.

From the previous claim, algorithm A computes the MST T . Indeed, by this claim we get that after phase ⌈log log n⌉, every node but the root of its fragment knows its parent. Steps ( 8) and ( 9) of Algorithm A enables each of these roots to learn its parent.

We complete the proof by showing that algorithm A runs in at most 9⌈log n⌉ rounds. For every phase i, 1 ≤ i ≤ ⌈log log n⌉, the decoding process runs in a time corresponding to one convergecast and one broadcast in every tree T F , where F is an active fragment. Therefore, phase i runs in at most twice the maximum size of an active fragment, hence, from Claim 1, in at most 2 i+1 rounds. The last phase of A, i.e., the one corresponding to phase ⌈log log n⌉ + 1 of Boruvska's algorithm, runs in the time required to collect ⌈log n⌉ bits from ⌈log n⌉ different nodes in every tree T F for each fragment F (not only the active ones). This takes at most ⌈log n⌉ rounds. Thus in total the decoding process runs in at most ⌈log n⌉ + ⌈log log n⌉ i=1 2 i+1 ≤ ⌈log n⌉ + 4(2 ⌈log log n⌉ -1) ≤ 9⌈log n⌉.

This completes the proof of Theorem 3.

Conclusion

Our result suggests a tradeoff between the computation time and the amount of advice for constructing a MST distributively. In particular we show that computing a MST in time 0 requires an average of Ω(log n) bits of advice whereas computing a MST in time 1 can be achieved by an algorithm using an average of O(1) bits of advice. As far as the maximum size of the advices is concerned, we have designed an (O(1), O(log n))-advising scheme for MST. It would be interesting to establish whether the tradeoff between computation and knowledge does exist or not for the maximum size of the advices. In particular, it would be of interest to prove or disprove the existence of an (O(1), O(1))-advising scheme for MST.

Figure 1 :

 1 Figure 1: The graph G n in the proof of Theorem 1.

LCL problems are problems on graphs of bounded degree whose solutions can be checked by each node via investigations within a fixed radius around it.

The node IDs are used to break symmetry; In the anonymous ring with all edge-weights the same, there is no way to break symmetry.

This work was partially done while Amos Korman was visiting LRI at University Paris Sud, supported by the COST Action 295 "DYNAMO".

Decoding process A Input: The distributed network G, with each node v provided with O(G, v) = advice(v)|b(v); Output: Each node v computes the port number of the edge leading to its parent in the MST T .

Begin

For i = 1 to ⌈log log n⌉ do /* The objective is to determine each node's parent inside active fragments after phase i */ For all active fragments F at phase i do (in parallel) [START_REF] Awerbuch | Optimal distributed algorithms for minimum weight spanning tre, counting, leader election and related problems[END_REF] Every node u ∈ F , u = r F , sends all the bits of advice(u) between position cons(u, i -1) + 1 and position c, to its parent in T F ; [START_REF] Afek | Local detection for global self stabilization[END_REF] Messages are forwarded up to the root r F of T F in BFS order; /* At that point, nodes of F know their children in

r F collects and concatenates the several parts of the i + 2 bits of A(F ), and r F broadcast (end(F ), A(F )), where

Each node u updates cons(u, i) according to end(F ); [START_REF] Chin | An almost linear time and O(n log n + e) messages distributed algorithm for minimum-weight spanning trees[END_REF] The choosing node v j of F selects its incident edge e of minimum weight among all its incident edges having its other extremity at level b level . If b up is true [START_REF] Cormen | Introduction to Algorithms[END_REF] then v j is now aware of the port number of e, leading to its parent; [START_REF] Elkin | A Faster Distributed Protocol for Constructing a Minimum Spanning Tree[END_REF] else v j sends a message across e to inform the other extremity of e that v j is its parent. Endfor Endfor i := ⌈log log n⌉ + 1; Do (in parallel) [START_REF] Elkin | An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem[END_REF] The root r F of each fragment F at phase i collects the bits of A(F ) in BFS order in T F ; (9) A(F ) = index r F (e) allows r F to compute the port number of edge e leading to its parent in T . End Before proving that Algorithm A is correct, we first prove the following.

Claim 2

The edge e selected by the node v j of F in Algorithm A is the edge selected by Boruvska's algorithm for the fragment F .

To establish the claim, we first note that, from the encoding of the advices, node v j is the choosing node of fragment F in Boruvska's algorithm. Its incident edge of minimum weight going out of F is the edge selected by Boruvska's algorithm. By definition of the levels, the selected edge has its extremity in a fragment at level b level . Therefore, selecting the edge incident to v j of minimum weight among all incident edge leading to a fragment at level b level enables to discard edges going inside F while preventing from missing the selected edge.

The following claim proves the correctness of the decoding algorithm A.

Claim 3 After phase i, 1 ≤ i ≤ ⌈log log n⌉, for every fragment F resulting from phase i, each node u = r F in F knows the port number of its incident edge leading to its parent in T F , and the root r F of T F knows that it is the root.

The proof is by induction on i. At phase 1 of the decoding process, every fragment F is active, and reduced to the unique node r F , and every node knows that it is the root of its fragment.


J Robic

B Perret

A Nkengne

M Couprie

H Talbot

CLASSIFICATION OF THE DERMAL-EPIDERMAL JUNCTION USING IN-VIVO CONFOCAL MICROSCOPY

Keywords: Conditional Random Fields, Reflectance confocal microscopy, image segmentation, skin modeling

Reflectance confocal microscopy (RCM) is a powerful tool to visualize the skin layers at cellular resolution. The dermalepidermal junction (DEJ) is a thin complex 3D structure. It appears as a low-contrasted structure in confocal en-face sections, which is difficult to recognize visually, leading to uncertainty in the classification. In this article, we propose an automated method for segmenting the DEJ with reduced uncertainty. The proposed approach relies on a 3D Conditional Random Field to model the skin biological properties and impose regularization constraints. We improve the restitution of the epidermal and dermal labels while reducing the thickness of the uncertainty area in a coherent biological way from 16.9 µm (ground-truth) to 10.3 µm.

INTRODUCTION

The characterization of skin conditions is a major challenge for skin aging understanding. Skin aging is defined by a set of cumulative alterations of its various components over the years. The two major layers of the skin, the epidermis and the dermis, are separated by the dermal-epidermal junction (DEJ), which is also affected by skin aging.

The DEJ is a complex, wave-like, 3D structure. Its peaks and troughs, called dermal papillae, are due to projections of the dermis into the epidermis. With skin aging, the DEJ's appearance flattens, which could have important consequences such as lower epidermal adhesion.

Reflectance confocal microscopy (RCM) is a powerful tool for non-invasively assessing the skin architecture and cytology. RCM images provide a representation of the skin at the cellular level, with melanin and keratin working as natural contrast agents [START_REF] Calzavara-Pinton | Reflectance confocal microscopy for in vivo skin imaging[END_REF]. Our data consists of depth-oriented (enface), in-vivo, confocal sections of the skin from the surface to 200 µm. Several approaches to automatize confocal image analysis have been proposed focusing on quantifiying the epidermal state [START_REF] Robic | Automated quantification of the epidermal aging process using in-vivo confocal microscopy[END_REF], performing computer-aided diagnostic of skin lesions [START_REF] Kose | A machine learning method for identifying morphological patterns in reflectance confocal microscopy mosaics of melanocytic skin lesions invivo[END_REF] and identifying the layers of human skin. In fair skin, the DEJ detection is a difficult task since it appears Epidermis Dermis Uncertain Dermis Fig. 1. Expert segmentation in 3 labels : Epidermis, Uncertain and Dermis. The epidermis exhibits a well defined honeycomb pattern, the dermis is textured by the collagen fiber representation. One can notice the low-contrasted appearance of the uncertain area.

as an amorphous and low-contrasted structure. Its segmentation could further improve skin aging quantification.

In the skin, the DEJ architecture is a thin layer of cells but state-of-art methods define it as a thick transition zone due to the difficulty in precisely locating it by visual inspection (Fig. 1). Somoza et al. [START_REF] Somoza | Automatic localization of skin layers in reflectance confocal microscopy[END_REF] used an unsupervised clustering method to classify whole en-face image as a single distinct layer, resulting in a good correlation between human classification and automated assessment. Kurugol et al. [START_REF] Kurugol | Automated delineation of dermalepidermal junction in reflectance confocal microscopy image stacks of human skin[END_REF] developed a hierarchical method on small tiles to segment the DEJ as a transition zone from the epidermis to the dermis. In [START_REF] Hames | Automated segmentation of skin strata in reflectance confocal microscopy depth stacks[END_REF][START_REF] Hames | Anatomical skin segmentation in reflectance confocal microscopy with weak labels[END_REF], Hames et al. proposed a supervised classification method based on a one-layer per depth strategy for the labeling of their training set. They have extended their method to perform pixel-wise classification, allowing them to distinguish several skin strata in one image. Their algorithm uses a 1D linear chain Conditional Random Field and structured Support Vector Machine to model the skin structure.

In this paper, we provide a method to automatically segment the dermo-epidermal junction in 3 classes : epidermis (ED), uncertain area (U), and dermis (D) using in vivo reflectance confocal microscopy on fair skin. Our proposed ap-proach consists of a 3D Conditional Random Field, which allows us to provide a spatial regularization on label distribution and to model skin biological properties. The CRF model predicts a pixel label according to 1) its probabilities to belong to one of the skin layers, and to 2) the labels of its neighbors. The probability of a pixel to belong to one of the three classes is estimated by a Random Forest classifier trained on relevant features. The relations between pixel neighbors mimic the skin layers behavior in 3D by imposing the transition order between en-face sections. Such a model is represented in Fig. 2. Our main result is a DEJ segmentation which respects the high-confidence expert label while reducing the thickness of the uncertain area.

DATABASE

Our database consists of 23 annotated stacks of confocal images acquired from fifteen healthy volunteers with fair skin. Volunteers were assigned to two groups: a 7-persons group aged from 18 to 25 and another 8-persons group aged from 55 to 65. Image acquisition was carried out on the cheek to further assess chronological aging. No cosmetic products nor skin treatment were allowed on the day of the acquisitions. Appropriate consent was obtained from all subjects before imaging. RCM images are acquired using a near-infrared reflectance confocal laser scanning microscope (Vivascope 1500; Lucid Inc, Rochester, NY, USA) [START_REF] Rajadhyaksha | In vivo confocal scanning laser microscopy of human skin: melanin provides strong contrast[END_REF]. Each image corresponds to a horizontal section with a 500 × 500 µm field of view and a resolution of 1000 × 1000 pixels. On each imaged site, stacks are acquired from the skin surface to the reticular dermis with a step of 5 µm. Visual labeling of the DEJ is not easy to perform even for experts, therefore they were asked to delineate the stacks in the 3 zones described in Sec. 1 (see Fig. 1).

CONDITIONAL RANDOM FIELDS

An image y consists of M pixels i ∈ S = 1, M with observed data y i , i.e, y = (y 1 , y 2 , ..., y M ) organized in layers (en-face images) forming a 3D structure. We want to assign a discrete label x i to a each pixel i from a given set of classes C = {Epidermis, Uncertain, Dermis}. The classification problem can be formulated as finding the configuration x that maximizes p(x | y), the posterior probability of the labels given the observations.

A CRF is a model of p(x | y)with an associated graph G = (V, E) where V is the set of vertices representing the image pixels and E the set of edges modeling the interaction between neighbors [START_REF] Kumar | Discriminative random fields[END_REF]. Here, E is the usual 3D 6-connectivity. The CRF model is represented in Fig. 2.

We use a model with pairwise interactions defined by : where ϕ i (x i , y) is the node potential linking the observations to the class label at pixel i and ψ ij (x i , x j , y) the interaction potentials modeling the dependencies between the labels of two neighboring pixels i and j.

p(x | y) ∝ i∈S ϕ i (x i , y) × i,j∈E ψ ij (x i , x j , y), (1)

Node potential

The node potential is defined as the probability of a label x i to take a value c given the observed data y by :

ϕ i (x i , y) = p(x i = c | f i (y)) (2)
with f i (y) a feature vector computed at pixel i from the observed data.

In our case, each node potential is associated with the predicted class probability vector produced by a Random Forest (RF) classifier. We apply the following classical features from the literature [START_REF] Kurugol | Automated delineation of dermalepidermal junction in reflectance confocal microscopy image stacks of human skin[END_REF][START_REF] Hames | Anatomical skin segmentation in reflectance confocal microscopy with weak labels[END_REF] : first and second order statistics, gray level co-occurrence matrix contrast, energy and variance, Gabor filter output and Laplacian variance.

We propose new features to estimate the distance of the current pixel to the DEJ. The DEJ is an amorphous structure compared to the epidermis, which appears as a honeycomb pattern, and the dermis, which contains collagen fibers. Thus, we expect low values of Laplacian variance in en-face sections around the DEJ location. For a pixel i at a given en-face section p, we calculate the feature vector for every en-face section at its location. We define D DEJ as the distance to the closest minimum. The Laplacian variance of the closest minima is also added to the set of features. An example is presented in Fig. 3.

Interaction potential

The interaction potential describes how likely x i is to take the value c given the label c of one of its neighboring pixel j:

ψ ij (x i , x j , y) = p(x i = c | x j = c ) (3)
Fig. 3. Laplacian variance and distance to the closest minimum.

Prior information on skin structure is essential to determine efficiently the interaction potentials in our CRF model. We know that several skin layers can co-exist in a single enface section. However, the skin layers follow a specific order from the surface to inner layers : ED → DEJ (contained in the uncertain area) → D. We define an incoherent transition as a transition not following such a specific order.

In an en-face section, edges are modeled symmetrically i.e ψ ij = ψ ji (dashed arrows in Fig. 2). Between en-face sections, only coherent transitions are allowed, the edge potentials thus depend of their direction, i.e ψ ij = ψ ji (plain arrows in Fig 2).

The interaction potentials are modeled by a 3×3 matrix representing the transition probabilities between classes. We estimate such transition probabilities from the frequency of co-occurrence of classes (c, c ) between neighboring pixels i and j in the ground-truth images. Co-occurrence frequencies are learned for each depth of en-face sections.

For the 3D case, constraints are added to the transition matrix according to the edge direction. Between two pixels i and j belonging to adjacent en-face sections, if i is above j, ψ ij is equal to H(label i , label j ), the transition matrix in

RESULTS & DISCUSSION

Our goal is to produce a precise information about the DEJ shape, i.e. to simultaneously provide an accurate restitution of the epidermal and dermal labels while reducing the uncertain area.

We want to evaluate our set of features and the regularization strategy. We consider three cases: 1) RF lit in which we train the RF classifier on the classical set of features from the literature, 2) RF prop in which we train the RF classifier on our proposed set of features, and 3) CRF3D prop in which we train the RF classifier on our proposed set of features followed by the CRF modelisation.

To evaluate our proposed set of features, we compare the mean accuracy of RF lit and RF prop . Then, to validate our 3D model, we compare the sensitivity for ED and D, to assess the accurate restitution of those layers, and the specificity for U that penalizes the classification of the epidermal or dermal layers as uncertain area.

Each labeling is evaluated using a 10-fold cross-validation. The optimal labels for Eq. ( 1) were computed with a LBP algorithm using DGM Lib [START_REF] Kosov | Direct graphical models C++ library[END_REF].

The mean accuracies of the RF classifications are presented in Table 2. Using features from the literature [START_REF] Kurugol | Automated delineation of dermalepidermal junction in reflectance confocal microscopy image stacks of human skin[END_REF][START_REF] Hames | Anatomical skin segmentation in reflectance confocal microscopy with weak labels[END_REF], we achieve a recall score of 90% on the high confidence labels, epidermis and dermis, and 57% on the uncertain area.

Our proposed set of features allows us to increase the accuracy on the uncertain area classification to 66%. These results suggest that our set of features is relevant to identify the three skin labels according to the experts' visual inspection. However, the result of RF prop contains 7.1% of incoherent transitions motivating the introduction of spatial constraints with CRF3D prop . 3. Sensitivity and specificity of the three labeling in the unregularized vs. regularized cases.

ED

Our regularization promotes spatial consistency and forbids incoherent layer transitions. The results of the regularized CRF model, presented in Table 3, show that the epidermal and dermal sensitivity are increased. The misclassification scores of high confidence labels improve with the 3D CRF regularization from 9% to 4% for the epidermis and 3% to 1% for the dermis.

The specificity of the uncertain detection is enhanced suggesting a coherent expansion, in a biologically-coherent way, of the high-confidence labels into the uncertain area.

We also compute the average thickness of our uncertain area defined as the average distance between its two borders for every pixel. In the manual annotation, the uncertain area thickness is measured as 16.4 µm. We estimate the thickness of this area as 16.9 µm in the RF model. With our CRF 3D model, the uncertain region thickness is reduced to 10.

CONCLUSION

In this article, we have proposed an improved set of features and a 3D Conditional Random Field regularization for the modeling of skin structures. We have shown that the use of a 3D CRF has a positive impact in terms of improved sensitivity and specificity for the Epidermis and Dermis labeling. We have also shown that the thickness of the uncertain region is reduced significantly. With our method, the DEJ segmentation is nearly always (more than 98% specificity) included within the ground-truth. It allows us to get closer to the true shape of the dermal epidermal junction. Our next aim will be to develop measures for the shape of the DEJ to quantify its changes within skin aging.

Fig. 2 .

 2 Fig.2. 3D CRF modelisation. The sets of nodes in gray and in white belong to two different en-face sections. The edge potentials of each en-face sections ψ jk (Eq. 3) are learned for each depth. Edge potentials between en-face sections ψ ij (Eq.3) impose biological transition constraints.

  3 µm. 3D visualizations of the DEJ segmentations, obtained with CRF3D prop , are presented in Fig. 4. (a) Young epidermis (b) Aged epidermis

Fig. 4 .

 4 Fig. 4. Visual appearance of the lower border of the epidermal layer. Notice that the aged epidermis appears flatter than the young epidermis, as expected. Colors encode the depth.

Table 1 ,

 1 and to H(2 -label i , 2 -label j ) otherwise.

	label j	Epidermis	Uncertain	Dermis
	label i	(label 0)	(label 1)	(label 2)
	Epidermis (label 0)	0.58	0.38	0.04
	Uncertain (label 1)	0	0.91	0.08
	Dermis (label 2)	0	0	1

Table 1 .

 1 Transition matrix H(label i , label j ) with i above j where values are the learned probabilities of transition between depth 80 and 85 µm. The null values ensure that incoherent transitions are impossible.

Table 2 .

 2 Results for the unregularized experiments. Mean accuracy of the RF classifications of the three labels.

				U	D
		RF lit	0.89 0.57 0.97
		RF prop 0.90 0.66 0.97
		Sensitivity		Specificity
		ED	D	ED	U	D
	RF prop	0.90 0.97	0.99 0.96 0.98
	CRF3D prop 0.96 0.98	0.99 0.98 0.98
	Table