Eric Ngo

Federico Panciera

Jean-Christophe Harmand

Weixi Wang

Martin Foldyna

Pere Roca

I Cabarrocas

Laurent Travers

Ileana Florea

Jean-Luc Maurice

Molecular Beam Epitaxy of Germanium in the Atomic-Resolution Transmission Electron Microscope

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

Molecular Beam Epitaxy of Germanium in the Atomic-Resolution Transmission Electron Microscope.

Éric Ngo 1 , Federico Panciera 2 , Jean-Christophe Harmand 2 , Weixi Wang 1 , Martin Foldyna 1 , Pere Roca i Cabarrocas 1 , Laurent Travers 2 , Ileana Florea 1 and Jean-Luc Maurice 1 .

1. LPICM, CNRS, École polytechnique, 91128 Palaiseau, France, 2. C2N, CNRS, Université Paris-Sud-11, Université Paris-Saclay, 91120 Palaiseau, France.

Molecular beam epitaxy (MBE) is an atomically precise method for making monocrystalline thin films or nano-objects. Aberration-corrected transmission electron microscopy allows one to observe crystalline solids at the atomic scale. Combining the two techniques has been an old dream among materials scientists as it allows one to watch the nanostructures growing atom by atom. However, and despite the ripeness of those two methods, this dream has only become true recently [START_REF] Harmand | Nanowire week[END_REF][START_REF] Harmand | [END_REF] with the NanoMAX transmission electron microscope (TEM) used in the present work; a modified Thermo Fisher Titan environmental TEM that is fitted with molecular beam effusion sources. In the present communication, the potential of this combination is illustrated by the observation of step-by-step growth at the surface of germanium nanowires (NWs) as a function of temperature, notably at low temperatures, where in situ chemical vapour deposition (CVD, see e.g. [START_REF] Kodambaka | [END_REF]) would probably not have worked.

The growth proceeds through the vapour-liquid-solid (VLS) mechanism [4], using Au as catalyst. The heating sample holder is a modified Protochips Fusion holder. Firstly, upon increasing the Ge content of Au nanoparticles, we observe at 400°C the solid to liquid transition associated with eutectic formation. Measuring the increase of droplet size as a function of time (Fig. 1), we deduce (i) the Ge flux (~5 at. nm -2 s -1 ) and (ii), the Ge content when particles become fully liquid. We find that this happens above ~27 Ge at. %, which is consistent with the bulk phase diagram where, at 400°C, the liquidus curve is met at ~26.2% [5].

With MBE, the NW growth may be essentially axial or radial depending on whether the surface diffusion of Ge adatoms is respectively high or low, feeding the growing crystal respectively through the catalyst or through the walls directly. Decreasing deposition temperature should then promote sidewall growth by decreasing surface diffusion. Going from 450°C to 200°C, we observe indeed the development of sidewalls: at medium temperature (~350°C), NWs acquire a pyramidal shape (Fig. 2a). Quite remarkably, it allows us to observe standard epitaxy viewed in cross-section on the NW walls (Fig. 2b).

A good crystalline stacking is ensured on such a side-wall when an atom finds its equilibrium position before it is stuck in place by the incoming flux. Here, when lowering the deposition temperature at constant flux, stacking faults occur at 200°C. Upon further decrease of the temperature, the surface mobility becomes so low that no crystalline stacking is allowed: at room temperature, the deposited material is amorphous (Fig. 2b).

The presentation will show the movies from which the figures have been extracted. The present study is part of a project, the aim of which is to understand how, in certain conditions of growth, the diamond stacking of atoms in Ge and Si NWs may adopt a hexagonal polytype [6] that would have, in turn, specific and interesting opto-electronic properties [7] [8].

Figure 1 .

 1 Figure 1. TEM images of an AuGe particle during bombardment by Ge atoms at 400°C. The material becomes liquid as the Ge concentration reaches the eutectic one. The size measurement allows one to infer the number of Ge atoms present in the droplet and deduce the Ge flux.

Figure 2 .

 2 Figure 2. Advancing atomic steps on {111} sidewalls. (a) Three successive frames of a typical pyramidal Ge NW, viewed about 10° off the [110] zone axis at 350°C. See the movement of the individual atomic step on the left {111} wall. The time between two frames is 0.25s. (b) Effect of temperature: {111} sidewall similar to that of (a), viewed in the [110] zone axis, and pictured at the three temperatures indicated. Note surface smoothing and introduction of crystalline defects at 200°C, and of amorphous structure at 20°C. Scale bar 5 nm.


Marin Bougeret

Klaus Jansen

Michael Poss
email: michael.poss@lirmm.frkj

Lars Rohwedder

Approximation results for makespan minimization with budgeted uncertainty

Keywords: Makespan minimization, robust optimization, approximation algorithms, EP-TAS, parallel machines, unrelated machines

We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to Bertsimas et al.

[3], once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs' processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of 2 -for the case of unrelated machines.

Introduction

Classical optimization models suppose perfect information over all parameters. This can lead to optimal solutions having poor performance when the actual parameters deviate, even by a small amount, from the predictions used in the optimization model. Different frameworks have been proposed to overcome this issue, among which Robust Optimization which tackles the uncertainty by providing a set of possible values for these parameters, and considering the worst outcome over that set. In this paper, we consider the problem of scheduling a set of jobs J on the set of machines M , so as to minimize the makespan, and considering that the processing times are uncertain. What is more, we consider the budgeted uncertainty model introduced by Bertsimas et al. [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] where each processing time varies between its nominal value and the latter plus some deviation. Further, in any scenario, at most Γ of the uncertain parameters take the higher values, the other being at their nominal values.

Let us now formally define the Robust Scheduling on Unrelated Machines (R|U Γ |C max ) problem. For any job j ∈ J and machine i ∈ M , we denote by p ij ≥ 0 the nominal processing time of j on i, and by pij ≥ 0 the (potential) deviation of j on i. We point out that nominal processing times are non negative as it is also the case in the classical R||C max problem, and deviations are also non negative as in the uncertainty model U Γ defined below, any negative pij can be equivalently set to 0. A schedule σ is a function from J → M . We write σ i for the subset of jobs scheduled on machine i. Let U Γ = {ξ ∈ {0, 1} |J| : ξ 1 ≤ Γ } be the set of all possible scenarios where at most Γ jobs deviate. For any ξ ∈ U Γ , we set p ξ ij = p ij + ξ j pij to be the actual processing time of j on i in scenario ξ.

Let us now formalize some common terms, but with dependence on scenario ξ. The load of machine i in scenario ξ is calculated as j∈σ i p ξ ij . The makespan in scenario ξ is the maximum load in scenario ξ, i.e., C ξ max (σ) = max i∈M j∈σ i p ξ ij . Finally, C Γ max (σ) = max ξ∈U Γ C ξ max (σ) denotes the objective function we consider in Robust Scheduling, where the adversary takes the worst scenario among U Γ .

Next, we will state important observations about the objective function. We first need to introduce the following notations. Given a set of jobs X i scheduled on machine i, we define p(

X i ) = j∈X i p ij , p(X i ) = j∈X i pij , Γ (X i ) as the set of the Γ jobs of X i with the largest pij values (or Γ (X i ) = σ i when |X i | < Γ ) with ties broken arbitrarily. Finally, set pΓ (X i ) = p(Γ (X i )).
By definition we have C Γ (σ) = max ξ∈U Γ max i∈M j∈σ i C ξ (σ), and thus we can rewrite

C Γ (σ) = max i∈M max ξ∈U Γ j∈σ i C ξ (σ) = max i∈M C Γ (σ i ), where C Γ (σ i ) = max ξ∈U Γ j∈σ i C ξ (σ)
is the worst-case makespan on machine i. The benefit of rewriting C Γ (σ) in this form is that it is now clear that C Γ (σ i ) = p(σ i ) + pΓ (σ i ) as the worst scenario ξ for a fixed σ i is obtained by picking the Γ jobs with highest pij and make them deviate. Thus, R|U Γ |C max can also be thought as a "classical" scheduling problem (without adversary) where the makespan on a machine C Γ (σ i ) is simply the sum of all the nominal processing time of jobs of σ i , plus only the Γ largest deviating values of jobs of σ i . We are now ready to define R|U Γ |C max .

Problem 1. Robust Scheduling on Unrelated Machines (R|U

Γ |C max ) -Input: (J, M, p ∈ Q |M |×|J| + , p ∈ Q |M |×|J| +
) where J is the set of jobs, M the set of machines, p are the vectors of nominal processing times, and p the vectors of deviation -Output: find a schedule σ :

J → M -Objective function: min C Γ (σ) = max ξ∈U Γ max i∈M j∈σ i [p ij +ξ j pij ] = max i∈M C Γ (σ i ), where C Γ (σ i ) = p(σ i ) + pΓ (σ i ).
Following the classical three field notation, we denote by R|U Γ |C max the previous problem. Notice that when all pij = 0 the problem corresponds to the classical R||C max , for which we denote by C(σ i ) = j∈σ i p ij the makespan on machine i. We are also interested in a simplification of the above problem. This simplification is Robust Scheduling on Identical Machines (P |U Γ |C max ) where each has two processing times (p j and pj ), and we have p ij = p j and pij = pj for any i.

Robust scheduling has been considered in the past, mostly for finite uncertainty sets without particular structure [START_REF] Aloulou | Complexity of single machine scheduling problems under scenariobased uncertainty[END_REF][START_REF] Daniels | Robust scheduling to hedge against processing time uncertainty in single-stage production[END_REF][START_REF] Kasperski | Approximating a two-machine flow shop scheduling under discrete scenario uncertainty[END_REF][START_REF] Kasperski | Parallel machine scheduling under uncertainty[END_REF][START_REF] Mastrolilli | Single machine scheduling with scenarios[END_REF][START_REF] Kurpisz | Approximation schemes for robust makespan scheduling problems[END_REF]. More recently, robust packing and scheduling with the budgeted uncertainty model U Γ from Bertsimas et al. [START_REF] Bertsimas | The price of robustness[END_REF] has been considered [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF][START_REF] Tadayon | Algorithms and complexity analysis for robust single-machine scheduling problems[END_REF][START_REF] Basu Roy | Approximating robust bin-packing with budgeted uncertainty[END_REF]. Specifically, Bougeret et al. [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF] provided a 3-approximation algorithm and a (1 + )-approximation (PTAS) for P |U Γ |C max but only for a constant Γ , as well as a randomized approximation algorithm for R|U Γ |C max having an average ratio of O(log(m)), and an FPTAS for Rm|U Γ |C max (where the number of machines is fixed). It is also known [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF] that 1|U Γ | j w j C j is N P-hard in the strong sense, and is polynomial when w j = 1 for j ∈ J. Tadayon et al. [START_REF] Tadayon | Algorithms and complexity analysis for robust single-machine scheduling problems[END_REF] considered the robust one-machine problem for four commonly-used objective criteria: (weighted) total completion time, maximum lateness/tardiness, and number of late jobs. They showed that some of these problems are polynomially solvable and provide mixed-integer programming formulations for others. Their results considered U Γ as well as two closely related uncertainty sets. In a recent work [START_REF] Basu Roy | Approximating robust bin-packing with budgeted uncertainty[END_REF] (with also authors in common), it has been proved that robust bin-packing problem admits a constant-factor approximation algorithm, both for the U Γ model, and the uncertainty sets considered by Tadayon et al. [START_REF] Tadayon | Algorithms and complexity analysis for robust single-machine scheduling problems[END_REF].

In this paper we improve existing results [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF] for P |U Γ |C max and R|U Γ |C max . In Section 2 we show that any c-approximation for the classical R||C max problem leads to a (c + 1)-approximation for R|U Γ |C max , hence obtaining a 3-approximation algorithm for the latter problem, and a (2 + )-approximation for P |U Γ |C max . We point out that this result improves the previous ad-hoc 3-approximation for P |U Γ |C max [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF], while having a simpler proof. In Section 3, we show through a reduction from the Restricted Assignment Problem that there exists no (2-)-approximation algorithm for R|U Γ |C max unless P = N P. This implies that the best possible ratio (unless P = N P) for R|U Γ |C max is somewhere between 2 and 3, contrasting with the classical R||C max where the gap between 3 2 and 2 is open since the work of Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF]. In Section 4 we consider the P |U Γ |C max problem and present the first step of our main result, namely a PTAS which is valid even when Γ is part of the input, i.e., not constant. Having Γ in the input (and not constant) requires a totally different technique from the one used in the existing PTAS [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF] for fixed Γ . The algorithm is turned into an EPTAS in Section 5, i.e., a PTAS where the dependency of is not in the exponent of the encoding length.

A 3-approximation for unrelated machines

Theorem 1. Any polynomial c-approximation for R||C max implies a polynomial (c+1)approximation for R|U Γ |C max .

Proof. We design a dual approximation, i.e., given an instance I of R|U Γ |C max and an threshold T , we either give a schedule σ of I with C Γ (σ) ≤ (c + 1)T , or prove that T < OPT(I). Using a binary search on T this will imply a (c + 1)-approximation algorithm.

For that, given an instance I = (J, M, p, p) of R|U Γ |C max , and T the current threshold, our objective is to define an instance I = (J, M, p) of the classical R||C max problem. The transformation of a solution for I to a solution for I will be straightforward since the jobs and machines will be the same.

Given a machine i, let B

i = {j|p ij > T Γ } and S i = J \ B i . Define p ij := p ij + pij if j ∈ B i p ij otherwise. (1)
Let us now prove that (1) if OPT(I ) > T then we have OPT(I) > T , and (2) every schedule σ with makespan C I (σ) in I has a makespan at most

C I (σ) + T in I (C Γ (σ) ≤ C I (σ) + T ).
For (1), we prove that OPT(I) ≤ T implies that OPT(I ) ≤ T . Let σ be an optimal solution of I and i a machine. C Γ (σ) ≤ T implies that C Γ (σ i ) ≤ T for any i, and thus that p

(σ i ) + pΓ (σ i ) ≤ T . Now, observe that (B i ∩ σ i ) ⊆ Γ (σ i ). Indeed, assume towards contradiction that there exists j ∈ (B i ∩ σ i ) \ Γ (σ i ). This implies that |Γ (σ i )| = Γ . As by definition, any j ∈ Γ (σ i ) has pij ≥ pij > T Γ , we get that pΓ (σ i ) > T , a contradiction. This implies C I (σ i ) = p(σ i ) + p(B i ∩ σ i ) ≤ p(σ i ) + pΓ (σ i ) ≤ T .
For (2), let σ be a solution of

I . Let i ∈ M . Observe that p(Γ (σ i )) ≤ p(B i ∩ σ i ) + T as Γ (σ i ) contains at most Γ jobs in σ i \ B i , and these jobs have pij ≤ T Γ . Thus, C Γ (σ i ) = p(σ i ) + pΓ (σ i ) ≤ p(σ i ) + p(B i ∩ σ i ) + T = C I (σ i ) + T .
Thus, given a T and I we create I as above and run the c-approximation for R||C max to get a solution σ. If C I (σ) > cT then OPT(I ) > T , implying OPT(I) > T , and thus we reject T . Otherwise, we consider σ as a solution for I, and C Γ (σ) ≤ (c + 1)T .

Using the well-known 2-approximation algorithm from Lenstra et al. [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF], we obtain immediately the following.

Corollary 1. There is a 3-approximation for R|U Γ |C max .

Since by this reduction identical machines stay identical we also obtain the following using the EPTAS of Jansen et al. [START_REF] Jansen | Closing the gap for makespan scheduling via sparsification techniques[END_REF] for the classical P ||C max problem.

Corollary 2. For every > 0 there is a (2 + )-approximation for P |U Γ |C max running in time 2 O(1/ log(1/ ) 4 ) + poly(n).

We point out that even if the EPTAS of Jansen et al. [START_REF] Jansen | Closing the gap for makespan scheduling via sparsification techniques[END_REF] also holds for the Q||C max problem (where each machine i has a speed s i , and p ij = Theorem 2. Given an instance I of R|U Γ |C max , it is NP-complete to decide if OPT(I) ≤ 1 or OPT(I) ≥ 2, and thus for any > 0 is no (2 -)-approximation algorithm for R|U Γ |C max unless P = N P, even for Γ = 1 and when each job can be scheduled on at most 3 machines.

Proof. Let us define a reduction from 3-SAT to R|U Γ |C max with Γ = 1. Let I 0 be an instance of 3-SAT with clauses {C i , i ∈ [m 0 ]} and variables {x j , j

∈ [n 0 ]}. Each C i is of the form l 1 i ∨ l 2 i ∨ l 3
i where l k i ∈ {x j , xj } for some j. We define an instance I of R|U Γ |C max with m = 2n 0 machines and n = n 0 + m 0 jobs as follows. To each variable x j we associate two machines {j f , j t }. We create a set of n 0 variable jobs where for any j ∈ [n 0 ], p j f j = p jtj = 1, p i j = ∞ for any other i , and pij = 0 for any

i ∈ [m]. For any clause C i , i ∈ [m 0 ] we define M i : the set of 3 machines corresponding to literals {l k i } satisfying C i . For example, if C 7 = x 1 ∨ x3 ∨ x 5 then M 7 = {1 t , 3 f , 5 t }.
We now define a set of m 0 clause jobs as follows. For any j ∈ [n 0 + 1, n 0 + m 0 ], job j represents clause C j-n 0 with pij = 1 iff i ∈ M j-n 0 , pi j = ∞ for any other i , and p ij = 0 for any i ∈ [m]. For example, job j = n 0 +7 is associated to C 7 where in particular p1tj = p3 f j = p5tj = 1. Notice that each clause job can be scheduled on at most 3 machines. Let us now verify that I 0 is satisfiable iff OPT(I) = 1.

⇒. Suppose I 0 is satisfied by assignment a. For any j ∈ [n 0 ], we schedule j on j t if x j is set to false in a and on j f otherwise. For any j ∈ [n 0 + 1, n 0 + m 0 ], we schedule job j on any machine i ∈ M j-n 0 corresponding to a literal satisfying C i in assignment a. Notice that in this schedule, a machine either receives exactly one variable job, implying a makespan of 1, or only clause jobs, also implying a makespan of 1 as Γ = 1.

⇐. Suppose that OPT(I) = 1 and let us define an assignment a. This implies that any variable job j is either scheduled on machine j f , in which case we set x j to true, or on machine j t , in which case we set x j to false. As OPT(I) = 1, and clause job j ∈ [n 0 + 1, n 0 + m 0 ] is scheduled on a machine i ∈ M j-n 0 that did not receive a variable job, implying that clause j -n 0 is satisfied by literal i.

A PTAS for identical machines

Recall that for the P |U Γ |C max problem, given two n dimensional vectors p and p and the number of machine m, the objective is to create a schedule σ that minimizes max i∈M C Γ (σ i ). Recall also that C Γ (σ i ) = p(σ i ) + pΓ (σ i ), where p(σ i ) = j∈σ i p j , and pΓ (σ i ) is the sum of the pj values of the Γ largest jobs (w.r.t. pj ) of σ i (or the sum of all pj values if |σ i | ≤ Γ ). To obtain a PTAS for P |U Γ |C max , we will reduce to the following problem, which admits an EPTAS (see [START_REF] Jansen | An eptas for scheduling on unrelated machines of few different types[END_REF]).

Problem 2. Unrelated Machines with few Machine Types

-Input: n jobs and a set M of m machines with processing times p ij ≥ 0 for job j on machine i. Moreover, there is a constant k and machine types

T 1 ∪ • • • ∪T k = {1, .
. . , m}, such that every machine within a type behaves the same. Formally, for every k , every i, i ∈ T k and every j ≤ n it holds that p ij = p i j -Output: find a schedule σ :

J → M -Objective function: minimize makespan C(σ) = max i∈M C(σ i ), where C(σ i ) = j∈σ i p ij
Notice that the EPTAS of Jansen and Maack [START_REF] Jansen | An eptas for scheduling on unrelated machines of few different types[END_REF] for this problem provides an (1 + )approximation running in time f (|I|, , k) = 2 O(k log(k) 1 log 4 ( 1 )) + poly(|I|).

We also introduce the following decision problem.

Problem 3. Unrelated Machines with few Machine Types and capacities -Input: as above, but in addition every machine i has a capacity c i ∈ (0, 1]. Moreover, capacities are the same among a type (for any k ∈ [k], for any i, i ∈ T k , c i = c i ) -Output: decide if there is a schedule where C(σ i ) ≤ c i for any i.

Notice that the EPTAS for Problem 2 allows to approximately decide Problem 3 in the following sense.

Lemma 1. There is an algorithm that for any > 0, either outputs a schedule with C(σ i ) ≤ (1 + ) • c i for any i, or reject the instance, proving that there is no schedule with C(σ i ) ≤ c i for any i. This algorithm runs in time f (|I|, , k) where f is the complexity of the above EPTAS to get a (1 + )-approximation.

Proof. Let A be the EPTAS of Jansen and Maack [START_REF] Jansen | An eptas for scheduling on unrelated machines of few different types[END_REF] for Problem 2. Given a input I of Problem 3 we define an input I of Problem 2 in the following way. For every j ≤ n, scale p ij to p ij /c i . Then, if A(I ) ≤ (1 + ), we can convert the solution found by A into a solution for I of makespan at most (1 + ) • c i for any i. Otherwise, as A is a (1 + )-approximation, it implies that OPT(I ) > 1, and thus that no solution can have makespan at most c i for any i.

Let us now describe the PTAS for P |U Γ |C max . Our objective is to provide a (1+O( )) dual approximation for P |U Γ |C max . The constant multiplying can be ignored since we can divide by this constant in a preprocessing step.

1. Guess the makespan and scale OPT to 1. Let I be an input of P |U Γ |C max , and T be a positive value (representing the current threshold). We start by redefining I by scaling p j := p j T . Our objective is now to produce a schedule σ with C Γ (σ) ≤ 1 + , or to prove that OPT(I) > 1.

Rounding deviations.

Let us now define I 1 (having vectors p 1 and p1 ) in the following way. For any j, if pj < /Γ then we set p1 j ← 0. Intuitively, this will only result in an error of at most Γ • /Γ on every machine. Otherwise (p j ≥ /Γ ), we define p1 j by rounding pj to the closest smaller value of the form /Γ • (1 + ) i . In the following, we will denote by C I Γ (σ) the cost of σ for an instance I .

Observation 2 If OPT(I) ≤ 1 then OPT(I 1 ) ≤ 1. If we get solution σ 1 of I 1 , then

C I Γ (σ 1 ) ≤ (1 + )C I 1 Γ (σ 1 ) +
It only remains now to either produce a good solution of I 1 (of cost at most 1+O( )), or prove that OPT(I 1 ) > 1.

3. Machine thresholds. Given any solution σ of I 1 such that C I 1 Γ (σ) ≤ 1, we can associate to σ an outline ψ(σ) (denoted as an m dimensional vector t) which is defined as follows. For any machine i with more that Γ jobs, the threshold value t i is such that any job on i with pj > t i deviates (belongs to Γ (σ i )) and none of the jobs with pj < t i deviate. Notice that among jobs with pj = t i , some may deviate, but not necessarily all. For any machine i with at most Γ jobs, we define t i = 0, implying again that any job with pj > t i deviates on i. Notice that in both cases we have pΓ

(σ i ) ≥ Γ • t i . Notice also that C I 1 Γ (σ) ≤ 1 implies t i ≤ 1 Γ .
Indeed, if we had t i > 1 Γ , there would be Γ deviating jobs with pj > t i , implying C I 1 Γ (σ i ) > 1, a contradiction. Let us denote by ∆ the set of all possible values of a t i . According to Observation 1 we have |∆| = O(1/ log(1/ )). Let P = ∆ m be the set of all possible outlines (of solutions of cost at most 1).

Lemma 2. Consider a solution σ 1 * of I 1 such that C Γ (σ 1 * ) ≤ 1, and let t * = ψ(σ 1 * ). Then, we can guess in m O(1/ log(1/ )) time the vector t * (or a permutation thereof ).

Proof. As t * ∈ T , all the t * i have a value in {0} ∪ [ Γ , 1 Γ ]. Thus, as deviating values are rounded in I 1 , there are only a constant number of possible threshold value and we can guess them. For every possible threshold, we guess how many machines in the optimal solution have it.

Thus, we can now assume that we know the vector t * .

Constructing an instance with few machine types and capacities.

To give an insight of the correct reduction defined below, let us first see what happen if we define an instance I 2 (t * ) of R||C max as follows. For simplicity, we also assume that there are no job with pj = t * i on each machine i in the previously considered optimal solution of I 1 . For any machine i and job j, define the processing time in I 2 (t * ) as p ij = p j + pj if pj ≥ t * i , and p ij = p j otherwise. Then, consider the following implications.

1. if OP T (I 1 ) ≤ 1, then OPT(I 2 (t * )) ≤ 1 2. for any solution σ of I 2 (t * ), C I 1 Γ (σ ) ≤ C I 2 (σ ) (implying that if there exists σ with C I 2 (σ ) ≤ 1 + , then we will have our solution for I 1 of cost 1 + ) While Property (1) holds, this is not the case for Property [START_REF] Basu Roy | Approximating robust bin-packing with budgeted uncertainty[END_REF]. Indeed, suppose that in σ there is a machine i such that for all jobs j scheduled on i, pj < t * i . This implies that C(σ i ) = j∈σ i p j . However, if we look now at σ in I 1 , we get

C I 1 Γ (σ i ) = C I 2 (σ i ) + p(Γ (σ i ))
, which is greater than the claimed value. To solve this problem we have to remember in R||C max that there will be a space of size at most Γ • t i which will be occupied by deviations.

Let us now turn to the correct version.

Definition 1. For any t ∈ P, we define the following input I 2 (t) of Problem 3. We set the machine capacity to

c i := 1 -Γ • t i + .
The addition of is only a technicality to ensure that all c i are non-zero. Note that if there are less than Γ jobs on i, then t i must be 0 and therefore c i = 1 + . For every job j set

p ij := p j + pj -t i if pj ≥ t i , p j if pj < t i .
Note that at pj = t i , the values of both cases are equal. Notice also that in I 2 (t) there are only |∆| different machine types.

Lemma 3. If OPT(I 1 ) ≤ 1 and t is the outline of an optimal solution σ 2 , for any i,

C I 2 (t) (σ 2 i ) ≤ c i . Proof. Let us consider jobs σ 2 i scheduled on machine i. If t i = 0, then j∈σ 2 i p ij = j∈σ 2 i p j + pj ≤ 1 < c i . Assume now t i > 0, implying that |Γ (σ 2 i )| ≥ Γ . By choice of t i , every job j ∈ Γ (σ 2 i ) has pj ≥ t i and every j ∈ σ 2 i \ Γ (σ 2 i ) has pj ≤ t i . This implies j∈σ 2 i p ij = j∈Γ (σ 2 i ) p ij + j∈σ 2 i \Γ (σ 2 i ) p ij = j∈Γ (σ 2 i ) [p j + pj -t i ] + j∈σ 2 i \Γ (σ 2 i ) p j ≤ 1 -Γ • t i < c i .
Lemma 4. For any t ∈ P, if there is a solution

σ 2 of I 2 (t) such that C I 2 (t) (σ 2 i ) ≤ (1 + ) • c i for any i, then C I 1 Γ (σ 2 ) ≤ (1 + ) 2 .
Proof. Let i be a machine. Then for every j ∈ σ 2 i ,

p ij = p j + pj -t i ≥ p j if pj ≥ t i , p j if pj < t i .
Furthermore, for every j ∈ Γ (σ 2 i ),

p ij = p j + pj -t i if pj ≥ t i , p j > p j + pj -t i if pj < t i . This implies, j∈Γ (σ 2 i ) [p j + pj ] + j∈σ 2 i \Γ (σ 2 i ) p j ≤ Γ • t i + j∈Γ (σ 2 i ) [p j + pj -t i ] + j∈σ 2 i \Γ (σ 2 i ) p j ≤ Γ •t i + j∈Γ (σ 2 i ) p ij + j∈σ 2 i \Γ (σ 2 i ) p ij = Γ •t i + j∈σ 2 i p ij ≤(1+ )•c i ≤ Γ •t i +(1+ )•(1-Γ •t i + ) ≤ (1+ ) 2 .
Theorem 3. There is a (1+ )-approximation algorithm for

P |U Γ |C max running in time O(m O(1/ log(1/ )) × f (|I|, , O(1/ log(1/ )))
where f is the function of Lemma 1. This implies a running time in m O(1/ log(1/ )) (2 g( ) +|I| O(1) ), where g( ) = O((1/ ) 2 log 6 (1/ )).

Proof. Given I input of P |U Γ |C max and a threshold T , we run algorithm A of Lemma 1 on I 2 (t) for any t ∈ P with a precision . If A rejects all the I 2 (t) then we can reject T according to Observation 2 and Lemma 3. Otherwise, there exists t 0 such that A(I 2 (t 0 )) outputs a schedule σ 2 where C I 2 (t 0 ) (σ 2 ) ≤ (1 + ) • c i for any i, implying C I Γ (σ 2 ) ≤ (1 + )C I 1 Γ (σ 2 ) + ≤ (1 + ) 3 + ≤ 1 + 5 according to Observation 2 and Lemma 4 (for sufficiently small ). Finally, the running time is as claimed due to the bound of P in Lemma 2.

EPTAS for identical machines

The approach for an EPTAS is similar to the PTAS above. We would like to remove the bottleneck from the previous section, which is the guessing the thresholds. In the PTAS we notice that even if the thresholds were chosen incorrectly, but we find a solution to the derived problem, we can get a good solution for the initial problem. Informally, we will now still create an instance of Problem 3, but we only guess approximately the number of machines for each threshold.

We start by defining I 1 as in the previous section. Given any solution σ 1 of I 1 such that C I 1 Γ (σ 1 ) ≤ 1, we can associate to σ a restricted outline m = ψ(σ) where m is defined as follows. Let t = ψ(σ). For any threshold value l ∈ ∆, let m l = |{i|t i = l}| be the number of machines with threshold l in σ 1 . We define m l ∈ {0, 1, 2, 4, 8, . . . , 2 log(m) } such that m l ≤ m l < 2m l . Let P = {m ∈ {0, 1, 2, 4, 8, . . . , 2 log(m) } ∆ such that m 2 ≤ l m l ≤ m} be the set of possible restricted outlines (of solutions of cost at most 1).

Lemma 5. Consider a solution σ 1 * of I 1 such that C Γ (σ 1 * ) ≤ 1, and let m * = ψ(σ 1 * ). Then, we can guess in time 2 O(1/ log 2 (1/ )) + m O (1) the vector m * .

Proof. Clearly it suffices to iterate over all values m i ∈ {0, 1, 2, 4, 8, . . . , 2 log(m) }, i.e., O(log(m)) many. Guessing this number for every threshold value in ∆ takes log O(1/ log(1/ )) (m) time. Consider first the case when log(m)/ log log(m) ≤ 1/ log(1/ ). Observe that for any m ≥ 2, it holds that log 1/2 (m) ≤ log(m)/ log log(m). This implies that log 1/2 (m) ≤ 1/ log(1/ ). Hence,

log O(1/ log(1/ )) (m) = (log 1/2 (m)) 2•O(1/ log(1/ )) ≤ (1/ log(1/ )) O(1/ log(1/ )) ≤ 2 O(1/ log 2 (1/ )) .
If on the other hand, if log(m)/ log log(m) ≥ 1/ log(1/ ), then 1) .

log O(1/ log(1/ )) (m) ≤ log O(log(m)/ log log(m)) (m) = 2 O(log(m)/ log log(m)•log log(m)) = m O(1) . We conclude, log O(1/ log(1/ )) (m) ≤ 2 O(1/ log 2 (1/ )) + m O (
From all the guesses, we report fail whenever i m i < m/2 or i m i > m.

For any m ∈ P, we define the following input I 2 (m) of Problem 3. We first create for any l a set M l of m l machines where for each machine i ∈ M l the capacity and the p ij are defined as in Definition 1 for threshold t i = l. Then, we create another set M l of m l machines (that we call cloned machines) with the same capacity and the same p ij values. Let m = m l . Notice that the total number of machines is 2m , with m ≤ 2m < 2m. Thus, we have to ensure that not too many machines are used in total. For that purpose we add a set of 2m -m dummy jobs D, where all j ∈ D have p ij = ∞ on the original machines i ∈ M l and p ij = c i on every cloned machine i ∈ M l . Notice that the number of types is now 2|∆|, which is still small enough to get an EPTAS. Let us call the non-dummy jobs regular jobs. Lemma 6. If OPT(I 1 ) ≤ 1 and m is the restricted outline of an optimal solution, then there exists a solution σ 2 of I 2 (m) such that for any i, C

I 2 (m) (σ 2 i ) ≤ c i .
Proof. Let m * l = |{i|t i = l}| be the number of machines with threshold l in the considered optimal solution of I 1 . Let l ∈ ∆ be a threshold value. We first schedule 2m l -m * l many dummy jobs on cloned machines of M l . This will cover all dummy jobs, since

l [2m l -m * l ] = 2 l m l - l m * l = 2m -m.
We will now schedule all remaining jobs on the empty machines. For every threshold value l we have 2m l -(2m l -m * l ) = m * l many empty machines. In other words, we are left with an instance with the exact same number of machines for each threshold as in the optimal solution and with the original jobs. As argued in Lemma 3, we get the desired claim.

Lemma 7. For any m ∈ P, if there is a solution σ 2 of I 2 (m) such that C I 2 (m) (σ 2 i ) ≤ c i + for any i, then we can deduce a solution σ 3 for I 1 with C

I 1 Γ (σ 3 ) ≤ (1 + 2 ) 2 .
Proof. We will first normalize σ 2 . Since dummy jobs have p ij = c i on cloned machines, in a (1 + )-approximation there can only be one per machine (assuming that < 1). Indeed, there may still be a load of • c i from other jobs on the same machine. We want to ensure that every machine either has a dummy job or some regular load, but not both. For every threshold value l ∈ ∆, there can be at most m l machines in M l that have a dummy job. For any such machine in M l , we remove all the regular jobs (of total load of at most •c i ) from it and move them to one of the original machines in M l , without using the same machine in M l twice. Since for any i ∈ M l we had C I 2 (m) (σ 2 i ) ≤ (1 + )c i before moving the jobs, and since regular jobs have the same processing time on machines M l and M l , after moving the jobs we get C I 2 (m) (σ 2 i ) ≤ (1 + 2 )c i for any i ∈ M l . We now have a solution violating the capacities by at most 2 • c i such that a machine with a dummy job has no other jobs.

We now forget about all dummy jobs and the machines they are on. What we are left with is a set of m machines (with some thresholds t) such that for any i we have C I 2 (m) (σ 2 i ) ≤ (1 + 2 )c i . By Lemma 4 we get the desired result.

All in all, we were able to reduce the number of instances created to only 2 O(1/ log 2 (1/ )) + m O(1) many and removed the bottleneck from the PTAS this way. This leads to the following result.

Conclusion

In this article we have provided approximation results for P |U Γ |C max , Q|U Γ |C max and R|U Γ |C max , improving the results obtained by Bougeret et al. [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF]. The complexity status of P |U Γ |C max is somehow closed as we cannot hope for an FPTAS. Yet this paper leaves open two interesting questions: closing the [2 -, 3] gap for the approximability of R|U Γ |C max , and determining whether Q|U Γ |C max admits a PTAS.

Observation 1

 1 In I 1 there are at most O(1/ log(Γ/ )) deviation values, and at most O(1/ log(1/ )) deviation values in the interval [ /Γ, 1/Γ ].

Theorem 4 .

 4 There is a (1+ )-approximation algorithm for P |U Γ |C max running in timeO(2 O(1/ log 2 (1/ )) +m O(1) )×f (|I|, , O(1/ log(1/ )))where f is the function of Lemma 1. This implies a running time in 2 g( ) |I| O(1) , where g( ) = O((1/ ) 2 log 6 (1/ )).Proof. As in Theorem 3, given an instance of P |U Γ |C max we will use the algorithm of Lemma 1 on I 2 (m) for any m ∈ P. As according to Lemma 5 we have|P| ≤ 2 O(1/ log 2 (1/ )) + m O(1) , we get a running time in O(2 O(1/ log 2 (1/ )) + m O(1) ) × f (|I|, , O(1/ log(1/ )))where f is the function of Lemma 1. This running time can be rewritten(2 O(1/ log 2 (1/ )) + m O(1) ) × (2 O((1/ ) 2 log 6 (1/ )) + |I| O(1)), implying the claimed bound.

p j s i ), Corollary 2 cannot be extended to Q|U Γ |C max using the same reduction. Indeed, starting from a Q|U Γ |C max instance (where each job has only two processing times p j and pj , and we have p ij = p j s i , pij = pj s i for any i), the above reduction would create an instance of R||C max (and not of Q||C max ) as some job may require more than T Γ on a machine, and less that T Γ on another.3 A 2 -inapproximability for unrelated machinesFor the classical R||C max problem, when all p ij ∈ {1, ∞}, deciding if the optimal value is at most 1 is polynomially solvable as it can be reduced to finding a matching in a bipartite graph. The result below shows that answering the same question for R|U Γ |C max is N P-complete.

This work was supported by DFG Project, "Robuste Online-Algorithmen für Scheduling-und Packungsprobleme", JA 612/19-1, by the Jacques Hadamard Mathematical Foundation (FMJH) Gaspard Monge Program for optimization and operations research, the EDF, as well as the ANR project ROBUST [ANR-16-CE40-0018].


Chuan Xu
email: chuan.xu@inria.fr

Giovanni Neglia
email: giovanni.neglia@inria.fr

What else is leaked when eavesdropping Federated Learning?

In this paper, we initiate the study of local model reconstruction attacks for federated learning, where a honest-but-curious adversary eavesdrops the messages exchanged between the client and the server and reconstructs the local model of the client. The success of this attack enables better performance of other known attacks, such as the membership attack, attribute inference attacks, etc. We provide analytical guarantees for the success of this attack when training a linear least squares problem with full batch size and arbitrary number of local steps. One heuristic is proposed to generalize the attack to other machine learning problems. Experiments are conducted on logistic regression tasks, showing high reconstruction quality, especially when clients' datasets are highly heterogeneous (as it is common in federated learning).

Introduction

Federated learning (FL) [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF][START_REF] Lian | Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent[END_REF][START_REF] Li | Federated optimization in heterogeneous networks[END_REF] offers naturally a certain level of privacy, as clients' data is not collected at a third party. However, maintaining the data locally does not provide itself formal privacy guarantees. An (honest-but-curious) adversary can still infer some sensitive client information just by eavesdropping the exchanged messages (e.g., gradients). In fact, multiple recent works have shown the possibility to reconstruct private data samples (e.g., images) by inverting the gradients [START_REF] Zhu | Deep leakage from gradients[END_REF][START_REF] Zhao | idlg: Improved deep leakage from gradients[END_REF][START_REF] Geiping | Inverting gradients-how easy is it to break privacy in federated learning? NIPS[END_REF][START_REF] Wei | A framework for evaluating gradient leakage attacks in federated learning[END_REF][START_REF] Hongxu Yin | See through gradients: Image batch recovery via gradinversion[END_REF]. This attack works well when gradients are calculated on extremely small batches or data points belonging to the same class are similar, e.g., personal images of the same person or images of the same digit in MNIST dataset. However, this attack may not apply to FL settings, especially when clients are allowed to do multiple stochastic gradient updates locally to save significant communication costs. In [START_REF] Wei | A framework for evaluating gradient leakage attacks in federated learning[END_REF]Table 6a] the authors show that the success rate of a reconstruction attack degrades from 100% to 39% when the number of local steps increases from 1 to 9, and degrades from 100% to 13% when the batch size increases from 1 to 16. Similarly, anther study [START_REF] Hongxu Yin | See through gradients: Image batch recovery via gradinversion[END_REF] shows that the best attack by inverting the gradients can identify just 28% of ImageNet images with batch size equal to 48. In addition to the reconstruction attack, other attacks like membership attack and property inference attack (the adversary can infer when a property appears or disappears in the data during training) are also studied for FL [START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF]. Furthermore, these attacks are less effective as batch size increases [START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF]Table II], and the application of differential private techniques does not change the result [10, Figure 1,[START_REF] Kadhe | Fastsecagg: Scalable secure aggregation for privacy-preserving federated learning[END_REF].

In this paper, we initiate the study of a new attack, called the local model reconstruction attack, where the adversary seeks to reconstruct the model a client would have trained using only its local dataset. Allowing the adversary to have such information is dangerous, as the adversary can then target various types of personal information using model inversion attacks [START_REF] Fredrikson | Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing[END_REF][START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF], membership attacks [START_REF] Shokri | Membership inference attacks against machine learning models[END_REF], attribute inference attacks [14-16]1 , etc. Again, we assume a weak adversary, who is honest-but-curious (i.e., it does not interfere with the training process) and only eavesdrops the exchanged messages between the client and the server. The adversary knows the structure of the trained model and the loss function, as well as the training algorithm, which is common in the attacks for FL [START_REF] Geiping | Inverting gradients-how easy is it to break privacy in federated learning? NIPS[END_REF][START_REF] Wei | A framework for evaluating gradient leakage attacks in federated learning[END_REF][START_REF] Hongxu Yin | See through gradients: Image batch recovery via gradinversion[END_REF][START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF][START_REF] Nasr | Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning[END_REF]. Differently from the attacks proposed in literature, a local model reconstruction attack benefits from a larger batch size and is less sensitive to the number of local steps in FL.

First, we show analytically that, when training a linear least squares problem with full batch size and arbitrary number of local steps in FL, the adversary can reconstruct the exact local model of every client, just by eavesdropping the exchanged messages for Θ(d) number of rounds, where d is the number of the features in the data sample (Sec. 3.1). Second, we propose a heuristic to perform this attack on any machine learning problem (Sec. 3.2). Empirical results show that our heuristic works well for logistic regression problems (Sec. 4).

Motivation

We denote by C the set of all clients participating to FL. Let D c be the local dataset of client c ∈ C drawn from a universe X and |D c | be the size of D c . In FL, clients cooperate to learn a global model, which minimizes the following (weighted) empirical risk over all the data owned by clients:

min θ∈R d L(θ), where L(θ) = c∈C p c L c (θ) = c∈C p c 1 |D c | x∈Dc l(θ, x) , (1)
where l(θ, x) : R d , X → R + measures the loss of the model θ on the sample x ∈ X and p c is the positive weight of client c, s.t. c∈C p c = 1. Let θ * = arg min θ∈R d L(θ) be the global optimal model, i.e., the true minimizer of problem [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF]. The global model is the objective of FL training, and could be the target from where the adversary starts different attacks, such as membership attacks [START_REF] Shokri | Membership inference attacks against machine learning models[END_REF], model inversion attacks [START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF], and attribute inference attacks [START_REF] Prasad Kasiviswanathan | The power of linear reconstruction attacks[END_REF][START_REF] Yeom | Privacy risk in machine learning: Analyzing the connection to overfitting[END_REF][START_REF] Jayaraman | Evaluating differentially private machine learning in practice[END_REF]. However, applying these attacks on the global model suffers from the plausible deniability of the clients, as the global model does not capture identity information of data instances (i.e., to which client each data belongs). Moreover, due to the heterogeneity of the data distribution, the global model may not perform well on individual local data, which makes these attacks less accurate.

In this paper, we propose the idea that the adversary can perform the attacks mentioned above not on the global model learned through FL, but on the local optimal model θ * c , i.e., θ * c = arg min L c (θ). Then, the adversary needs first to estimate such a local model; this first step is the local model reconstruction attack we focus on in this paper. The local model reconstruction attack benefits from the local model overfitting the client's dataset and is more effective under non-i.i.d. clients' data distributions, which is exactly the case in FL. In FL, the degree of non-i.i.d can be quantified by the dissimilarity between the global optimal model and the local optimal model. In [START_REF] Li | On the convergence of fedavg on non-iid data[END_REF], the authors define the degree as c∈C p c (L c (θ * ) -L c (θ * c )). In [START_REF] Khaled | First analysis of local gd on heterogeneous data[END_REF][START_REF] Khaled | Tighter theory for local SGD on identical and heterogeneous data[END_REF], the authors define the dissimilarity degree as c∈C p c (∇L c (θ * ) -∇L c (θ * c )).

Local model reconstruction

To start, we present a general framework for FL in Algo. 1, which generalizes a majority of the FL algorithms, including FedAvg [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF], FedProx [START_REF] Li | Federated optimization in heterogeneous networks[END_REF], and FL with different client sampling techniques [START_REF] Nishio | Client selection for federated learning with heterogeneous resources in mobile edge[END_REF][START_REF] Chen | Optimal client sampling for federated learning[END_REF][START_REF] Cho | Client selection in federated learning: Convergence analysis and power-of-choice selection strategies[END_REF]. The model θ = θ(T ) in the FL framework is the final output for problem [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF]. Its performance depends on the applied FL algorithm, which precises how the clients are selected in line 2, how the updated local models are aggregated in line 5 and how the local update rule works in line 8.

Our attack targets any FL algorithm falling into the framework presented in Algo. 1. Notice that this FL framework does not consider the possible use of secure aggregation protocols [START_REF] Bonawitz | Practical secure aggregation for privacy-preserving machine learning[END_REF][START_REF] Kadhe | Fastsecagg: Scalable secure aggregation for privacy-preserving federated learning[END_REF], which allow the server to aggregate the local updates without having access to each individual update. Secure aggregation protocols prevent our adversary from decoding the local model of a specific client, as the identity information is lost after secure aggregation. However, they require significant additional computation, which makes these protocols hard to scale to a large system when training a large neural network. In this paper, we consider the case where no secure aggregation protocol is applied. Remember that the known attacks for FL where Algorithm 1 Framework for cross-device federated learning

Output: θ(T ) Server: // global model θ ∈ R d , local models {θ c ∈ R d , ∀c ∈ C}. 1: for t ∈ {0, ..., T -1} do 2:
Server selects a subset of the clients C s (t) ⊆ C,

3:

Server broadcasts the current global model θ(t) to C s (t),

4:

Server waits for the updated local models θ c from every client c ∈ C s (t), Client listens for the arrival of new global model θ,

8:

Client updates its local model:

θ c ← Local Update c (θ, D c ) 9:
Client sends back θ c to the server.

the clients are honest, such as gradient reconstruction attack [START_REF] Zhu | Deep leakage from gradients[END_REF][START_REF] Zhao | idlg: Improved deep leakage from gradients[END_REF][START_REF] Geiping | Inverting gradients-how easy is it to break privacy in federated learning? NIPS[END_REF][START_REF] Wei | A framework for evaluating gradient leakage attacks in federated learning[END_REF][START_REF] Hongxu Yin | See through gradients: Image batch recovery via gradinversion[END_REF] and inference attack [START_REF] Nasr | Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning[END_REF], are all against FL without secure aggregation protocols.

L c (θ) = Xθ -y 2 m (2) Let H = X T X, we know that θ * c = (X T X) -1 X T y.
When the batch size is set to m in FedAvg:

g(θ) = 2 m (Hθ -Hθ * c ) . (3)
At round t, if client c is selected, it receives the server model and executes Algo. 2. Let θ t c (e) be the model after the e-th local epoch's update. Replacing (3) with line 4 in Algo. 2, we have

θ t c (E) = θ t c (E -1) - 2η m Hθ t c (E -1) -Hθ * c = (I - 2η m H)θ t c (E -1) + 2η m Hθ * c = (I - 2η m H) E θ t c (0) + I -(I - 2η m H) E θ * c . Let W = I -(I -2η m H) E and v = Wθ * c .
We have

θ t c (0) -θ t c (E) = I -(I - 2η m H) E θ t c (0) -I -(I - 2η m H) E θ * c ( 4
) =Wθ t c (0) -v. (5)
Note that θ t c (0) is the server model and θ t c (E) is model returned from client c to server in Algo. 2. The adversary has access to both of them as it can eavesdrop messages exchanged between the server and the client. Since W ∈ R d×d and v ∈ R d , once the adversary gets d + 1 exchanged messages, it can reconstruct the exact matrix W and the vector v by solving d systems (one for each row of W and the corresponding element of v in ( 5)), each with d + 1 linear equations (one for each communication round). Solving a system of d + 1 linear equations requires O(d3 ) operations, thus solving d systems in parallel requires only O(d 3 ) operations. Since H is positive definite, W is invertible. Then, we can compute θ * c = W -1 v. Note that in this reconstruction process, the adversary does not require knowledge of the parameters in FedAvg, such as the learning rate and the number of local steps.

Observation 2. Consider training a least squares linear regression through FedAvg and assume that a client's design matrix has rank d equal to the number of features. For any FL algorithm where a client's local update rule can be seen as a first-order black box 3 , at least one client is required to communicate with the server Ω(d) times for the convergence to the optimum. In addition, to reconstruct the local optimal model of this client, the adversary must eavesdrop Ω(d) times.

Proof. To prove the lower bound for the communications, we construct the specific "hard" scenario. This scenario is inspired by the work for studying the lower bound for convergence of smooth convex function [26, Sect. 2.1.2].

Let c be the client having the local dataset (X, y) such that H = X T X is a tridiagonal matrix with H i,i+1 = H i+1,i = -1/2 and H i,i = 1, ∀i ∈ {1, 2, ..., d}, and X T y = [1/2, 0, 0, ..., 0] T . By substituting H and X T y into (2), we have

L c (θ) = 1 m θ T Hθ -2(X T y) T θ -y T y = 1 m d i=1 θ 2 [i] - d-1 i=1 θ [i] θ [i+1] -θ [1] -C , (6)
where C is a constant and

θ * c = arg min L c (θ) = H -1 X T y = [1 -1 d+1 , 1 -2 d+1 , ..., 1 -d d+1 ] T . According to (6), we know that if θ [i] = θ [i+1] = . . . = θ [d] = 0, then ∇L c (θ) [i+1] = . . . = ∇L c (θ) [d] = 0.
At the same time, for the other clients ∀c ∈ C \ c, we assume their local optimum are zeros and their H ∈ R d×d are identity matrices, i.e., θ * c = 0 and H = I. Under this setting, according to Observation 1, we know that if the i th element of the global model is zero, i.e., θ(t) [i] = 0, then θ t c(E) [i] = 0. Moreover, it is reasonable to assume that every element of the global optimum is non-zero, i.e., θ *

[i] = 0, ∀i ∈ {1, .., d}. Now, suppose that we run the FL algorithm (Algorithm 1) under the above scenario, with initial global model θ(0) = 0, i.e., θ 0 c (0) = 0, ∀c ∈ C. According to the previous analysis, we know that ∀t ∈ {0, 1..., d -1}:

θ t c (E) [t+1] = θ t c (E) [t+2] = . . . = θ t c (E) [d] = 0, (7)
and

θ(t) [t+1] = θ(t) [t+2] = . . . = θ(t) [d] = 0. (8)
Therefore, to reach the non-zeros global optimum, the client c needs to communicate with the server (be selected by the server) for at least d times.

Moreover, to recover the local optimum of client c, the adversary must listen on the communication channel for at least d times. Suppose that the client c holds another local data set which gives H equals to H except that the last row and the last column are zeros. Under this case, the adversary will have the same observation as for the case of H till round d -1.

Combining Observation 1 and Observation 2, we can conclude that the reconstruction algorithm presented in Observation 1 for least squares linear regression training through FedAvg, is optimal for local model reconstruction attack, in terms of the number of the communications that the adversary eavesdrops.

Heuristic for local model reconstruction

In this section, we propose a heuristic (Algo. 3) for a local model reconstruction attack suited for any algorithm falling into the FL framework (Algo. 1) and any machine learning problem.

Let T c be the indexes of the rounds at which client c has been selected by the server, i.e., T c = {t|c ∈ C s (t), ∀t ∈ {0, . . . , T }}. We denote by M c the messages exchanged in Algo. 1 between client c and the server, i.e., M c = {(θ(t), θ c (t)), ∀t ∈ T c }. Our approach to (approximately) reconstruct the local model of client c consists of two steps. First, the adversary learns a mapping function G c to mimic the local update rule of the client, by exploring the messages in M c (see [START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF] in Algo. 3). More precisely, given the server model θ as input, G c predicts the update difference ∆θ = θ -θ c . Second, the adversary estimates the local model of client c as the one which minimizes G c (θ) 2 (see [START_REF] Fan | Rethinking privacy preserving deep learning: How to evaluate and thwart privacy attacks[END_REF] in Algo. 3). The intuition behind this step is that the client does not update the model (∆θ = 0) once it has reached the local optimal model. When executing FedAvg using full batch size, the exact mapping function G c can be correctly estimated for least squares linear regression, and is shown to be linear (see [START_REF] Zhao | idlg: Improved deep leakage from gradients[END_REF] in the proof of Observation 1). In this case, minimizing G c 2 corresponds to solving the linear systems mentioned in the proof. We can then conclude that the decoding algorithm in Observation 1 can be seen as a particular instance of Algo. 3 and, in particular, leads to an exact local model reconstruction as proved above.

Generally speaking, the performance of our heuristic depends on two effects: 1) How well the mapping function G c mimics the behavior of the local update rule integrated in FL algorithm, 2) How close is the estimated θ to the true minimizer of problem [START_REF] Fan | Rethinking privacy preserving deep learning: How to evaluate and thwart privacy attacks[END_REF], when G c is non-convex.

The first effect depends on the complexity of the learning task, the randomness introduced by the local update rule in the FL algorithm (line 8 in Algo. 1), and the number of messages observed by the adversary. More randomness is introduced, less accurate is the estimation of G c , and then the final local model reconstruction. This corresponds to the fact that differentially private algorithms, which amplify the randomness in the original algorithm by adding noise, sub-sampling [START_REF] Balle | Privacy amplification by subsampling: Tight analyses via couplings and divergences[END_REF][START_REF] Wang | Subsampled rényi differential privacy and analytical moments accountant[END_REF], reshuffling [START_REF] Yu | Differentially private model publishing for deep learning[END_REF][START_REF] Sasy | Oblivious sampling algorithms for private data analysis[END_REF], etc., can better protect private information from attacks. The second effect depends on the convexity of problem [START_REF] Fan | Rethinking privacy preserving deep learning: How to evaluate and thwart privacy attacks[END_REF], and then on the structure of G c .

Experiment

We have evaluated our proposed heuristic (Algo. 3) on two logistic regression tasks in the federated learning setting: LEAF synthetic [START_REF] Caldas | Leaf: A benchmark for federated settings[END_REF] and Adult [START_REF] Dua | UCI machine learning repository[END_REF] (detailed below). For the structure of the mapping function G c , we use a simple neural network with one hidden layer of size 1000 followed by ReLu activation. Adam optimizer is used for solving the problems ( 9) and [START_REF] Fan | Rethinking privacy preserving deep learning: How to evaluate and thwart privacy attacks[END_REF].

LEAF synthetic This dataset is designed for classification, where clients' data sets are highly heterogeneous both in terms of number of samples and underlying statistical distribution. The detailed generation procedure can be found in [START_REF] Caldas | Leaf: A benchmark for federated settings[END_REF]Appendix A]. We set the number of features to 10, the number of the classes to 2, the number of clusters (determining statistical heterogeneity) to 5, and the number of the clients to 5. The batch size is set to 256. The numbers of samples for each client are 280, 184, 1536, 256 and 208 respectively.

Adult This dataset contains individual information such as sex, age, education level, family situation, working class, etc. This information is used to predict whether a person has an income higher than 50k$, which can be seen as sensitive information. We perform our attack on a subset of the data where the individual's education level is at least "bachelor". 4 There are 10 clients. To simulate a non-iid data distribution scenario, we distribute the records of people with a PhD degree among the first three clients according to their age. The first client owns the data of young PhDs less than 38 years old, the second client owns the data of PhDs aging between 38 and 52 years old, and the third client owns the data of PhDs elder than 52 years old. The numbers of training samples for the first three clients are 126, 258 and 134, respectively. The rest of the data is uniformly distributed among the remaining clients. To show the dissimilarity between clients, the relative Euclidean distance between each client's local optimum model is evaluated (See Fig. 1a). We can observe that, due to our specific non-iid data distribution, the local models of the first three clients are quite far from the rest of the local models, which is reasonable as people with PhD degree are more likely to have a different salary prediction pattern. Performance To evaluate the performance of the decoded local model θ * c obtained from Algo. 3, we consider as a baseline the last model θc returned by the client c at the end of training (instead of the final global model θ). The last returned model is potentially more susceptible to attacks than the final global model, as it contains more personal information. For every attack scenario, 10 independent runs were conducted with different seeds.

Local Model

Acc c (θ c ) of client c (%) c Accc(θc) 5 steps θ c c=0 c=1 c=2 c=3 c=4
In Table 1, we show the average training accuracy of θc and θ * c over 10 runs on each client's local dataset, under LEAF synthetic data distribution. Note that larger training accuracy values suggest the model is more suited to the local dataset and it may then leak more personal information. As the number of local steps increases, the accuracy of the last returned model increases as the model has been obtained through more local updates. We can see from the last column that, on average, our attack outperforms the baseline with 10%-20% improvement. The performance of the local model reconstruction attack is almost insensitive to the number of local steps. Moreover, this attack is more effective on client 3, whose local dataset is probably very different from the others as suggested by the low accuracy of the model θc .

In Figure 1b, we show the performance of the mapping function G c when attacking one of the first three client c, under different batch size scenarios in FL for Adult dataset. Small batch size would introduce more randomness into the data set ∆M c . Thus, the mapping loss (Eq. 9) is higher for small batch size. Figure 1c shows that the decoded local model outperforms the baseline (dash line) for test accuracy as well.

Conclusion

In this paper, we initiate the study of a new attack for FL training: the adversary estimates a client's local/personalized model which may reveal private information and open the road to other classical modelbased attacks. In comparison to state-of-the-art attacks on the global model, our attack reduces the plausible deniability and does not suffer the problem of large batch size (on the contrary, it works better the larger the batch size). There is still space for the improvement of our local model reconstruction attack and it would be interesting to evaluate its performance on neural networks which is one of our future research directions.

5 :

 5 Server updates θ(t + 1) by aggregating the received updated local models. Client c ∈ C: // global model θ, local model θ c , local dataset D c 6: while FL training is not completed do 7:

2

 2

3. 1 Algorithm 2

 12 Exact model reconstruction for linear least squares regression in FedAvgHere we show the possibility to reconstruct the exact local model in polynomial time when training a least squares linear regression through FedAvg[START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF] with full batch size and arbitrary number of local steps. The local update rule of FedAvg is given in Algo. 2. The procedure for the exact reconstruction is shown in the proof of Observation 1. Client c's local update rule in FedAvg [1] Local Update c (θ, D c ) // θ: server model, D c : local dataset, B: batch size, E: the number of local epochs, η: learning rate. 1: θ c ← θ, B ← (split D c into batches of size B) 2: for each local epoch e from 1 to E do 3: for batch b ∈ B do 4: θ c ← θ c -η × g(θ c , b), where g(θ c , b) = 1 B x∈b ∇l(θ c , x) 5: Return θ c Observation 1. Consider training a least squares linear regression through FedAvg with full batch size and assume that a client's design matrix has rank d equal to the number of features. Once the client has communicated with the server d + 1 times, the adversary can recover the client's local optimal model in O(d 3 ) operations. Proof. Let X ∈ R m×d be the design matrix with rank d and y ∈ R m be the labels in the local dataset D c of the client c. Let m be the number of the local samples, i.e., m = |D c |. The local loss function of client c is:

Algorithm 3 2 : 9 ) 4 : 10 ) 5 : 2 (

 32941052 Local model reconstruction attack // Input: M c , the messages exchanged between client c and the server 1: ∆M c = {(θ, ∆θ = θ -θ c ), ∀(θ, θ c ) ∈ M c } Define a mapping function G c with parameters w ∈ R m , taking the server model θ ∈ R d as input and predicting the difference between server model and local model, i.e., G c : R m × R d → R d . 3: Estimate G c parameters, denoted by ŵ, by minimizing the empirical risk: min w∈R m (θ,∆θ)∈∆M c G c (w, θ) -∆θ 2 (Estimate the model θc , by minimizing the local update difference G c for fixed parameters ŵ: min θ∈R d G c ( ŵ, θ) 2 (Return θ * c as the estimator for the local model of client c b) Mapping loss vs batch size (c) Test accuracy vs batch size

Figure 1 :

 1 Figure 1: Adult, one local step and η = 0.001. Figs 1b and 1c show the mean and the 95% confidential interval over 10 runs.

Table 1 :

 1 Average train accuracy on client c's local dataset of the final personalized model of FedAvg θc and the decoded model θ * c over 10 independent runs. LEAF synthetic dataset with 5 clients, batch size 256 and learning rate 0.01.

	1	θc θ * c	53.9 49.7 85.1 28.3 75.8 67.0 74.3 80.6 77.9 91.0	58.6 78.1
	5	θc θ * c	60.1 54.6 87.6 33.6 79.2 65.6 72.9 76.9 72.5 86.2	63.0 74.8
	10	θc θ * c	69.4 60.4 90.6 42.3 83.9 67.5 79.5 78.1 75.8 88.9	69.3 78.0

These attacks aim to learn hidden sensitive attributes of a data instance for which non-sensitive attributes are known to the public.

In[START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF], the authors claim that their property attack can succeed even in presence of secure aggregation protocols, but the attack can detect when a certain property appears during training, not at at which client.

For every client c, its local model θc(t) can be expressed as θc(t) = θc(0) + span{∇Lc(θc(0)), ∇Lc(θc(1)), ..., ∇Lc(θc(t -1))}.

The number of the data points are reduced from 48842 to 12300.

Acknowledgements

This work has been supported by the French government, through the UCAJEDI and UCA DS4H Investments in the Future projects managed by the National Research Agency (ANR) with the reference number ANR-15-IDEX-0001 and ANR-17-EURE-0004.


Nicolas Bredeche
email: bredeche@lri.fr

Yann Chevaleyre
email: yann.chevaleyre@lamsade.dauphine.fr

The Robot Swarm Re-localization Problem

This paper tackles the problem of re-localization in a swarm of moving virtual robots where some robots might be lost and where the distance between each neighboring robot is known within a limited communication radius (e.g. using the strength of a radio/wifi signal), whereas the precise localization is not known. The basic process in relocalization relies in a robot swarm that re-aggregates based on local information only by recruiting lost robots so as to build a swarm configuration where localization is possible and non-ambiguous. The main issues in relocalization is to provide highly decentralised behaviors for ensuring efficient and fast re-aggregation of the swarm that is scale independent. In this paper, the problem of relocalization is defined as well as criteria for evaluating swarm relocalization efficiency. Moreover, a set of decentralized behaviors based on local reactive behaviors is presented and experimentally studied.

I. INTRODUCTION

The advantages of relying on a swarm of robots rather than on a single robot are clear for a wide range of applications, would it be because of the intrinsic reliability of distributed agents or because of the parrallel approach to solving problems. However, considering a swarm of robots also implies to deal with a network of robots that should be synchronised in a distributed fashion so as to achieve organism-level tasks.

A key feature of swarm formation is to rely on coordination and cooperation on the local scale, possibly considering limited communication and computation ability, with regards to an objective (e.g. pattern formation) specified on the global scale. Such approches have long been advocated since early works in this domain [START_REF] Bayindir | A review of studies in swarm robotics[END_REF] [START_REF] Dudek | A taxonomy for multiagent robotics[END_REF] for a wide range of applications ranging from flocking to patrolling and cooperation. While these early works were application-driven (flocking, coordination, transport, etc.), more recent works have been addressing higher level approaches that can provide a basis for targeted applications as well as useful information for higher level components such as Mapping algorithms. The originality of these recent works is to consider properties regarding swarm or multi-robot configuration and organization strategy from a graph theory perspectives.

In the scope of this paper, the problem of re-localization in a swarm of robots is addressed. Given a swarm of robots, the goal is to achieve a configuration of connected robots that makes possible non-ambiguous localization of each robot in the swarm, given the robot have limited computation and communication capabilities. This implies both building a decentralized coordinate system and localizing each of the robot with regards to a base reference in the context of robot using radio signal that can be emitted/received within a limited range. As proposed in recent works [START_REF] Moore | Robust Distributed Network Localization with Noisy Range Measurements[END_REF], swarm localization is reformulated as the construction of a specific sub-class of grounded graphs that ensures localizability (ie. a swarm configuration from which actual localization can be handled by a dedicated algorithm, e.g. [START_REF] Thomas | Revisiting trilateration for robot localization[END_REF]). The central contributions of this paper are [START_REF] Thomas | Revisiting trilateration for robot localization[END_REF] to define the problem of re-localization of a swarm of moving robots, ie. strategy for recruiting new "lost" robots into the swarm for further localization, (2) to define some relevant criteria for evaluating re-localization and (3) to provide a set of behaviors for ensuring re-localization based on local information that can be applied in a distributed fashion. As the problem of relocalization implies moving robots, issues such as swarm coverage of the environment as well as behavior issues for "lost" robots are carefully studied.

The next section gives some definition of the problem of localization as well as its formulation as a problem of localizability in grounded graph. Section 3 describes the approach towards re-localization, which is based on incrementally re-building a swarm configuration that is shown to belong to a restricted family of localizable grounded graph. This approach is experimentally studied as well as analysed and discussed in section 4. Finally the last section concludes and gives some perspectives.

II. PROBLEM SETTING AND RELATED WORKS

In the scope of robot swarms, the amount of reliable information available to each robot may be relatively limited. A typical example is that of using wifi or radio signals so as to localize neighboring robots, which makes it possible to perceive information within a given radius, with a monotonously decreasing signal power. This implies that information contained by the radio signal include both data exchange as well as distance information. However, radio signals have radial diffusion which prevent a robot to stricly localize its neighbors. As a consequence, localization with regards to neighbors must be the results of a triangulation process using incoming signals from at least three robots (in 2D). Localization through triangulation, or "trilateration", is a rather classic way of proceeding in the field of mobile sensor networks, would it be for localizing mobile phones in telecom networks or one-to-one mobile robots localization for environment coverage [START_REF] Gini | Robotic Swarm Dispersion Using Wireless Intensity Signals[END_REF]. However, specificities of robot swarms imply the distributed flavor of localization as well as a limited range of radio signals compared to the swarm size. This implies that localization must be possible accross the swarm thanks to some self-contained beacon, which refers to a limited number of robots (usually, 3 robots) whose relative positions and inter-connection makes it possible to act as a local base for localizing neighboring robots, and some kind of relays that enables localization of distant robots.

From the graph theory perspective, a swarm of robot with radio connections giving information about distances can be seen as a grounded graph, defined as follows:

Definition 1: A grounded graph [START_REF] Eren | Rigidity, Computation, and Randomization of Network Localization[END_REF] is a graph G(V, E) with edges labelled with d ij , such that each vertex represents a robot, and two vertices (i, j) in the graph are connected if the distance d ij between them is known.

Thus, given a set of robots connected together with radio links, such that two connected robots have the ability to estimate the distance between them, then a corresponding grounded graph can be build with robots as vertices and weighted edges as signal links with distance. Localizing the agents consists in computing a realization of this grounded graph:

Definition 2: A realization [START_REF] Hendrickson | Conditions for unique graph realizations[END_REF] of a grounded graph G is a function that maps vertices of G to points in the euclidian space, such that for each edge (i, j) of G, the euclidian distance between the two corresponding points is equal to d ij . A grounded graph is realizable if some realization exists. Moreover, G is said to be localizable iff all possible realizations are equal up to some translation, rotation, and reflection of the entire space.

Figure 1 illustrates grounded graphs that are, or not, localizable. The major problems are that of continuous deformations (case (b), the graph may be continuously deformed) and rigid deformations (case (a), the graph may flip from one realization to another. On the other hand, case (c) gives an example a localizable graph, which is formally defined as 3-connected and redundantly rigid [START_REF] Hendrickson | Conditions for unique graph realizations[END_REF]. A direct consequence of dealing with such localizable graphs is that it is possible to compute coordinates for each robot with regards to one another.

Although checking the localizability is known to be NPhard in general, under a few natural assumptions, a polynomial algorithm is known for this problem [START_REF] Hendrickson | Conditions for unique graph realizations[END_REF]. It can be observed that checking for localizability in the general case implies computation on the global scale since all the links between robots have to be considered to ensure complete check. Because of the intrinsic nature of swarms, this is of course a problem since one has to consider local computation and peer-to-peer communication, thus enforcing specific localizability and localization algorithms.

Even harder than checking localizability, the problem of computing the realization has been shown to be NP-hard even with strong restrictions on grounded graphs [START_REF] Eren | Rigidity, Computation, and Randomization of Network Localization[END_REF] and even in one-dimension [START_REF] Hendrickson | Conditions for unique graph realizations[END_REF]. As a consequence, many works have focused on defining simple sufficient (but not necessary) conditions under which localizability is ensured and computing this realization becomes tractable. Among such work, Eren et al. define trilateration [START_REF] Eren | Rigidity, Computation, and Randomization of Network Localization[END_REF] : Definition 3: A trilaterative ordering [START_REF] Eren | Rigidity, Computation, and Randomization of Network Localization[END_REF] of a grounded graph G(V, E) is an ordering of the vertices v 1 , . . . , v n such that the first three vertices are connected together, and that for all i ∈ 4 . . . n, v i is connected to at least 3 vertices appearing before v i in the ordering. Grounded graphs for which a trilaterative ordering exist are called trilateration graphs.

It was shown in [START_REF] Eren | Rigidity, Computation, and Randomization of Network Localization[END_REF] that trilateration graphs are localizable. Thus, once a trilaterative ordering has been found on some grounded graph, the two above problems are easily solved.

Note that in trilaterative orderings, the first four nodes form a quadrilateral (a set of four fully connected vertices). The key feature of such a "quad" is that it is the only pattern of 4 vertices that ensure localizability (cf. definition 2). This means that given a set of four interconnected reference robots -a quad -it is possible to localize all robots in a non-ambiguous fashion with regards to this reference robots (ie. an absolute coordinate system). Similarly, the approach presented in [START_REF] Moore | Robust Distributed Network Localization with Noisy Range Measurements[END_REF] addressed this issue by considering specific swarms of robots build through quadrilateration of each node. Their approach consist of two steps: firstly quads are grown locally on the graph and connected to each other only if two quads share three vertices (to ensure localizability), secondly, quad clusters are connected with one another through shared vertices, which may imply global message exchange and costly computation to trilaterate clusters among themselves (e.g. two clusters sharing three different vertices with each vertex being part of different quads involves long distance communication to solve the localization problem). Clearly, this two steps approach can be seen as building a trilaterative ordering. Thus, when this whole process succeeds, the graph is ensured to be localizable and the localization to be easily computable. As in most works focusing on the localization problem, the approach of [START_REF] Moore | Robust Distributed Network Localization with Noisy Range Measurements[END_REF] relies on the choice of a specific growing pattern (quads) growing on the grounded graph. This impacts the family of localizable grounded graphs one has to consider. As a consequence, it may exclude candidate graphs, or at least may imply costly computation to overcome exceptions which might be more or less frequent in the real world. Thus, in many cases in which the graph is localizable, this approach will not succeed in finding the realization.

This also has some impact regarding the problem of relocalization. Indeed, the problem of re-localization considers a swarm in a localization mode with moving robots and can be formalized as follows:

Definition 4: Let G be a grounded graph associated with set of robots. Given that G is not localizable, the relocalization problem consists in rearranging the swarm of robots in such a way that localizability is restored.

In this context, the key issues are to consider both localizability within clusters of inter-connected agents as well as a strategy regarding recruitment of robots having too few connections to be localizable. Figure 2 shows an example of swarm being re-localized.

Four major steps constitute re-localization: (1) choosing a basic node which will serve as a refence (possibly through automatic bidding process) ; (2) growing a non-ambiguous pattern as a basis for trilateration (3) extending this pattern to the neighborhood when trilateration is possible (4) recruiting new (possibly moving) robots that are near-by but cannot be directly trilaterated.

Re-localization is thus largely dependant on the localization strategy (constraints over the grounded graphs considered), which also implies the relation between swarm configuration and recruiting lost robots (ie. the wider the swarm coverage, the more chance to recruit new robot). In the following sections, some criteria are described to evaluate the efficiency of re-localization in the scope of considering swarm as grounded graph with trilaterative ordering as well as several behaviors that can be distributed among the swarm.

III. LOCALIZABILITY AND RE-LOCALIZATION

A. Criteria for Evaluating Relocalization

In order to evaluate to performance of relocalization algorithms, a set of evaluation criteria has to be devised. These criteria may encompass several, possibly conflicting, objectives which are to be selected depending on the task at hand. Firstly, the following terms are defined: let (x i , y i ) be the position of agent i at the beginning of the relocalization process, and (x i , y i ) be its position when relocalization is achieved. Next, a set of generic criteria is proposed:

• C0. Relocalization Speed: time elapsed until localizability is ensured. • C1. Agents Displacement: sum of the distances between each agent's position before and after relocalization, namely i distance ((x i , y i ), (x i , y i ) • C2. Agent with Maximal Displacement: max euclidian distance between each agents position before and after relocalization, namely max i distance ((x i , y i ), (x i , y i ) • C3. Agents Involvement: number of agents which will have to move to ensure localizability. • C4. Communication load: number of bits exchanged between agents during relocalization. • C5. Neighborhood co-linearity. Average value during relocalization of the following algorithm: for each agent, estimate to what extent connected neighbors are +/-colinears. This can be an important issue to localization as linear independence is required for ensuring localization. Underlined items are considered in the next experimental section -indeed, C0 and C1 are the most relevant straightforward criteria to optimize when it comes to relocalization. However, other criteria may be of interest depending on the context. As examples, C3 might be the most important one in the scope of rescue robots while C4 is particularly interesting in the context of low energy consumption (note that in this paper, it is not relevant as we consider behavior based on local information).

B. Generic Algorithms for Relocalization

The re-localization problem implies to consider three classes of agents depending on their respective situation regarding localizability, and are defined as follow:

• LOC -Localized agents: A cluster of agents for which a trilaterative ordering has been computed. As a consequence, LOC agents can be localized relatively to each other. Clearly, count(LOC neighbors ) ≥ 3, with LOC neighbors the set of all LOC agents connected to the current agent).

• CNL -Connected but Not Localized agents: agents that are connected to at least one LOC agent, and at most two LOC agents. ie. their aren't enough edges towards the cluster of LOC agents to allow CNL agents to compute their relative position (ie. count(LOC neighbors ) ∈ {1, 2}). • NC -Not Connected agents: NC agents may have neighbors, but none of them are LOC agents. Ie. NC agents have strictly no information concerning their position (ie. count(LOC neighbors ) = 0). Broadly, this means that LOC agents are part of a "localizable cluster" while CNL and NC agents are considered as two kinds of "lost agents". These classes of agents also differs by the relocalization behavior used so as to reach global swarm localizability. As a consequence a class of behaviors is defined for each class of agents in order to described the type of behaviors used to address re-localization. Namely, the following classes of behaviors are defined: LOC-behaviors, CNL-behaviors and NC-behaviors. Thus, the basic algorithm for relocalization, "relocalization algorithm", is distributed on each agent and is summarized as follow:

• If LOC-agent Then • call-LOC-behavior • Else • If CNL-agent Then • call-CNL-behavior • Else • call-NC-behavior • End If • End If
At the beginning of the re-localization process, as no trilaterative ordering has been computed, the LOC class does not contain any agent. Thus, it now remains to describe how to bootstrap the relocalization by selecting the first three LOC agents from which the whole localizable cluster can be incrementally built. As shown in the previous section, constructing a trilaterative ordering on a grounded graph suffices to solve the localization problem, when this construction is possible. The "incremental trilateration bootstrap algorithm" is described as follow: Let LOC-agent source be a robot defined as the unique starting point to grow the localizable swarm (see below). For any robot in the swarm that is both directly connected to LOC-agent source and not yet a LOC-agent itself (ie. this is a CNL-agent), check with each neighboring robots (with the exception of LOCagent source ) if it is also connected with LOC-agent source -if checking succeeds, then agent state switches to LOC-agent. To sum it up, this means that each possible candidates for boostraping localization simply check if they can take part in a group of three inter-connected robots, one of them being the LOC-agent source . Afterwards, the algorithm described previously makes it possible to relocalize the whole swarm through incrementally building a trilaterative ordering.

The selection of a specific robot as LOC-agent source can be performed through various process, some of which are given as examples here: ad hoc selection of a reference robot, bidding process between all robots prior to deployment, human-triggered when relocalization is needed (e.g. a human supervisor following the robots equipped with a short range emitter), etc. The last example is of particular interest as human supervision in the context of a swarm of robots also face the problem of highly distributed agents over a terrain and may need to trigger flocking and relocalization behavior to centralize and gather important data -this is a typical example of exploration of indoor environment after natural disasters where such a property of relocalization from a robot selected on the fly is needed.

Note that ensuring localizability is very different from computing localization: maintaining localizable swarm implies only local maintenance of connectivity between robots (ie. avoid breaking links with the neighborhood) while localization itself implies synchronization and message exchange of all individuals in the swarm as the coordinate system is highly dependant of swarm relative position and movement. In a real world experiment, localization, which implies costly communication, may be performed from time to time when necessary while localizability, which implies very few (and only local) messaging, must be ensured any time.

C. Agent Behaviors for Relocalization

As stated before, the goal of NC agents is to find CNL/LOC agents so as to connect to the localizable group of robots. Having no information whatsoever, they must explore their environment. When encountering other NC agents, they might exchange information about where to go/not to go. In the following, several candidate behaviors are described for each the agent class.

1) NC behaviors:

• RE. Random forward exploration. The agent moves forward and rotates around itself with small random angle. • BOIDS. Agent follows the boids algorithm as described in [START_REF] Reynolds | Herds and Schools: A Distributed Behavioural Model[END_REF], and tend to aggregate while exploring the environment.

2) CNL behaviors:

• RE. Random forward exploration (same as before).

• CLOSER-MAXLOC. The agent gets closer to the LOC agent of maximal degree.

3) LOC behaviors:

• STATIC. Agent does not move.

• COVER. The agent gets away from closest LOC agent if closer than a given pre-defined threshold distance.

With this behavior, LOC agents tend to spread out. Each of these behaviors are reactive behaviors that rely solely on local information, implying minimal (ie. zero) communication accross the swarm.

IV. EXPERIMENTS AND DISCUSSION

In this section, a set of experiments implying several combinations of aforementionned behaviors were tested in different setups. All experiments were run using the NetLogo framework, which has long been considered as a major development platforms for simulating robot swarms [START_REF] Railsback | Agent-based Simulation Platforms: Review and Development Recommendations[END_REF]. The environment is defined as a (continuous) square area of size 100 × 100 with wrapping enabled (ie. no border). In all experiments, 100 agents were randomly placed on the area. Each agent is connected to all agents within a radius of either 6, 9 or 12. In order to evaluate the average performance for all settings, all experiments are performed over 80 runs so as to provide smooth results. As stated in the previous section, several combination of behaviors are put to the test so as to provide 8 differents behavior combinations (LOC: Static or Cover, CNL: RE or CLOSER-MAXLOC, NC: RE or BOIDS). Given the three possible radii, this means that 24 distinct experimental setups are defined. Figure 3 shows a typical swarm relocalization process through time, ie. from the initial swarm configuration with many lost robots until a fully localizable swarm.

Results for all experiments are presented in table I using two generic criteria: C0 (time taken to complete relocalization) and C1 (sum of agent displacements). Random exploration behaviors, both for CNL and NC robots, produce the worst results, whatever the LOC robot behavior used. This is not really a surprise as these setups are considered as the baseline approach due to its simplicity. Then, it can observed that both CNL "CLOSER-MAXLOC" and NC "BOIDS" behaviors separately improve results on C0 as the perception radius of robots grows. Indeed, using CNL "CLOSER-MAXLOC" tends to lead to even better results as the radius grows, which may vote in favor of the crucial importance of an efficient behavior on the edge of relocalizability. Then, combining both behaviors leads to the best results observed, whatever the LOC behavior considered. Interestingly enough, C0 and C1 are strongly correlated, with the notable exception when using a small radius and the CNL "CLOSER-MAXLOC" behavior (C1 is worse than expected compared to other experiments and the current C0 value). On the other hand, the LOC "COVER" behavior have a more or less important negative impact, which is mainly due to deadlock situations because of limitations of coverage algorithms where each LOC agents must remain connected to all its LOC neighbors (ie. agents get stuck in a situation were they cannot move anymore).

The take home message from these experiments is that relocalization seems to depend first on accurate CNL behaviors, for which there exists some local information that can be efficiently exploited, and then on NC behaviors, for which few information is available.

V. CONCLUSIONS AND PERSPECTIVES

In this paper, we introduced the problem of re-localization, which extends the localization task to moving, possibly lost, agents. The motivation behind relocalization is to provide an efficient algorithm to ensure swarm localizability, ie. the fact that a localization algorithm provide a unique non ambiguous position for each of the robot in the swarm with regards to the whole swarm. The major contributions of this paper are to provide a formal definition of the relocalization problem as well as proposing a set of evaluation criteria and a methodology towards defining a relocalization strategy. Moreover, a set of local behaviors addressing relocalization are presented. These behaviors are designed so as to be distributed over the robots in a swam. An experimental study as well as an in-depth analysis is provided. The major advantage of these behaviors is to require very low bandwidth by using only local information.

Relocalization is a key feature in swarm robotics, as it addresses the problem of dynamically recovering a swarm configuration where localization algorithms may be used. Moreover, many open questions are raised in this paper, some of which are listed below:

• Currently, behaviors based on local interaction have been used. However, there might be a trade-off between bandwidth consumption and relocalization efficiency. For example, the class of gossip behaviors described previously may enable lost robots to avoid already explored areas.

• Noisy measures regarding distance to neighbors impact the spatial distribution of robots. This is also a problem in the scope of the localization problem where connected, but aligned, robots fail to provide a reliable basis for localizing other robots. This problem has already been addressed to some extent for localization, for example in [START_REF] Moore | Robust Distributed Network Localization with Noisy Range Measurements[END_REF], and could provide a starting point for designing noisy re-localization algorithms. Moreover, the reality gap between experiments in simulation and actual implementation on real robots should definitely be addressed in further works. • Re-localization may be stated as an optimization problem -which imply designing the optimization criteria to be used. Indeed, criteria defined in this paper provide a starting point, yet far from complete. • More formally, efficient centralized algorithm for solving re-localization should be studied so as to provide a basis comparaison for distributed algorithms. In a similar fashion, the computational complexity of relocalization should be carefully studied.

Fig. 1 .

 1 Fig. 1. Three grounded graphs. (a) and (b) are not localizable, whereas (c) is.

Fig. 2 .

 2 Fig. 2. A swarm before and after re-localization. (left) Swarm partially localized. The agent at the bottom-right corner has a single neighbor, which is not sufficient for him to compute its position by triangulation. (right) After re-localization process, the swarm has rearranged itself: agent at the bottom-right has moved closer to the cluster, thereby connecting itself to three agents. Clearly, the swarm is now trilateralizable.

Fig. 3 .

 3 Fig. 3. Swarm relocalization through time (from upper-left to bottom-right) with RE behaviors for NC and CNL robots and STATIC behavior for LOC robots. Both robots and comunication links between robots are shown in this figure. The resulting configuration holds the desired unique realization property.

TABLE I EXPERIMENTS

 I WITH DIFFERENT BEHAVIORS FOR NC, CNL AND LOC ROBOTS USING A PERCEPTION RADIUS OF EITHER 6, 9 OR 12. EVALUATION OF RELOCALIZATION USING C0 AND C1 CRITERIA. FOR EACH EXPERIMENTS, AVERAGE VALUE OVER 80 RUNS AND STANDARD DEVIATION IS PROVIDED. BEST RESULTS FOR EACH RADIUS SIZE AND CRITERIA IS IN BOLD FONT. WORST RESULTS ARE MARKED WITH ITALIC FONT.