Jean Colombani
email: jean.colombani@lpmcn.univ-lyon1.fr

Jacques Bert

Toward a complete description of nucleation and growth in liquid-liquid phase separation Short title : Nucleation and growth in liquids

published or not. The documents may come

Toward a complete description of nucleation and growth

in liquid-liquid phase separation

Introduction

In binary liquid mixtures exhibiting a miscibility gap, the two components experience an effective repulsive interaction. At high temperature, this repulsion is overwhelmed by thermal stirring and the system is monophasic. Under a composition-dependent temperature (the binodal line, delimiting the miscibility gap), the entropic mixing is dominated by the chemical repulsion and the liquid separates in two phases. This liquid-liquid phase separation gives the opportunity to observe the pathway of a system evolving from a nonequilibrium or metastable state toward a stable equilibrium state. Indeed when quenching the mixture from the one-phase region inside the two-phases domain, the homogeneous phase abruptly reaches:

• either a nonequilibrium state, when quenched inside the spinodal line. The phase separation mechanism is here spinodal decomposition, which is now quite understood.

• or a metastable equilibrium state, when quenched between the spinodal and binodal lines. The phase-separation process is then nucleation and growth. If the behaviour of the early and late stages of the growth are now well established, the intermediate stage still presents open questions that we plan to study in this work.

Unlike the case of spinodal decomposition where measurements of the evolution of the growing domain size exist over at least 7 decades of time [START_REF] Perrot | Nucleation and growth of tightly packed droplets in fluids[END_REF], measurements of the radius R of the growing droplets of the minority phase after nucleation are available only over narrower windows of time, as pointed in [START_REF] Sagui | Nucleation and growth: Decay of a metastable state[END_REF]. Nevertheless, the collection of the literature results enables to get a view of the successive processes and corresponding growth laws:

• After a generally heterogeneous nucleation [START_REF] Buil | Nucleation and early stage growth in phaseseparating liquid mixtures under weak time-dependent supersaturation[END_REF], the droplets grow with a R ∼ t

1 2
law [START_REF] Cumming | Light-scattering experiments on phase-separation dynamics in binary fluid mixtures[END_REF]. This evolution corresponds to a "free growth" where the solute migrates through the bulk phase by molecular diffusion toward the nuclei [START_REF] Langer | Kinetics of nucleation in near-critical fluids[END_REF].

• An intermediate regime of slower growth is subsequently achieved when the solutedepleted layers around the nuclei start to overlap and when the interfaces between the two phases become progressively sharp. The growth law during this stage and its domain of existence is still a matter of investigation [START_REF] Tokuyama | Dynamics of crossover phenomenon in phase separating systems[END_REF].

• Afterward, the equilibrium order parameter, i.e., the final volume fraction of the minority phase, equal to the initial supersaturation Φ, is attained and the coarsening proceeds through the diffusion of this order parameter via two possible mechanisms : either Ostwald ripening (small nuclei evaporate and condensate onto large ones) [START_REF] Lifschitz | The kinetics of precipitation from supersaturated solid solutions[END_REF] or coalescence induced by Brownian collisions [START_REF] Siggia | Late stages of spinodal decomposition in binary mixtures[END_REF]. Both processes lead to a reduction of the total interface and to a R ∼ t • Finally, when the gravitational effects dominate, a macroscopic sharing of the two phases occurs by sedimentation.

In order to evaluate the growth exponent and the range of existence of the abovementionned intermediate regime, we have used a sedimentation-based indirect method which has given us access to the radius evolution of the droplets over several decades of time.

Experiments

Our procedure is the following. We have quenched off-critical mixtures of water-isobutyric acid (showing a consolute critical point at T c = 27.05 • C) below the binodal line. We have then studied the nucleation, growth and sedimentation in the experimental cell with a light attenuation technique, sketched in figure 1. Figure 2 displays the evolution of the light attenuation curves (transmitted light intensity over incident light intensity) along a vertical axis in the cell as a function of time. Initially the curve is a horizontal line of strong attenuation, which originates in the scattering of light by the rapidly moving nucleating and growing droplets of submicrometer size. When sedimentation sets in, a droplet-free clarification zone appears and expands at the top of the liquid due to the average settling motion of all the droplets. This can be observed in the curves by a steep increase just preceding the plateau: the number density of droplets starts to decrease at the top, so the light scattering diminishes at this point. The bulk droplet-rich liquid and the clarification zone are separated by the sedimentation front, which broadens with time owing to the droplets Brownian diffusion (see figure 3).

We now focus on the onset of sedimentation at time t s . The Péclet number Pe is the ratio of the buoyant velocity v of a droplet to its diffusive velocity D/R: Pe= vR/D (D droplet diffusivity). When the former sufficiently exceeds the latter, at t s , the droplet begins to settle down. We will tentatively consider that this occurs when the gravity effect overwhelms the diffusive effect by one order of magnitude, i.e., for Pe s = 10. The position of the first droplets experiencing Pe=Pe s , i.e., the first sedimenting droplets, can be traced in figure 2 through the early evolution of z s . The point z s is the intercept of the increasing curve with the plateau. In other words, z s represents the position of the lower sedimentation front (cf. figure 3) and its motion just at t s reflects the settling of the droplets experiencing Pe=Pe s . The velocity of these droplets is v s = (dz s /dt) t=ts . Their diffusion coefficient is evaluated through a Stokes-Einstein law : D s = k B T /(5πηR s ) (η viscosity of the majority phase). Therefore the radius of the droplets at the beginning of sedimentation t s , calculated in introducing the above-mentionned expressions in Pe s = v s R s /D s = 10, is:

R s = 2k B T πη (dz s /dt) t=ts 1 2
.

(

It should be noticed that the droplets at t s are at the end of the "weightless" regime of growth and just enter the sedimentation-influenced growth. Consequently, their radius at this time derives only from the sedimentation-free coarsening regimes that they have experienced until this point (diffusive growth, Ostwald ripening, . . . ) [START_REF] Colombani | Early sedimentation and crossover kinetics in an off-critical phase-separating liquid mixture[END_REF].

To allow comparison with literature results, renormalized values are needed. The reference size in nucleation and growth mechanisms is the radius of the critical nucleus (for which the bulk free energy gain exactly compensates the surface free energy loss) R c = α/Φ with α a capillary length evaluated as ξ -/3 (ξ -is the concentration fluctuations correlation length) [START_REF] Langer | Kinetics of nucleation in near-critical fluids[END_REF]. The reference time is the relaxation time of this critical nucleus t c = R 2 c /(D -Φ) (D -solute diffusivity) [START_REF] Langer | Kinetics of nucleation in near-critical fluids[END_REF].

Results

We have then plotted in figure 4 [τ = t s /t c , ρ = R s /R c ] points for experiments of quench depths δT ranging from 0.03 to 0.50 K and initial supersaturation Φ ranging from 0.3 to 5.9 % vol . We note that all these experiments build a universal coarsening behaviour with a crossover time τ CO ≃ 1 × 10 3 between two growth exponents: 0.15 followed by 0.36 ≃ 1/3. The latter obviously corresponds to the interface-reduction coarsening, but the experimental dispersion has not enabled to discriminate between Brownian coalescence and Ostwald ripening [START_REF] Colombani | Early sedimentation and crossover kinetics in an off-critical phase-separating liquid mixture[END_REF]. It follows that the former characterizes the intermediate regime and that τ CO shares the end of the intermediate regime and the beginning of the conserved order-parameter coarsening.

To check the consistency of this interpretation with known results, the (τ , ρ) curves of the major theoretical and experimental studies in the literature for very off-critical liquid mixtures, i.e., Φ ≤ 6%, have been added in figure 4. The discrepancies between these results reveal incoherence so a critical survey is needed. Of the pioneering work of Wong and Knobler, only the most off-critical quenches have been drawn [START_REF] Wong | Light-scattering studies of phase separation in isobutyric acid + water mixtures: Hydrodynamic effects[END_REF]. A crossover dynamics was not expected at this time, the experimental curves are bent and growth exponents are difficult to evaluate. The quench numbered L of another study of Wong and Knobler [START_REF] Wong | Light scattering studies of phase separation in isobutyric acid + water mixtures[END_REF], reanalysed by Siebert and Knobler [START_REF] Siebert | Analysis of light-scattering measurements near a cloud point[END_REF], corresponds to a supersaturation Φ = 4.2 % and has accordingly been drawn. Their values take place at the end of the diffusive growth and the beginnning of the intermediate regime. For this part of their curve, the authors indicate a growth exponent of 0.18, which is fairly close to ours (0.15). The outstanding results of Buil et al. obtained by an original optical method for Φ = 2.6 % give access to the very beginning of the phase separation, including the nucleation and early free growth, and have been added [START_REF] Buil | Early stage kinetics of phase-separating liquid mixtures[END_REF]. The results of Cumming et al., also displayed, show the t 1/2 coarsening law unexpectedly elapsing far beyond τ CO [START_REF] Cumming | Light-scattering experiments on phase-separation dynamics in binary fluid mixtures[END_REF]. This feature can be a consequence either of a specific kinetic behaviour of the polymer blends used by these authors or more likely of the difficulty to compute renormalized quantities in macromolecular liquids comparable to those of simpler systems (cf. a discussion of this point in [START_REF] Lalaude | Scaled growth of an isolated droplet generated by laser-induced phase separation in a microemulsion -Comparison with systems of the same Ising class[END_REF]). Baumberger et al. also find a free growth regime for 2 % < Φ < 4 % -with an exponent 0.6-beyond τ CO despite their use of exactly the same system as ours [START_REF] Baumberger | Kinetics of nucleation and growth in a near-critical mixture at rest and under a shear flow[END_REF]. We have evaluated the Péclet number of their droplets for the studied dimensionless times and we have found P e ranging between 50 and 1000. Therefore their experiments should have been performed during the sedimentation regime, which could explain their high growth exponent. Finally, Tokuyama and Enomoto have made a systematic model of the phase separation dynamics after heterogeneous nucleation, to predict the coarsening laws in the three regimes, in particular for Φ = 1% [START_REF] Tokuyama | Dynamics of crossover phenomenon in phase separating systems[END_REF]. Their intermediate regime exponent (1/4) is slightly larger than our experimental one (0.15) but their crossover time τ CO ≃ 2 × 10 3 lies in agreement with ours (1 × 10 3 ). As they concern only homogeneous nucleation, the ρ(τ ) curves of the model of Sagui et al. were not included [START_REF] Sagui | Nucleation and growth: Decay of a metastable state[END_REF] .

Conclusion

By collecting the main literature results and completing them with an indirect method based on the light attenuation observation of early sedimentation, we have achieved a coherent universal description of growth in phase-separating binary liquid mixtures of low supersaturation. Some minor questions remain, like for instance the exact respective domains of existence of Ostwald ripening and Brownian coalescence as a function of time and supersaturation. Besides, the field of phase separation in complex systems presents still appealing problems, like for instance the interplay between phase separation, aggregation and conformational changes in macromolecular solutions, which show wide applications in life sciences [START_REF] Manno | Multiple interactions between molecular and supramolecular ordering[END_REF].

List of Figures

1

  Figure 1:

  Figure 3:

Figure 4 :

 4 Figure 4:


Sara Brofferio

Bruno Schapira

POISSON BOUNDARY OF GL d (Q)

We construct the Poisson boundary for a random walk supported by the general linear group on the rational numbers as the product of flag manifolds over the p-adic fields. To this purpose, we prove a law of large numbers using the Oseledets' multiplicative ergodic theorem. The only assumption we need is some moment condition on the measure governing the jumps of the random walk, but no irreducibility hypothesis is made.

Introduction

The Poisson boundary of a group endowed with some measure µ, describes the asymptotic behavior of the random walk with step law µ. In the same time it gives a representation of bounded harmonic functions (see for instance [START_REF] Furman | Random walks on groups and random transformations[END_REF] for a survey on this topic). There are now many results on Poisson boundary of groups of matrices (see for instance [START_REF] Azencott | Espaces de Poisson des groupes localement compacts[END_REF][START_REF] Furstenberg | A Poisson formula for semi-simple Lie groups[END_REF][START_REF] Guivarc | Frontière de Furstenberg, proprétés de contraction et thórèmes de convergence[END_REF][START_REF] Kaimanovich | The Poisson formula for groups with hyperbolic properties[END_REF][START_REF] Kaimanovich | Random walks on discrete groups: boundary and entropy[END_REF][START_REF] Ledrappier | Poisson boundaries of discrete groups of matrices[END_REF][START_REF] Raugi | Fonctions harmoniques sur les groupes localement compacts à base dénombrable[END_REF] for some of the main results in this field, and [START_REF] Bougerol | Products of random matrices with applications to Schrödinger operators[END_REF][START_REF] Furstenberg | Boundary theory and stochastic processes on homogeneous spaces[END_REF] for some surveys).

Here we consider more specifically groups of matrices with rational coefficients, which were already considered in our previous works [START_REF] Brofferio | The Poisson Boundary of random rational affinities[END_REF][START_REF] Br | The Poisson boundary of triangular matrices in a number field, to appear[END_REF] for subgroups of triangular matrices. The novelty in the rational case, in comparison with standard results on real matrices, is that to describe the Poisson boundary, one has now to consider all possible embeddings of the rational field in the p-adic fields, and the Poisson boundary is then a product of "local parts", one for each prime number p (see Theorem 1.1 below for a precise statement of our result). This phenomenon was already observed in [START_REF] Kaimanovich | Poisson boundaries of random walks on discrete solvable groups, Probability measures on groups[END_REF] for the group of affine transformations with dyadic coefficients, and is very similar to some result proved in [START_REF] Bader | Factor and normal subgroup theorems for lattices in products of groups[END_REF] in an adelic setting. It should be noticed also that we do not need any hypothesis on the support of the measure µ.

Denote by P * the set of prime numbers and let P = P * ∪ {∞}. For p ∈ P * , denote by Q p the field of p-adic numbers, and set by convention

Q ∞ = R.
If µ is a probability measure on GL d (Q p ) with finite logarithmic moment, i.e. where µ * n denotes the n-fold convolution of µ and ∧ the exterior product. Denote by P p the parabolic subgroup of GL d (Q p ) consisting of matrices (p i,j ) with p i,j = 0, when λ i (p) < λ j (p), and let B p := GL d (Q p )/P p be the associated flag manifold. The main result of this paper is the following:

Theorem 1.1. Let µ be a probability measure on GL d (Q) such that p∈P ln + ||g|| p + ln + ||g -1 || p dµ(g) < +∞.
Then there exists a unique probability measure ν on the space

B := p∈P B p , such that (B, ν) is the Poisson boundary of (GL d (Q), µ).
This theorem unifies and generalizes several results on Poisson boundary of rational matrices groups, known up to now. In particular, it has been proved separately by F. Ledrappier [START_REF] Ledrappier | Poisson boundaries of discrete groups of matrices[END_REF] and V. Kaimanovich [12] that the Poisson boundary of a random walk supported by SL d (Z) is the real flag manifold B ∞ . This results is contained in Theorem 1.1 because, in this case, for all p = ∞, the associated Lyapunov exponents are all equal to zero, thus B p is trivial. Furthermore since Theorem 1.1 does not require any irreducibility condition, it also applies to the case of rational affine group and to rational triangular matrices previously threaded by the authors [START_REF] Brofferio | The Poisson Boundary of random rational affinities[END_REF][START_REF] Br | The Poisson boundary of triangular matrices in a number field, to appear[END_REF].

We would like to remark that for general number fields (i.e. finite extensions of Q) a similar result can be proved by adapting our methods (see in [START_REF] Br | The Poisson boundary of triangular matrices in a number field, to appear[END_REF] hints to possible generalization).

Due to its generality, our result does not say much about ν and its support. In particular it is not true that the restriction of ν to each B p has always full support. For instance if µ is supported on the subgroup of upper triangular matrices, we know [START_REF] Brofferio | The Poisson Boundary of random rational affinities[END_REF][START_REF] Br | The Poisson boundary of triangular matrices in a number field, to appear[END_REF] that ν charges only one Bruhat cell of each B p . But even this is not optimal since µ could be supported on diagonal matrices and with all Lyapunov exponents distinct, but in this case the Poisson boundary would be trivial (one point). However irreducibility hypothesis can give information on the support of µ. We have for instance the following triviality criterion:

Corollary 1.1. Let p ∈ P. If λ 1 (p) = λ d (p), then the projection of ν on B p is trivial.
Conversely, if the projection of ν on B p is trivial and no proper subspace of

Q d p is fixed by the support of µ, then λ 1 (p) = λ d (p).
There exists several results in the literature to decide whether the real Lyapunov exponents are all equal λ 1 (∞) = λ d (∞). For instance, under irreducibility hypothesis this is equivalent to ask that the closed subgroup generated by µ in GL d (R) is amenable [START_REF] Guivarc | Théorèmes quotients pour les marches aléatoires[END_REF]. For other references and results on product of real random matrices, see also [START_REF] Bougerol | Products of random matrices with applications to Schrödinger operators[END_REF]. It seem very likely that similar results hold on p-adic setting.

A different question that is still open is to understand the behavior of the measure ν on the product of the p-flag manifolds, and not only of its projection on each B p . For instance: does ν charge the whole product or is it supported by some "diagonal" sub-set? Is there some sort of correlation among the different p-adic components?

The main tool of the proof of Theorem 1.1 is to produce, using the multiplicative ergodic theorem of Oseledets, a law of large numbers for random walks on GL d (Q p ) (not necessarily with rational coefficients, see Proposition 3.1). Notice that such result on GL d (R) or on the affine group over Q p was already known (see [START_REF] Kaimanovich | Lyapunov exponents, symmetric spaces and a multiplicative ergodic theorem for semisimple Lie groups[END_REF] and [START_REF] Cartwright | Random walks on the affine group of local fields and of homogeneous trees[END_REF] respectively). The Lyapunov exponents give the speeds of convergence and the boundary limit of the random walk on B p the directions. This is done in Section 3, where we also use this result to prove that B p and B are µ-boundaries.

In Section 4, we use entropy criterion due to Kaimanovich to establish the maximality of (B, ν) and prove the main theorem and its corollary.

We notice that our strategy is very similar in spirit to that used by Karlsson and Margulis in [START_REF] Karlsson | A multiplicative ergodic theorem and nonpositively curved spaces[END_REF] in a slightly different setting. But here the proof is more direct, since we can use Oseledets theorem, and we do not need to identify the Poisson boundary with the geometric boundary of some non-positively curved metric space.

The authors would like to thank Uri Bader for suggesting them the problem. They are also grateful to François Ledrappier and Anders Karlsson for useful advices and references.

Preliminaries

2.1. General linear group over Q p . If K is a field, we denote by GL d (K) the group of invertible matrices of size d with coefficients in K. We denote by e the identity matrix.

For

p ∈ P and v = (v 1 , . . . , v d ) ∈ Q d p , we set |v| p = max i |v i | p , if p = ∞ and |v| ∞ = i |v i | 2 ∞ ,
and if g ∈ GL d (Q p ) we set

||g|| p = sup |v|p=1 |gv| p .
For any p ∈ P and g, h

∈ GL d (Q p ) set d p (g, h) = ln + ||g -1 h|| p + ln + ||h -1 g|| p ,
where ln + denotes the positive part of the function ln. It is easily checked that d p is symmetric and satisfies the triangular inequality. It is not a distance since the set of

g ∈ GL d (Q p ) such that d p (e, g) = 0 is the compact subgroup of linear isometries of Q d p . Furthermore d p is left-invariant: d p (γg, γh) = d p (g, h), for all g, h, γ ∈ GL d (Q p ). For all g, h ∈ GL d (Q), let d(g, h) = p∈P d p (g, h).
This define a left-invariant pseudometric on GL d (Q).

2.2. The flag manifold. For each p ∈ P fix the sequence of Lyapunov exponents

λ 1 (p) ≥ • • • ≥ λ d (p).
The associated parabolic sub-group is

P p = {(p i,j ) ∈ GL d (Q p ) | p i,j = 0 if λ i (p) < λ j (p)} .
The flag manifold

B p := GL d (Q p )/P p is then a compact separable GL d (Q p )-space.
We mention that there is a one to one map between B p and the space of flags, viewed as the set of imbedded sequences of sub-spaces of Q d p of fixed dimensions. In fact

B p = (V 1 , . . . , V r ) | V 1 ≤ • • • ≤ V r = Q d p , dim(V i ) = j i ∀i ≤ r
, where r is the number of distinct values taken by λ 1 (p), . . . , λ d (p), and j 1 , . . . , j r are defined inductively by j r = d and

j i-1 = max{j < j i | λ j (p) > λ ji (p)}, for 2 ≤ i ≤ r.
To see the correspondence between B p and this space of flags, observe that GL d (Q p ) acts transitively on the flags and that the parabolic subgroup P p is the stabilizer of the element (E 1 , . . . , E r ), where for all i, E i is the vector space generated by the first j i vectors of the canonical basis.

Let

B := p∈P B p ,
equipped with the product topology. With the natural diagonal action, B is a compact separable GL d (Q)-space.

2.3. Random walk and µ-boundaries. Let µ be a probability measure on a locally compact separable group G. Let (Ω, P) := (G, µ) ⊗N , be the product of N independent copies of (G, µ) (here N is the set of strictly positive integers). If w = (w i , i ≥ 1) ∈ Ω, the random walk is the process defined by

x n := w 1 . . . w n ∀n ≥ 1 and x 0 := e. Observe that under P, for any fixed n, the law of x n is µ * n , the n-th convolution power of µ.

Assume that B is a compact separable space, endowed with a probability measure ν and a continuous action of G. We say that ν is µ-stationary (also known as µinvariant or µ-harmonic), if

µ * ν := G (gν) dµ(g) = ν,
where for all g ∈ G, gν is defined by

gν(f ) = B f (gz) dν(z),
for all continuous functions f . In this case, according to Furstenberg [START_REF] Furstenberg | A Poisson formula for semi-simple Lie groups[END_REF][START_REF] Furstenberg | Boundary theory and stochastic processes on homogeneous spaces[END_REF], we say that (B, ν) is a µ-boundary if, P-almost surely x n ν converges weakly to a Dirac measure.

A µ-boundary (B, ν) is naturally associated to a measurable function b = b B : Ω → B defined by [START_REF] Azencott | Espaces de Poisson des groupes localement compacts[END_REF] lim

n→+∞ x n ν = δ b(w) .
Then ν is the image of P under b.

Denote by θ the shift transformation on Ω: if w = (w i , i ≥ 1) ∈ Ω, then

(θw) i = w i+1 i ≥ 1.
The measure P is θ-invariant and it is easy to see that the function defined in (1) satisfies w 1 b(θw) = b(w). This property characterizes functions that arise from µ-boundaries, as follows from this known result (see for instance [START_REF] Kaimanovich | The Poisson formula for groups with hyperbolic properties[END_REF][START_REF] Ledrappier | Poisson boundaries of discrete groups of matrices[END_REF]): Proposition 2.1. Let B be a compact separable G-space and let b : Ω → B be a measurable map, such that P-a.s. we have w 1 b(θw) = b(w). Let ν be the law of b. Then (B, ν) is a µ-boundary.

Proof. We give here a proof for sake of completeness. By using the invariance of P by θ and the hypothesis on the map b we get for every continuous functions

f on B ν(f ) = Ω f (b(w)) dP(w) = Ω f (w 1 b(θw)) dP(w) = G Ω f (w 1 b(w ′ )) dP(w ′ ) dµ(w 1 ) = µ * ν(f ),
proving that ν is µ-stationary. The hypothesis on b also shows that for any continuous function f , the sequence

M n (w) := x n • ν(f ) n ≥ 1,
is a bounded martingale. Thus this sequence converges a.s and in L 1 toward some limit, say ν w ∞ (f ). Since B is separable, this defines actually a random measure ν w ∞ on B, which is the weak limit of x n • ν, n ≥ 1. Observe now that for all k ≥ 1,

ν w ∞ = x k ν θ k w ∞ P -a.s. Moreover E[ν w ∞ ] = ν.
Observe also that the Dirac measure δ b(w) has the same properties. As a consequence for any k ≥ 1, any Borel subsets O 1 , . . . , O k ⊂ G and U ⊂ B,

Pν w ∞ [O 1 × • • • × O k × U ] = Ω ν w ∞ (U )1(w 1 ∈ O 1 , . . . , w k ∈ O k ) dP(w) = Ω w 1 . . . w k ν θ k w ∞ (U )1(w 1 ∈ O 1 , . . . , w k ∈ O k ) dP(w) = Ω ν((w 1 . . . w k ) -1 U )1(w 1 ∈ O 1 , . . . , w k ∈ O k ) dP(w).
For the same reason

Pδ b(w) [O 1 × • • • × O k × U ] = Ω ν((w 1 . . . w k ) -1 U )1(w 1 ∈ O 1 , . . . , w k ∈ O k ) dP(w).
Thus the two measures Pν w ∞ and Pδ b(w) defined on Ω × B coincide on F k := σ(w 1 , . . . , w k ) ∨ B, for all k ≥ 1, where B denotes the Borel sets of B. Since the filtration (F k ) k≥0 generates the σ-algebra of Ω × B on which are defined these measures, they are equal, proving that ν w ∞ is well a Dirac measure. This concludes the proof of the proposition.

Poisson boundary and asymptotic entropy. The Poisson boundary (B, ν)

is defined as the maximal µ-boundary, i.e. it is the µ-boundary such that any other µ-boundary is one of its measurable G-equinvariant quotients. A classical problem is to decide weather a space, that is known to be a µ-boundary, is in fact the maximal one.

For countable groups, there exists powerful techniques based on the estimation of the entropy introduced by Kaimanovich and Vershik [START_REF] Kaimanovich | Random walks on discrete groups: boundary and entropy[END_REF] and Derrienic [START_REF] Derriennic | Entropie, théorèmes limite et marches aléatoires[END_REF] and further developed by Kaimanovich (see [START_REF] Kaimanovich | The Poisson formula for groups with hyperbolic properties[END_REF] for details). Suppose that the measure µ has finite entropy:

H(µ) := - g∈G µ(g) ln µ(g) < ∞.
If (B, ν) is a µ-boundary and z ∈ B, it is possible to define the law P z of w ∈ Ω conditioned by b(w) = z. Then for n ≥ 0, P z n denotes the law of x n under P z , i.e. P z n (g) = P z (x n = g) = P(x n = g | b(w) = z). The conditional asymptotic entropy h z is defined by

h z := -lim n→+∞ ln P z n (x n ) n P z -a.s.
Then (B, ν) is the Poisson boundary if, and only if, h z is equal to zero for ν-almost every z.

Law of large numbers and µ-boundaries for GL

d (Q p )
In this section we can assume µ to be a probability measure on GL d (Q p ), not necessarily supported on matrices with rational coefficients. We are going to show that, under first moment hypothesis, the random walk on GL d (Q p ) satisfies a strong law of large numbers, in which the "speeds" of the drift are given by the Lyapunov exponents and the "directions" are given by an element of the associated flag manifold B p . This approach was introduced by V. Kaimanovich in [START_REF] Kaimanovich | Lyapunov exponents, symmetric spaces and a multiplicative ergodic theorem for semisimple Lie groups[END_REF] for semisimple Lie groups, as a group-geometrical version of the classical multiplicative ergodic theorem of Oseledets (see also [START_REF] Karlsson | A multiplicative ergodic theorem and nonpositively curved spaces[END_REF] and [START_REF] Karlsson | On laws of large numbers for random walks[END_REF]).

Related to this result, we will see that B p , endowed with the law of the "direction", is a µ-boundary for the random walk.

Oseledets' theorem and law of large numbers

. If p = ∞, let Λ n = Λ n (∞) be the diagonal matrix of GL d (R) with coefficients (2) (Λ n ) i,i := e nλi(∞) ∀i ≤ d.
If p ∈ P * , let Λ n = Λ n (p) be the diagonal matrix with coefficients

(3) (Λ n ) i,i := p - h nλ i (p) ln p i ∀i ≤ d;
where [•] is the integer part. In such a way, Λ n has rational entries whose p-norms are close to the e nλi(p) 's. To prove this proposition we use the following lemma that translates Oseledets' Theorem in our setting: Proof. Let us first recall the multiplicative ergodic theorem, first proved by V.I.

Oseledets [START_REF] Oseledets | A multiplicative ergodic theorem. Lyapunov characteristic numbers for dynamical systems[END_REF] for real matrices and generalized by M.S. Raghunathan [START_REF] Raghunathan | A proof of Oseledec's multiplicative ergodic theorem[END_REF] to matrices on local fields. It says that P-a.s. there exists a filtration of subspaces of

Q d p , {0} = V 0 (w) ⊂ V 1 (w) ⊂ • • • ⊂ V r (w) = Q d p , such that (i) The map w → V i (w) is measurable for all i ≤ r. (ii) For all 1 ≤ i ≤ r, we have v ∈ V i (w) \ V i-1 (w) if, and only if, lim n→+∞ 1 n ln ||w -1 n . . . w -1 1 v|| p = -λ ji (p),
where r and j 1 , . . . , j r are defined as in section 2.2. Suppose that p = ∞ (the real case is treated analogously). Denote by (e 1 , . . . , e d ) the canonical basis of

Q d p . Consider a matrix b ∈ GL d (Q p ) such that for all i ≤ r, b sends the family (e 1 , . . . , e ji ) into a basis of V i (w). Then b = [v 1 | • • • |v d ],
where for all i ≤ r, (v 1 , . . . , v ji ) is a basis of V i (w). Observe that

x -1 n bΛ n = x -1 n v 1 p - h nλ 1 (p) ln p i • • • x -1 n v d p - h nλ d (p) ln p i . Then max k=1,...,d p h nλ k (p) ln p i |x -1 n v k | p ≤ x -1 n bΛ n p ≤ d max k=1,...,d p h nλ k (p) ln p i |x -1 n v k | p . Then, since w -1 n . . . w -1 1 = x -1 n , by (ii) lim n→+∞ 1 n ln ||x -1 n bΛ n || p = 0.
To conclude the proof, just observe that two matrices b 1 and b 2 give two bases of the same filtration {V i (w)} i if, and only if, b -1 1 b 2 is in the group P p , thus such matrix b can be identified with an element of B p .

Proof of Proposition 3.1. Let x n = (w t 1 ) -1 • • • (w t n ) -1 = (x t n ) -1
be the random walk of law µ, image of µ under the map g → (g t ) -1 . Then the Lyapunov exponents associated to µ are

λ i = -λ d-i .
Let Λ n be the diagonal matrix constructed with the exponents λ i as in (3). For P-almost all w there exists a b ∈ GL d (Q p ) such that:

lim n→+∞ 1 n ln ||x t n b Λ n || p = 0. Consider the matrix s =    0 • • • 1 . . . • • • . . . 1 • • • 0    that transforms the basis (e 1 , . . . , e d ) in
the basis (e d , . . . , e 1 ). Then

||x t n b Λ n || p = ||x t n bss -1 Λ n s|| p since s p = s -1 p = 1 = ||x t n bsΛ -1 n || p since s -1 Λ n s = Λ -1 n = ||Λ -1 n ( bs) t x n || p since g t p = g p . Set b = (( bs) t ) -1 , then lim n→+∞ 1 n ln ||Λ -1 n b -1 x n || p = 0.
We want to show now that if b is as in ( 5) then b and b are in the same class in B p . To do this observe that ( 6)

u ∈ P p ⇐⇒ lim n→+∞ 1 n ln ||Λ -1 n uΛ n || p = 0 ⇐⇒ lim n→+∞ 1 n ln ||Λ -1 n uΛ n || p ≤ 0.
This can be proved by direct calculations using the fact that max i,j |g i,j | p ≤ ||g|| p ≤ d 2 max i,j |g i,j | p for all p ∈ P.

Then since ln Λ -1 n b -1 bΛ n p = ln Λ -1 n b -1 x n x -1 n bΛ n p ≤ ln Λ -1 n b -1 x n p + ln x -1 n bΛ n p , it follows immediately that b -1 b ∈ P p .
On the other hand

||Λ -1 n b -1 x n || p ||Λ -1 n uΛ n || -1 p ≤ ||Λ -1 n u -1 b -1 x n || p ≤ ||Λ -1 n u -1 Λ n || p ||Λ -1 n b -1 x n || p .
Then for every b 1 = bu with u in the group P p , lim n→+∞

1 n ln ||Λ -1 n b -1 1 x n || p = 0.
Thus for all b ∈ b(w),

lim n→+∞ 1 n d p (x n , bΛ n ) = lim n→+∞ 1 n (ln + x -1 n bΛ n p + ln + ||Λ -1 n b -1 x n || p ) = 0.
It just remains to see that the class b(w) is the unique such that (4) holds. But if b 1 and b 2 are two matrices such that (4) holds, then

0 = lim n→+∞ 1 n d p (b 1 Λ n , b 2 Λ n ) = lim n→+∞ 1 n d p e, Λ -1 n b -1 1 b 2 Λ n ,
and using once more (6) we conclude. Let ν be the law of b. Then (B, ν) is a µ-boundary.

Poisson boundary of GL d (Q)

To prove that B is the maximal µ-boundary, we use the following lemma, which is a generalization of the ray criterion of V. Kaimanovich [START_REF] Kaimanovich | The Poisson formula for groups with hyperbolic properties[END_REF], already implicitly used in our previous works [START_REF] Brofferio | The Poisson Boundary of random rational affinities[END_REF][START_REF] Br | The Poisson boundary of triangular matrices in a number field, to appear[END_REF]. Lemma 4.1. Let µ be a probability measure on a countable group G with finite entropy. Let (B, ν) be a µ-boundary and b the associated boundary map. Suppose that for each n there exits a measurable map C n from B to subsets of G such that:

lim n→+∞ P(x n ∈ C n (b(w))) = 1 and lim n→+∞ 1 n ln |C n (z)| ≤ δ ν(dz)-almost surely.
Then h z ≤ δ for ν-almost all z.

Proof. Observe that

P (x n ∈ C n (b(w))) = B P z n [C n (z)] ν(dz) → 1.
Thus, along a sub-sequence, P z n [C n (z)] converges to 1 for ν-almost all z. Recall that h z is the P z -almost sure limit ofln P z n (x n )/n. Now for any ε > 0 consider the set

A n (z) = {g ∈ G | -h z -ε < ln P z n (g)/n < -h z + ε} . Then P z n (A n (z) ∩ C n (z))
converges to 1 on a sub-sequence, while, for large n δ+ε) . Thus δh z + 2ε ≥ 0. Since ε was arbitrarily chosen, we get h z ≤ δ.

P z n (A n (z) ∩ C n (z)) ≤ e n(ε-h z ) |C n (z)| ≤ e n(ε-h z ) e n(
In order to apply this lemma in our setting we need to show that the gauge on GL d (Q) associated to the distance d grows at most exponentially:

Lemma 4.2. For g ∈ GL d (Q) and R ≥ 0, let B(g, R) = {h ∈ GL d (Q) | d(g, h) ≤ R}.
Then there exits a constant C > 0 such that for all g and R |B(g, R)| ≤ Ce CR .

Proof. First observe that since d(e, g -1 h) = d(g, h), we have g -1 B(g, R) = B(e, R). Thus two balls with the same radius have the same cardinality, and we can restrict us without loss of generality to the case g = e.

Observe now that if h = (h i,j ) ∈ B(e, R) then for all couples of indices (i, j)

p∈P ln + |h i,j | p ≤ p∈P max i,j ln + |h i,j | p ≤ d(e, h) ≤ R.
It can be shown (see for instance [START_REF] Brofferio | The Poisson Boundary of random rational affinities[END_REF]) that there exists

C ′ such that for all R    q ∈ Q | p∈P ln + |q| p < R    ≤ C ′ e C ′ R .
The desired result follows.

Proof of Theorem 1.1. First observe that, since µ has finite first moment with respect of to an exponentially growing gauge, it has finite entropy. For any p, consider the moment of the random walk with respect to d p :

m p = d p (e, g) dµ(g).

Observe that p∈P m p = E(d(e, w 1 )) < +∞. Fix F a finite subset of P and set m F c = p∈F c m p . By the law of large numbers, P-almost surely Thus for all finite F and all ε > 0,

h z ≤ 2C(|F |ε + m F c + ε).
Letting ε go to zero and F grow to P (in such a way m F c goes to zero), it follows that h z = 0 and thus that (B, ν) is the Poisson boundary.

To conclude we prove our triviality criterion:

Proof of Corollary 1.1. It is immediate that if λ 1 (p) = λ d (p) then P p = GL d (Q p ), thus B p is trivial. Suppose now that the projection of ν on B p is trivial , but that λ 1 (p) > λ d (p). In this case B p is nontrivial and the projection of ν on B p is a dirac measure whose mass is concentrated in a point b ∈ B p that is fixed by the support of µ. Then the support of µ fixes all sub-spaces that compose the nontrivial flag associated to b. This contradicts the fact that no proper subspace of Q d p is fixed by the support of µ.

Proposition 3 . 1 .

 31 Assume that d p (e, g) dµ(g) < +∞. Then there exists a measurable map b = b p : Ω → B p , such that P-almost surely b(w) is the unique element of B p such that x n , bΛ n ) = 0, for any b in the class of b(w).

Lemma 3 . 1 .ln ||x - 1 n

 311 Assume that d p (e, g) dµ(g) < +∞. Then there exists a measurable map b = b p : Ω → B p , such that P-almost surely bΛ n || p = 0, for any b in the class of b(w).

3. 2 . 3 . 1 .

 231 The spaces B p and B are µ-boundaries. It is easily checked, using leftinvariance of d p , that the function b p defined in Proposition 3.1 satisfies the hypothesis of Proposition 2.1. Then we immediately get Corollary Let µ be a probability measure on GL d (Q p ). Assume that d p (e, g) dµ(g) < +∞, and let ν p be the law of b p . Then (B p , ν p ) is a µ-boundary. Let µ be a probability measure on GL d (Q). Assume that d(e, g) dµ(g) < +∞. Let b be the map from Ω to B = p∈P B p defined by: b : w → b(w) = (b p (w)) p∈P .

1 P

 1 p∈F c d p (x n , e) n ≤ n k=1 p∈F c d p (x k , x k-1 ) n = n k=1 p∈F c d p (w k , e) n → m F c .Fix ε > 0 and b = (b p ) p∈P ∈ B, and setC F,ε n (b) =    g ∈ GL d (Q) | d p (g, b p Λ n (p)) ≤ n ε ∀p ∈ F, p∈F c d p (g, e) ≤ n (m F c + ε) x n ∈ C F,ε n (b(w)) → 1.To apply Lemma 4.1, we need to control the cardinality ofC F,ε n . Suppose that C F,ε n (b) is nonempty and let g 0 ∈ C F,ε n (b). Then for all g ∈ C F,ε n (b), d(g 0 , g) = p∈P d p (g 0 , g) ≤ p∈F (d p (g 0 , b p Λ n ) + d p (b p Λ n , g)) +p∈P-F (d p (g 0 , e) + d p (e, g)) ≤ 2n (|F |ε + m F c + ε) Thus 1 n ln |C F,ε n (b)| ≤ 1 n ln |B(g 0 , 2n (|F |ε + m F c + ε))| ≤ 2nC (|F |ε + m F c + ε) + ln C n .

Département de Mathématiques, Bât. 425, Université Paris-Sud 11, F-91405 Orsay, cedex, France.

E-mail address: sara.brofferio@math.u-psud.fr E-mail address: bruno.schapira@math.u-psud.fr


Samuel Bernard
email: samuel.bernard@lip6.fr

Fabrice Le

Optimizing Peer-to-Peer Backup using Lifetime Estimations

 have shown that lifetimes in a peer-to-peer system follow a Pareto distribution. Consequently, peers can be sorted on their expected lifetimes, depending only on the length of their history in the system. By carefully selecting the peers on which backup data is stored, repairing cost can be highly reduced for long-term backup users, while it is still acceptable for new users. The efficiency of this technique is evaluated through simulations of a state-of-the-art peer-topeer backup system.

INTRODUCTION

Backup of data has never been as important as in today's life. The presence of computers (digital cameras, organizers, etc.) in every part of our lives has considerably increased the quantity of personal digital data. In the same way, companies are now highly dependent on vital information stored on their computers. As a consequence, efficient techniques to prevent the loss of these data have to be used on every computer.

Yet, few computers are correctly configured to protect their data. Traditional backups on external supports are very common, but also unexpectedly very inefficient: 20% of nightly backups on tapes fail, while 40% are unusable afterwards; systems are not well configured, or just badly maintained. Few people know that backups on CD-R are short term (two years). Finally, all these solutions are very slow, and require additional hardware or manual interventions, and do not protect against thieves, fires or floods. Service Storage Providers (SSP) have received a lot of attention lately, with the cloud-computing wave, but still suffer from other risks, such as bankrupcies, internal failures (in Hotmail and Gmail) or lack of security. Therefore, our long term objective is to provide a new alternative backup system, free, efficient, reliable, yet still easyto-use, to help people protect data on their personal computers. Our system would be based on the exchange of free disk space between its members. To lower the cost and to bring a high resilience to faults, it has to be decentralized and to work in a peer-to-peer (P2P) way. In the literature, there are already some P2P backup systems. But most of them are still in prototype phase and has not yet been tested in acceptable conditions. The other ones are too restrictive and do not offer the conditions we want. Before building a complete system, we want to simulate such systems in order to know what their viability is, based on common properties of already designed systems.

Our contributions. In this paper we present the general description of a backup system and the specifications needed to estimate its viability. Then we describe our simulations and analyse their results. The contributions are twice. We prove the viability of a general peer-to-peer backup system and we introduce a new criteria, the age, to estimate the reliability of a peer.

SPECIFICATIONS

In this section, we introduce the general model and the basic assumptions for this work. We also describe the behavior of a state-of-the-art peer-to-peer backup system.

Model

We consider a large-scale network (in the order of thousands of computers) composed of nodes (or peers), connected by an underlying communication medium, typically IP. In this network, we assume full connectivity between peers, i.e. any peer can communicate with any other peer. This can usually be done by relaying the communications for firewalled peers, and we will not discuss it further.

Peers in the network have some disk space, divided between data that they need to backup and free disk space that they can share with other peers.

Studies of real peer-to-peer file-sharing networks [START_REF] Bustamante | Friendships that last: Peer lifespan and its role in P2P protocols[END_REF][START_REF] Maymounkov | A peer-to-peer information system based on the XOR metric[END_REF][START_REF] Tian | Understanding the dynamic of peer-to-peer systems[END_REF] have shown that the lifetime of peers in these systems is highly correlated to the length of their presence in the system. In other words, the longer a peer has been in the system, the longer it is expected to stay in the system. We assume that this property will also be observed in peer-to-peer backup systems, especially as peers are likely to participate more if the safety of their data is at stake.

To take this into account in our system, we assume the existence of a secure monitoring protocol for peer availability [START_REF] Morales | Optimal and scalable discovery of consistent availability monitoring overlays for distributed systems[END_REF][START_REF] Fessant | Pacemaker: Tracking peer availability in large networks[END_REF]: any peer can query the availability of any other peer for a given period of time, for example the last 90 days.

We assume that peers have enough computation resources to run all the parts of the backup system. Indeed, this paper focuses on optimizing the bandwidth used by the backup system, and not on optimizing the computation power, as the bandwidth is often the most limitating resource for home users. Consequently, we do not focus on the confidentiality of data: standard cryptography can be used to ensure data confidentiality, for example by encrypting data before it is used by the backup system.

Finally, we assume that the backup system uses erasure codes, such as Reed-Solomon [START_REF] Reed | Polynomial Codes Over Certain Finite Fields[END_REF], instead of simple replication to increase the redundancy of the backup. With such codes, for each set of k blocks of data, the system generates m blocks of correcting codes. These n = k + m blocks are then stored in the system. To get back the data, any k blocks from the n final blocks can be used. As an example, if k = 128 and m = 128, the system will store the data on 256 different nodes using twice the initial storage, but supporting until 128 node failures without losing any data. With replication, using twice the storage would mean that the data is only replicated twice, and so data might be lost after only two failures.

Description of the Backup System

A peer-to-peer backup system can be divided into three main tasks:

Backup of data : how the data is moved from the computer to the network Restoration of data : how the data is moved from the network back to the computer Maintenance of data : how the data is preserved in the network

In the following, we describe these three tasks in more details. Some of these details might differ in different systems, but this description can easily be adapted to most peer-topeer backup systems.

Backup of data

During the backup task, new data (either the content of complete files or the diffs between versions) is collected on the file-system, and is stored in a single file (archive). A new archive is created when the previous one reaches a given size. Usually, meta-data is stored in a different archive, with a better redundancy, to speed up the restoration task. For confidentiality, data in each archive can be encrypted using a session key.

Each archive is splitted in k blocks, and n = k + m new blocks are created. With Reed-Solomon, the k first blocks are the original ones, but these blocks might be different from the original ones in other coding systems. The n blocks are then uploaded to n different peers in the system. If the backup system contains a direct exchange mechanism, these n partners will be allowed to store one or more blocks of data on the peer in exchange for the space they have provided. Some systems might prefer a more global policy of fairness, where space is exchanged globally (see [START_REF] Cox | Honor among thieves in peer-to-peer storage[END_REF] for example) instead of between partners.

Finally, a master block is created. It contains the list of peers on which data has been stored, the list of archives, in particular the ones containing meta-data, and session keys, encrypted with the user public key (and consequently, only accessible using the user personal private key). The master block is then uploaded to the network, for example to all the partners storing the peer's data or to a DHT.

Restoration of data

The restoration task is done in the exact opposite order of the backup task. The master block is first retrieved from the network, for example using a flooding request or a query to a DHT. Meta-data archives are then downloaded to build an index of all the files stored in the backup. These two steps are only needed if the local copy of this information stored on the user computer has been lost. The data archives are then downloaded to restore the files on the computer, using the deciphered session keys to decrypt the files if needed.

To download an archive, the peer must reach at least k of its partners for that archive. Once k blocks have been downloaded, the k original blocks are decoded from these k blocks, and the content of the archive becomes available.

Maintenance of data

Churn is a well known problem in peer-to-peer systems: peers participating in the network are not connected all the time, and can decide to leave the network definitively, for example if they are not satisfied by the quality of service and they rather use another software.

As a consequence of churn, all blocks are not always available, and they might completely disappear when a peer decides to leave the network. In backup systems, contrary to distributed file-systems [START_REF] Busca | A highly-scalable multi-user peer-to-peer file system[END_REF], availability is less important than durability: if there is a trade-off between speed and security, the users are likely to prefer security, i.e. a better guarrantee to be able to retrieve their files, even if it takes more time. Therefore, in this paper, we are not interested in the instantaneous availability of the blocks, but only in their durability.

The maintenance of the backup is the perpetual task of replacing the blocks which have disappeared from the network. Since a peer cannot know if another peer that it cannot connect, will come back in the network or not, a time threshold is used: if a peer could not be connected during the threshold period, it is considered that the peer has definitively left the system and the blocks it was supposed to store have disappeared.

A repair threshold k ′ is usually defined, to decide when a repair operation should be triggered. The repair threshold specifies the minimal number of blocks that should be visible in the system. If fewer blocks are visible in the system, more failures could prevent a peer from recovering its data and thus its backup would be useless.

In this paper, we assume that, to replace d blocks that have disappeared from the network for a given archive (when nd < k ′ ), the peer must first download k blocks to be able to decode the original data. It can then re-encode either the missing blocks, or new blocks. This is a worst-case choice, as alternative coding systems [START_REF] Dimakis | Network coding for distributed storage systems[END_REF][START_REF] Duminuco | Hierarchical codes: how to make erasure codes attractive for peer-to-peer storage systems[END_REF] have been proposed to reduce the number of blocks needed to replace missing blocks. Finally, the peer must upload the new blocks to new partners (or to current partners but for other archives) and update the corresponding meta-data.

Evaluation of Maintenance Cost

From the previous description, we can evaluate the cost of maintenance of one archive with the following formula:

∆ download + ∆ decoding + ∆ encoding + ∆ upload + ∆ metadata
With recent computers, computation time for encoding and decoding is negligible compared to transfers on the network. In particular, DSL connections are usually asymmetric, with a good download bandwidth and a limited upload bandwidth. Finally, updating the meta-data is fast, as the peer just needs to upload the descriptors for the new partners, if any. Consequently, the cost of repair can be simplified to the download of k blocks and the download of d blocks:

∆repair = ∆ download + ∆ upload
We set the following parameters for our backup system: In this paper, we show that it is possible to decrease this maintenance cost for daily users of such a system, by better choosing on which peers the data is stored. Our choice heuristics uses the age of peers to estimate their stability.

In the following, we describe the simulations we made to evaluate the efficiency of our scheme.

SIMULATIONS 3.1 Simulation Context

To prove that an availability-aware scheme is efficient for peer-to-peer backup, we simulated a simple protocol using the PeerSim [START_REF] Jelasity | Peersim simulator, a peer-to-peer simulator[END_REF] simulator, a peer-to-peer simulator written and extensible in Java.

Our simulations are round-based: in a round, each peer is given the opportunity to execute some code and interact with some other peers; execution is sequential, so the code for one peer is always executed before or after the code for another peer, never concurrently, but the order of peers is chosen randomly at each round.

In our simulations, each round represents one hour. Indeed, we are not interested in small events, such as the messages which are sent or short-term disconnections. Instead, we focus on longer events, such as long-term peer disconnections and repair operations. One hour is indeed close to the approximation we did in the previous section of the time needed for a long repair (128 blocks in 77 minutes). Still, it is important to notice that repair operations do not need to be limited to one hour, since the critical part is the download of n blocks, taking usually around 8 minutes when done aggressively, while the upload of generated blocks can be done later as new partners become available. Finally, such a long duration per round allows us to simulate the system over a longer period, such as a few years, which is quite important for a long-term backup system.

To simulate a peer-to-peer backup system, we first made some assumptions:

Independence All departures, arrivals, disconnections and reconnections of nodes are strictly independent. This property was verified experimentally [START_REF] Bhagwan | Understanding availability[END_REF] on real peerto-peer systems.

Fidelity A node is less likely to quit the system when it has been in the system for a long time [START_REF] Bustamante | Friendships that last: Peer lifespan and its role in P2P protocols[END_REF][START_REF] Maymounkov | A peer-to-peer information system based on the XOR metric[END_REF][START_REF] Tian | Understanding the dynamic of peer-to-peer systems[END_REF]. This is the key property as it gives us a good criteria for the selection of partners. A node is more likely to exchange blocks of data with nodes which are as stable or more stable than it is.

Moreover we do not consider the existence of free-riders in this work, for the sake of simplicity. Yet, a peer does not rely completely on the system. It chooses his partners, evaluates them and is responsible for the maintenance of its backup. This design allows peers to completely monitor their backup and to choose different strategies independently, such as different parameters for repair thresholds. Moreover, peers only rely on the system for storing their blocks, and not to do complex tasks, such as repairs, which is safer approach. If a peer deletes some data, or is disconnected for a long time, it should still be able to recover its data. The time needed for recovery depends of the repairs rate, and the results are presented in section 4.

Simulated Protocol

In this subsection, we describe the protocol that we implemented in our simulator, in particular, during a repair operation. As written in section 2.2, it can be seen as a simple extension of existing protocols, such as [START_REF] Lillibridge | A cooperative internet backup scheme[END_REF]. We consider only one data archive per peer, the results can be trivially extended to the case of multiple archives.

When a node wants to store blocks on the peer-to-peer network, it creates a pool of possible partners, i.e. peers that do not yet store blocks for the same archive. To enter this pool, both peers must agree on their partnership, using an acceptation function that will be specified later. Once the pool is big enough, the peer can choose the d partners it needs to store the new blocks, and upload the data. Nodes are selected according to their stability. Because this stability cannot be guessed, the protocol uses the ages of the peers in the system to sort them: the longer a node has been in the system, the more stable it will be considered.

The acceptation function is used by peer p1 to choose whether a partnership can be started with peer p2. In our simulations, we took the following acceptation function:

f (p1, p2) = min " L -(min(s1, L) -min(s2, L)) + 1 L , 1
«
In this function, s1 and s2 are the estimations of the stability of both peers, i.e. the number of rounds since each peer first connected to the system. If some peers have an age greater than L, only the L part will be considered. We chose 90 days for L in our simulations, as we think it is a long enough period to consider a peer stable, and peers which have been in the system for longer times are not much different.

The result of the acceptation function is the probability for peer p1 to accept p2 as partners. We can notice the following properties:

The result is never zero, and actually, its minimum is 1 L . Indeed, we want that the probability to be accepted as a partner is never nul, even for newcomers in the system.

The result is always one if peer p2 is older than peer p1. Indeed, peers should always accept older peers as partners.

The function is not symmetric: the probability for p1 to accept p2 is different from the probability for p2 to accept p1, unless both peers are older than L.

Then during each round, every peer monitors its partners, i.e. checks whether they are online and have its data (see [START_REF] Oualha | Verifying self-organized storage with bilinear pairings[END_REF] for proofs of storage). If the number of partners for an archive is below a threshold, the peer will trigger a repair to replace the missing partners.

In our simulation, the initial step, when initial blocks are uploaded for the first time to the network, is seen as a repair where d = 256. A peer is not considered as included in the network until that first operation finishes.

Profiles of Peers

All the peers do not have the same behaviour in our system. Some peers are very stable and do not disconnect very often. Other peers are unavailable most of the time and are highly likely to quit the system early, consequently removing the blocks of their partners from the network.

In order to simulate this heterogeneity of behaviors, we have classified the peers into different profiles. A profile is a class of peers sharing globally the same behavior. For instance, in our simulation, there is a profile for very stable nodes, another one for very unstable nodes, etc.

In this paper, we are interested in making the system inexpensive for peers in the stable profiles, while making it a little more expensive for newcomers, who have to prove their stability to really benefit from such a system.

EVALUATION AND RESULTS

We first specify the parameters used in our simulations, and then, we present and discuss the results.

Parameters

In our simulations, we have used the following parameters:

• After a short growing phase, the number of peers in the system is 25,000. Each peer leaving the system is immediatly replaced, and its blocks are immediatly removed from its partners. We plan to investigate a more realistic approach in future work, where data would be removed only after a grace period ranging between one and several weeks.

• We only consider one archive per peer, with k = 128 original blocks and m = 128 redundancy blocks, thus n = 256 total blocks. However, we claim that these results should scale linearly when the number of archives of a peer is increasing, since they can be handled independently.

• We make the threshold before repair vary between 132 and 180, focusing later on the value 148. • A peer provides storage for at most 384 blocks in total to its partners: quota = 384. It means that a peer should provide three folds of free storage what it plans to backup in the system. We plan to investigate smaller quota in future work.

• We simulate 50,000 rounds which is approximately 5 years and half.

Note that, although our simulations are limited to 25,000 peers and one archive, results should the same for bigger systems and more archives, as peers are likely to aggregate into clusters or cliques, where all peers are partners for the other peers of the cluster, and pools for an archive are filled by partners for other archives.

Profiles

Each peer belongs to a profile and it cannot change during the simulation. A peer cannot know to which profile an other peer belongs to. A profile specifies different properties for a peer. Currently, there are two properties, the peer's life expectancy, which is how many rounds it will stay in the system, and its availability, which is the percentage of time it will be online. We use four different profiles, in different proportions in the system for our simulations. In short, around a third of the peers are stable and should suit to the backup, another third are less stable and could cause some problems and the last third is too erratic to be really usable. The question we ask is if the unstable peers can prevent stable ones from achieving good backup performances (in number of repairs).

We claim that this setting is a realistic one. To the best of our knowledge, no peer-to-peer backup system is largely deployed on the Internet, so no traces of user's behaviors are available. Therefore, to create the previous profiles, we used the result of studies on peer-to-peer file-sharing systems [START_REF] Bhagwan | Understanding availability[END_REF]. Those result are too pessimistic to create a reliable backup system, so we modified them a little to be more optimistic. However, we kept a large part of unstable peers in order to still keep a pessimistic approach. We claim that this approach is the most realistic one, as users in peer-to-peer file-sharing networks have an incentive to disconnect early (not to be caught by the police), whereas users in peer-topeer backup networks have an incentive to remain connected (to protect their data).

Results and Discussion

In the following, we present and discuss our two main results: the impact of the repair threshold, and the cost of maintenance for the four profiles of users.

Impact of the Repair Threshold

Our goal was to evaluate the impact of the repair threshold on the repair rate and on the data loss rate. So we ran a set of simulations with exactly the same parameters, presented at the beginning of this section, while varying the repair threshold between 132 and 180.

We present the results for 4 categories of nodes, differentiated by their age. Note that during the life of a peer, its category changes depending on its age, whereas its profile does not change: at the beginning it is a Newcomers, then after 3 months it will be counted as a Young peer, etc. The following table details the interval of ages for each category: Peers Age Elder peers > 18 months Old peers 6 -18 months Young peers 3 -6 months Newcomers < 3 months Figure 1 plots the average rate of repairs, for the four categories depending on the repair threshold. Figure 2 plots the average rate of data loss for the four categories, also depending on the repair threshold. Average Rate of Repairs. As expected, the main result of figure 1 is that the number of repairs increases accordingly to the repair threshold. The bigger the threshold, the more peers need to repair. The reason is that peers are progressively losing their partners and, if the repair threshold is high, it is reached sooner. The increase is not linear and raises faster after 156. Another result is the stratification between the profiles. Young peers (erratic ones) repair more often than the elder ones (stable ones). We detail this in the section 4.2.2.

Average Rate of Data Lost. As the repair threshold has an impact on the number of repairs, it has also an impact on the number of lost archives. As seen in the figure 2, if the repair threshold is too small, a peer may lose too quickly its partners, and will be unable to regenerate original blocks to fulfill the repair. For instance, if the threshold is 132 and a peer has 133 blocks available, it may lose more than 5 blocks in a round if its partners are not very stable, and consequently, with fewer than 128 blocks available in the system, be unable to repair. Even if the disconnections were temporary, the peer might never be able to repair early enough before other definitive disconnections. On the contrary, if the threshold is too high, a young peer will lose its blocks too quickly and thus will have to repair at each round. But that peer might have some difficulties to find new partners, and so the peer might be unable to upload all the missing blocks, and so, to prevent the number of its partners from decreasing dangerously.

To decide on a good repair threshold, we have to find a good compromise between the loss rate and the repair rate. As the repair rate is strictly increasing, we can take the smallest value of threshold with a good loss rate. 148 seems such a good compromise. In the following, we present in more details the simulations computed with a repair threshold set to 148.

Impact of the Age of Peers

In the previous results, we have seen that the stable profiles will repair less often than the unstable ones. We now explain what is happening on an example, the simulation computed with a repair threshold set to 148.

Repair Rate for Observers. Figure 3 shows the total number of repairs done by some particular peers, called observers. An observer is a special peer, whose age does not increase like the age of other peers. Other peers cannot choose an observer as a partner, but the observer can choose other peers as partners, without however consuming their quota (the quota is the number of blocks a peer can host for its partners, and is set to 384 blocks in our simulations). As normal peers, it has to repair if its number of available blocks decreases below the repair threshold.

In this simulation, we put 5 observers: The figure shows that the repair rate strongly depends on the age of a peer. The Elder and Senior observers have less than 10 repairs in 2000 days, the Adult has less than 20 repairs, the Teenager has less than 100 repairs and finally the Baby has a huge 900 repairs. Note that the global performance are better than we may think. The Baby observer has 900 repairs but a normal peer, during its lifetime in the system, will only be considered as a Baby for one day and as a Teenager for one week. So, quickly, most of the peers will be as good as an Adult observer, or even better.

Analysis. The link between the age and the rate of repair is clearly understandable. An elder peer is accepted by every other peer, so he can choose to store its blocks on the most stable peers. Moreover, after some repairs, he has replaced most of the unstable partners that he was forced to use when he was a newcomer. Moreover, as a side-effect of the protocol, stable peers will progressively form clusters of partners.

Nevertheless, younger peers still have good performances, since usually, one week is enough to find good stable partners.

Losses of Archives.

To understand why data is lost, we plotted in figure 4 the evolution of the cumulative average number of lost archives for the four categories of peers presented in the table of the section 4.2.1 (and not observers this time).

The figure shows that an Newcomers will lose about 18 archives during 2000 days in the system, while all the other peers almost never lose anything. The loss of data for Newcomer peers seems huge but we can also notice a faster increase of data loss between the 200 th and the 600 th day. This corresponds to a stabilisation phase due to the start of the simulation where all peers have the same age. The more eloquent part of the curve is between the 1000 th and the 2000 th day when the system has became stable: we see that the total number of lost archives drop to 2 in 1000 days which is reasonable. Moreover in 1000 days, a peer would be quickly considered as at least an unstable or a stable peer and so would not suffer archives lost anymore in fact.

With these simulations, we have shown that it is possible to optimize the maintenance cost of a peer-to-peer backup system, by moving the load of maintenance from stable peers (actually, long-term users of the system) to unstable peers. Moreover, we have shown that the cost is higher for newcomers only for a short period.

RELATED WORK

As far as we know, no previous study of viability of peerto-peer backup systems has been done. However, some work has already been done on their design, for example OceanStore [START_REF] Rhea | Probabilistic location and routing[END_REF][START_REF] Rhea | Pond: The oceanstore prototype[END_REF], Past [START_REF] Rowstron | Storage management and caching in past, a large-scale, persistent peer-to-peer storage utility[END_REF], pStore [START_REF] Batten | pStore: A secure peer-to-peer backup system[END_REF], Pastiche [START_REF] Cox | Pastiche: Making backup cheap and easy[END_REF], a system designed by Lillibrige et al. [START_REF] Lillibridge | A cooperative internet backup scheme[END_REF], Total Recall [START_REF] Bhagwan | Total recall: System support for automated availability management[END_REF], PeerStore [START_REF] Landers | Better performance by relaxing in peer-to-peer backup[END_REF], Pastis [START_REF] Busca | A highly-scalable multi-user peer-to-peer file system[END_REF] and Glacier [START_REF] Haeberlen | Glacier: Highly durable, decentralized storage despite massive correlated failures[END_REF].

Some of these systems are presented as peer-to-peer filesystems which makes them a little different from a backup system. In particular, persistence of data in backup systems is more important than read/write performances, while it is the opposite for file-systems. Most of them are still in prototyping phase, without real deployments. The main difficulty of this phase is that it is hard to have a large enough testbed, i.e. enough users trusting the system to use it on a daily basis. Our work with large size simulations could help developers to tune the parameters of these systems, like the repair threshold which is very difficult to set otherwise.

Another interesting optimization of the maintenance of a peer-to-peer backup system is presented in [START_REF] Duminuco | Proactive replication in distributed storage systems using machine availability estimation[END_REF]. To decrease the probability of losing archives, their system measures the churn, i.e. the rate of departure of partners, and pro-actively creates new blocks at the same rate. Consequently, peer don't need to know exactly which partners have departed, relaxing the stress on the monitoring system.

CONCLUSION

This work has two main contributions. The first one is to prove the viability of a peer-to-peer backup system. We showed that, with a simple scheme based on lifetime estimation, a peer-to-peer backup system using erasure codes could achieve good performances in term of maintenance cost. Indeed, the number of repairs for normal users is far below the limit of feasibility imposed by the bandwidth of actual Internet home connections with almost one repair per archive in 200 days.

The second contribution is to provide a new criteria for the selection of partners. In our scheme, an older peer that has used the system for a long time, is considered more stable and more reliable than a newcomer. This assumption has often been verified in other systems. With this selection criteria, we achieve excellent performance for older peers, which are also the best contributors of the system. As a result, this may also be considered as a kind of tit-for-tat protocol. Reliable peers will be rewarded by excellent performances.

As future works, we plan to improve our simulations by allowing parameters to adapt more dynamically. For instance, the repair threshold might be changed depending on the peer context, its difficulties to find partners, the data that it needs to download, etc. We also plan to investigate more on the impact of temporary disconnections, in particular by delaying the repair to allow peers to come back in the system.

Figure 1 :

 1 Figure 1: Average rate of repairs for the four categories of peers depending of the repair threshold.

Figure 2 :

 2 Figure 2: Average rate of data lost for the four categories of peers depending of the repair threshold

Figure 3 :

 3 Figure 3: Total number of repairs done by observers

Figure 4 :

 4 Figure 4: Evolution of the cumulative number of lost archives for the four categories of peers