Anne-Marie Kermarrec
email: anne-marie.kermarrec@inria.fr

Nicolas Le Scouarnec
email: nicolas.le-scouarnec@technicolor.com

Gilles Straub
email: gilles.straub@technicolor.com

Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes

Keywords: distributed storage, regenerating codes, multiple failures, selfhealing, network coding erasure correcting codes, regenerating codes, distributed storage, repair, multiple failures

in the presence of simultaneous failures. It is crucial to maintain the required redundancy over time to prevent permanent data losses. We go beyond existing work (i.e., regenerating codes by Dimakis et al.) and propose coordinated regenerating codes allowing devices to coordinate during simultaneous repairs thus reducing the costs further. We provide closed form expressions of the communication costs of our new codes depending on the number of live devices and the number of devices being repaired. We prove that deliberately delaying repairs does not bring additional gains in itself. This means that regenerating codes are optimal as long as each failure can be repaired before a second one occurs. Yet, when multiple failures are detected simultaneously, we prove that our coordinated regenerating codes are optimal and outperform uncoordinated repairs (with respect to communication and storage costs). Finally, we define adaptive regenerating codes that self-adapt to the system state and prove they are optimal.

Réparation de défaillances multiples avec des codes régénérants coordonnés et adaptatifs

Résumé : Les codes correcteurs d'effacements sont largement utilisés pour assurer la persistance des données dans les systèmes de stockage distribués.

Ce rapport s'intéresse à la réparation de tels codes dans le cas de défaillances simultanées. Cette maintenance est cruciale afin de prévenir les pertes de données permanentes. Nous étendons les travaux existants (codes régénérants par Dimakis et al.) et proposons des codes régénérants coordonnés qui permettent aux éléments du systèmes de se coordonner durant les réparations de défaillances simultanées afin de réduire les coûts de réparation. Nous fournissons une forme close des coûts de communications de nos codes en fonction du nombre d'équipements vivants et du nombre d'équipements en cours de réparation. Nous prouvons, par ailleurs, que retarder les réparations de façon délibérée n'apporte pas de gains additionnels. Cela signifie que les codes régénérants sont optimaux tant qu'une première défaillance peut être réparée avant une seconde. Cependant, quand de multiples défaillances sont détectés simultanément, nous prouvons que nos codes régénérants coordonnés sont optimaux et dépasse les réparations non coordonnées (vis à vis des coûts de stockage et de réparation). Enfin, nous définissons des codes régénérants adaptatifs qui s'auto-adaptent à l'état du système et prouvons qu'ils sont optimaux.

Mots-clés :

stockage distribué, codes régénérants, défaillances multiples, auto-réparation, codage réseau

I. INTRODUCTION

Over the last decade, digital information to be stored, be it scientific data, photos, videos, etc, has grown exponentially. Meanwhile, the widespread access to the Internet has changed behaviors: users now expect reliable storage and seamless access to their data. The combination of these factors dramatically increases the demand for large-scale distributed storage systems. Such systems are used as back-ends by cloud service providers or as a basis for P2P systems to provide users with storage, backup or sharing capabilities. This is traditionally achieved by aggregating numerous physical devices to provide large and resilient storage [START_REF] Dabek | Wide-area Cooperative Storage with CFS[END_REF]- [START_REF] Bhagwan | Total Recall: System Support for Automated Availability Management[END_REF]. In such systems, which are prone to disk and network failures, redundancy is the natural solution to prevent permanent data losses. However, as failures occur, the level of redundancy decreases, potentially jeopardizing the ability to recover the original data. This This is an extended version of an article published as a regular paper at NetCod 2011 available on IEEE Xplore (please cite the conference article [START_REF] Kermarrec | Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes[END_REF]). It initially appeared (September 2010) as an INRIA Research Report (http://hal.inria.fr/inria-00516647) entitled Beyond Regenerating Codes. The following notice apply to the conference article published at NetCod 2011. c 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. requires the storage system to self-repair to go back to its healthy state (i.e., keep redundancy above a minimum level).

Repairing redundancy is of paramount importance for the design and implementation of distributed storage systems. A self-healing mechanism is usually composed of three phases. First, the system must self-monitor to detect failures. Second, the system must trigger a repair on a set of spare devices. Finally, the system must regenerate the lost redundancy from the remaining one. In this paper, we focus on this last phase. Redundancy in storage systems has been extensively implemented using erasure correcting codes [START_REF] Weatherspoon | Erasure Coding Vs. Replication: A Quantitative Comparison[END_REF]- [START_REF] Rodrigues | High Availability in DHTs: Erasure Coding vs. Replication[END_REF] because they enable tolerance to failures at a low storage overhead. In this context, the repair used to induce a large communication overhead, as it required to download and decode the whole file. Yet, Dimakis et al. recently showed [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF], [START_REF]Network Coding for Distributed Storage Systems[END_REF] that the repair cost can be significantly reduced by avoiding decoding in the so-called regenerating codes.

In this paper, we go beyond these works by considering simultaneous repairs in regenerating-like codes. We propose coordinated regenerating codes allowing devices to leverage simultaneous repairs: each of the t devices being repaired contacts d live (i.e., non-failed) devices and then coordinates with the t -1 others. Our contribution is threefold:

• As deliberately delaying repairs in erasure correcting codes leads to savings [START_REF] Bhagwan | Total Recall: System Support for Automated Availability Management[END_REF], [START_REF] Datta | Internet-scale storage systems under churn -A Study of steady-state using Markov models[END_REF], [START_REF] Dalle | Analysis of Failure Correlation Impact on Peer-to-Peer Storage Systems[END_REF], it is natural to wonder if the same additional savings can be expected when delaying repairs for regenerating codes. By defining coordinated regenerating codes, we prove that, when relying on regenerating-like codes (MSR or MBR) [START_REF]Network Coding for Distributed Storage Systems[END_REF], deliberately delaying repairs (so that t > 1) cannot lead to further savings.

• Yet in practical systems, it might be difficult to detect every single failure and fix it before a second one occurs (i.e., ensure t = 1). We establish the optimal quantities of information to be transferred when t devices must be repaired simultaneously from d live devices. Our coordinated regenerating codes consistently outperform existing approaches.

• In addition, most practical systems are highly dynamic. Therefore, assuming that t and d remain constant across repairs is unrealistic. To address this issue, we define adaptive regenerating codes achieving optimal repairs according to t and d. Under a constant system size d + t, their performance does not depend on t (i.e., the cost of a repair does not increase if the number of failed devices to repair increases). Previous approaches are either known for not supporting simultaneous coordinated repairs [START_REF]Network Coding for Distributed Storage Systems[END_REF] or known for assuming that repairing implies decoding which requires to download the whole file [START_REF] Bhagwan | Total Recall: System Support for Automated Availability Management[END_REF]- [START_REF] Lin | Erasure Code Replication Revisited[END_REF], [START_REF] Datta | Internet-scale storage systems under churn -A Study of steady-state using Markov models[END_REF], [START_REF] Dalle | Analysis of Failure Correlation Impact on Peer-to-Peer Storage Systems[END_REF]. Hence, we define coordinated regenerating codes that fill the gap between the two aforementioned approaches by achieving simultaneous repairs without decoding (Figure 4). Furthermore, as existing regenerating codes assume a static set of parameters, we define adaptive regenerating codes that can self-adapt. Two recent works have been interested in these same problems. MCR Codes [START_REF] Hu | Cooperative Recovery of Distributed Storage Systems from Multiple Losses with Network Coding[END_REF] define MSR-like codes that support multiple repair at once and MFR [START_REF] Wang | MFR: Multi-Loss Flexible Recovery in Distributed Storage Systems[END_REF] codes show that MSR codes can be turned into adaptive codes. Yet, MCR Codes only consider the Minimum Storage point and assume that all transfers are equal without proving it (i.e., β = β ); and MFR [START_REF] Wang | MFR: Multi-Loss Flexible Recovery in Distributed Storage Systems[END_REF] codes are not optimal when repairing more than one failure. Finally, since, for erasure correcting codes, simultaneous repairs reduce the communication overhead, we study the impact of deliberately delaying repairs with regenerating-like codes.

The paper is organized as follows. Section II describes the background on codes. Section III presents our coordinated regenerating codes. In this section, we prove the optimality of our codes, we derive closed-form expressions for specific subsets of codes, and we show that deliberately delaying repairs does not reduce the costs further as long as each failure can be fixed before a second one occurs. In Section IV, we propose adaptive regenerating codes that self-adapt to the dynamic of the system and we prove their optimality. Section V briefly reviews some related work. Section VI concludes.

II. BACKGROUND

We consider a n device system storing a file of M bits split in k blocks of size B = M/k. To cope with device failures, blocks are stored with some redundancy so that a single failure cannot lead to permanent data losses. We consider code-based approaches to redundancy since they have been proven to be more efficient than replication with respect to both storage and repair costs [START_REF] Weatherspoon | Erasure Coding Vs. Replication: A Quantitative Comparison[END_REF]. We focus on self-healing systems (i.e., systems that automatically repair themselves upon failure). Distributed storage systems are required to be self-healing so as to ensure that the system does not gradually lose its ability to recover the initial file. Self-healing systems are equipped with a self-monitoring component that detects failed devices and triggers repairs [START_REF] Morales | AVMON: Optimal and Scalable Discovery of Consistant Availability Monitoring Overlays for Distributed Systems[END_REF] on new spare devices. To repair, the new spare devices regenerate the lost redundancy from data downloaded from live devices. The repair is constrained by the communication costs [START_REF] Blake | High Availability, Scalable Storage, Dynamic Peer Networks: Pick Two[END_REF]. In the rest of this section, we describe the main code-based approaches for generating and repairing redundancy.

A. Erasure correcting codes (immediate/eager repairs) Erasure correcting codes have been widely used to provide redundancy in distributed storage systems [START_REF] Weatherspoon | Erasure Coding Vs. Replication: A Quantitative Comparison[END_REF]- [START_REF] Rodrigues | High Availability in DHTs: Erasure Coding vs. Replication[END_REF]. Devices store n encoded blocks of size B, which are computed from the k original blocks. As erasure correcting codes are optimal with respect to recovery (i.e., they allow recovering the k original blocks from any subset of k encoded blocks), storing encoded blocks at n = k + f devices is sufficient to tolerate f failures. This approach is efficient with respect to storage. Yet, repairing a lost encoded block is very expensive since the devices must fully decode the initial file. Hence, repairing a single lost block implies downloading k encoded blocks as shown on Figure 1a.

B. Erasure correcting codes (delayed/lazy repairs)

A first approach to limit the repair cost of erasure correcting codes is to delay repairs and factor downloading costs [START_REF] Bhagwan | Total Recall: System Support for Automated Availability Management[END_REF], [START_REF] Datta | Internet-scale storage systems under churn -A Study of steady-state using Markov models[END_REF], [START_REF] Dalle | Analysis of Failure Correlation Impact on Peer-to-Peer Storage Systems[END_REF]. When a device has downloaded k blocks, it can produce as many new encoded blocks as wanted without any additional cost. Therefore, instead of performing a repair upon every single failure (Figure 2a), repairs are deliberately delayed until t (threshold) failures are detected (Figure 2b). This repair strategy is depicted on Figure 1b. One of the new devices downloads k blocks, regenerates t blocks and dispatches them to the t -1 other spare new devices.

C. Network coding and regenerating codes

A second approach to increase the efficiency of repairs relies on network coding. Network coding differs from erasure correcting codes as it allows devices to generate new blocks with only partial knowledge (i.e., with less than M bits). Network coding was initially applied to multicast, for which it has been proved that linear codes achieve the maxflow in a communication graph [START_REF] Ahlswede | Network Information Flow[END_REF]- [START_REF] Koetter | An Algebraic Approach to Network Coding[END_REF]. Network coding has latter been applied to distributed storage and data persistence [START_REF] Dimakis | Ubiquitous Access to Distributed Data in Large-Scale Sensor Networks Through Decentralized Erasure Codes[END_REF]- [START_REF] Lin | Differentiated Data Persistence with Priority Random Linear Codes[END_REF]. A key contribution in this area are regenerating codes [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF], [START_REF]Network Coding for Distributed Storage Systems[END_REF] introduced by Dimakis et al. They infer the minimum amount of information to be transferred to repair lost redundancy.

The idea behind regenerating codes [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF] is that, when compared to erasure correcting codes, more devices are contacted upon repair but much less data is downloaded from them thus offering low repair cost for each single failure. Similarly to erasure correcting codes, n encoded blocks of size α bits are computed from the k original blocks. Each device stores α ≈ M k bits. During a repair, the new device contacts d > k other devices to get β M/k bits from each and stores α bits as shown on Figure 1c. Regenerating codes achieve an optimal trade-off between the storage α and the repair cost γ = dβ. The graph on Figure 3 depicts the performance of the optimal regenerating codes. Points (α, γ) above the curve correspond to correct (but non-optimal) regenerating codes. Two specific regenerating codes are interesting: MSR (Minimum Storage Regenerating codes) offer optimal repair cost γ = M for a minimum repair cost γ = M k 2d 2d-k+1 . Regenerating codes can be implemented using linear codes [START_REF] Li | Linear Network Coding[END_REF], [START_REF] Koetter | An Algebraic Approach to Network Coding[END_REF] be they random [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF], [START_REF] Duminuco | A Pratical Study of Regenerating Codes for Peer-to-Peer Backup Systems[END_REF] (i.e., random linear network codes), or deterministic [START_REF] Dimakis | A Survey on Network Codes for Distributed Storage[END_REF]- [START_REF] Suh | Exact Regeneration Codes for Distributed Storage Repair Using Interference Alignment[END_REF]. Similarly to regenerating codes, our codes can be implemented using random linear network codes.

Table I gives some examples of storage cost α and repair cost γ for the codes we describe including the coordinated codes we propose. These costs depend on the number k of devices needed to recover the file, the number d of contacted live devices, and the number t of devices being repaired simultaneously. Regenerating codes by Dimakis et al. [START_REF]Network Coding for Distributed Storage Systems[END_REF] represent a clear improvement over erasure correcting codes, and our coordinated regenerating codes allow reducing further the costs.

D. Design rationale

Regenerating codes transfer the minimal quantity of information needed to repair one device storing α bits. Dimakis et al. assume fully independent repairs: simultaneous failures are fixed independently. The cost of repairs increase linearly in t. In this work, we investigate coordinately repairing simultaneous failures in an attempt to reduce the cost, along the lines of delayed repair in erasure correcting codes. Contrary to regenerating codes that repair only using data from live devices, our coordinated regenerating codes also allow the use of data from other devices being repaired. By coordinating the repair, we show that it is possible to repair multiple failures at once with an average cost of γ < γ. As depicted on Figure 4, our new codes encompass both erasure correcting codes (d = k) and regenerating codes (t = 1). In the next section, we detail our coordinated regenerating codes supporting coordinated repairs.

III. COORDINATED REGENERATING CODES

We consider a situation where t devices fail and, repairs are performed simultaneously. We assume that an underlying monitoring service triggers the repair and contacts all involved devices (i.e., the t spare devices that join the system to replace failed ones). Directly applying erasure correcting codes delayed repairs (Fig. 1b) (i.e., one device repairing for many other devices) to regenerating codes (Fig. 1c) is not appropriate. In short, the fact that all the data goes through the device that regenerates for others induce more network transfers than needed: as repairing does not require decoding, gathering all the information at a single device is not necessary.

A. Repair algorithm

We introduce new coordinated regenerating codes allowing devices to repair simultaneously at the optimal cost (with respect to network communication). The repair is illustrated on Figures 5 and7 showing the amounts of information transfered, and on Figure 6 showing the computations and exchanges of sub-blocks of data. A device being repaired performs the three following tasks, jointly with all other devices being repaired: . W 1 and W 2 can be erased upon completion. Interestingly, thanks to the explicit coordination step involving all devices, this approach evenly balances the load on all devices. Hence, coordinated regenerating codes avoid the bottleneck existing in erasure correcting codes delayed repairs (i.e., the device gathering all the information) (cf. Fig. 1b).

1. Collect. It
In the rest of this section, we present our main results: we investigate the optimal tradeoffs between storage and repair costs (i.e., optimal values for α (data to store), β and β (data to transfer)). As we consider the problem from an information theoretic point of view, we can ignore the nature of the information and only consider the amounts of information that must be exchanged to repair the redundancy. Our results define the fundamental tradeoffs that can be achieved (i.e., lower bounds on amounts of information to be transfered to repair).

Our proof is inspired from the proof by Dimakis et al. found in [START_REF]Network Coding for Distributed Storage Systems[END_REF]. We represent the system as an information flow graph. For we add a coordination step, our graph differs from the one proposed in [START_REF]Network Coding for Distributed Storage Systems[END_REF]. However, Lemmas 2 and 3 are identical to the ones proposed in [START_REF]Network Coding for Distributed Storage Systems[END_REF] as they still apply to our information flow graph. When compared to [START_REF]Network Coding for Distributed Storage Systems[END_REF], we

y 1,1 = f 1 (X) y 1,2 = f 2 (X) y 1,3 = f 3 (X) c 1,1 g 1 c 1,2 g 2 y 2,1 = f 4 (X) y 2,2 = f 5 (X) y 2,3 = f 6 (X) c 2,1 g 3 c 2,2 g 4 y 3,1 = f 7 (X) y 3,2 = f 8 (X)
y 3,3 = f 9 (X) c 3,1 g 5 c 3,2 g 6 y 4,1 = f . (X) y 4,2 = f . (X) y 4,3 = f . (X) c 1,1 c 2,1 c 3,1 e 1,1 h 1 e 2,1 y 6,1 y 6,2 y 6,3 k 1 k 2 k 3 y 5,1 = f . (X) y 5,2 = f . (X)
y 5,3 = f . (X) c 1,2 c 2,2 c 3,2 e 2,1 h 2 e 1,1 y 7,1 y 7,2 y 7,3 k 4 k 5 k 6 c 1,1 = g 1 (y 1,1 , y 1,2 , y 1,3 ) e 1,1 = h 1 (c 1,1 , c 2,1 , c 3,1 ) y 6,1 = k 1 (c 1,1 , c 2,1 , c 3,1 , e 2,1 )
dashed edges: network transfers plain edges: local computations We determine the optimal codes (i.e., we minimize the storage and the repair cost under some constraints obtained by studying information flow graphs). We give the expressions for optimal values of α (storage at each node), γ (repair cost), β (data transferred during collecting step) and β (data transferred during coordinating step) as a function of d, k and t (parameters of the system). We also examine the influence of deliberately delaying repairs (i.e., increasing t while decreasing d). Our notations are summarized in Table II.

MSCR codes (k = 2, d = 3, t = 2). M = 2MB, β = β ′ = 0.33MB W 1 W 1 W 3 W 3 W 2 W 2 α = 1MB }0.33MB Collect Coordinate Store

B. Information flow graphs

Our study is based on information flow graphs similar to the ones defined in [START_REF]Network Coding for Distributed Storage Systems[END_REF]. An information flow graph is a representation of a distributed storage system that describes how the information about the file stored is communicated through the network. The information flow graph G is a directed acyclic graph composed of a source S, intermediary nodes x i,j in , x i,j coor and x i,j out (i corresponds to a time step while j corresponds to the index of a device introduced at time step i), and data collectors DC i (data collectors try to contact k devices to decode and recover the file). The capacities of the edges (α, β, β ) correspond to the amounts of information that can be stored or transferred.

In our approach, a real device x i,j is represented in the graph by 3 nodes (x i,j in , x i,j coor and x i,j out ) corresponding to its successive states. The graph of a repair of t devices is shown on Figure 7 (assume t divides k.). First, devices perform a collecting step represented by edges x k,j out → x i,j in (k < i) of capacity β (d such edges). Second, devices undergo a coordinating step represented by edges x i,j in → x i,j coor of capacity β for j = j (t -1 such edges). Devices keep everything they obtained during the first step justifying the infinite capacities of edges x i,j in → x i,j coor . Third, they store α using edges x i,j coor → x i,j out . Figure 8 gives other examples of information flow graphs.

The graph G evolves as repairs are performed. When a repair is performed, a set of nodes is added to the graph and the nodes corresponding to failed devices become inactive (i.e., subsequently added intermediary nodes or data collectors cannot be connected to these nodes).

The rest of the article relies on the concept of minimum cuts in information flow graphs. A cut C between S and DC i is a subset of edges of G such that there is no path from S to DC i that does not have at least one edge in C. The minimum cut is the cut that has the smallest sum of edge capacities.

C. Achievable codes

We define two important properties on codes: Correctness A code (n, k, d, t, α, γ) is correct iff, for any succession of repairs, a data collector can recover the file by connecting to any k devices. Optimality A code (n, k, d, t, α, γ) is optimal iff it is correct and any code (n, k, d, t, ᾱ, γ) with (ᾱ, γ) < (α, γ) is not correct 1 . The following theorem is an important result of our work. Theorem 1. A coordinated regenerating code (n, k, d, t, α, γ) is correct2 if and only if there exists β and β such that the constraints of (1) and (2) are satisfied. A code minimizing the repair cost γ (1), along constraints of (2) is optimal.

γ = dβ + (t -1)β (1)
x i,3

in x i,2 in x i,1 in x i,3 coor x i,2 coor x i,1 coor x i,3 out x i,2 out x i,1 out β β β β β β β β β ∞ ∞ ∞ α α α β ′ β ′ β ′ β ′ β ′ β ′ d d d t

Collect

Coordinate Store ∀u, such that

g-1 i=0 u i = k and 1 ≤ u i ≤ t, g-1 i=0 u i min{α, (d - i-1 j=0 u j )β + (t -u i )β } ≥ M (2)
These constraints, proven in the rest of this subsection, mean that the sum of the amounts of information that can be downloaded from each of the k devices contacted by a data collector must be greater than the file size (amount of information needed to recover the original file). To this end, we consider, for a given coordinated regenerating code (n, k, d, t, α, γ), all (infinite) corresponding information flow graphs and evaluate the flow of information that can go from the source to any data collector in such graphs. The vector u = (u i ) 0≤i<g represents a possible recovery scenario (i.e., the number u i of devices contacted in each of the g repair group of size t during the recovery). Since the recovery must be possible for any scenario, we consider all possible u. We show that (2) is satisfied if and only if decoding is possible at any time (i.e., as long as the aforementioned constraints are satisfied, no data is lost).

Lemma 2. For any information flow graph G, no data collector DC can recover the initial file if the minimum cut in G between S and DC is smaller than the initial file size M.

Proof: Similarly to the proof in [START_REF]Network Coding for Distributed Storage Systems[END_REF], since each edge in the information flow graph can be used at most once, and since source to data collector capacity is less than the file size M, the recovery of the file is impossible. Lemma 3. For any finite information flow graph G, if the minimum of the min-cuts separating the source and each data collector is larger than or equal to the file size M, then there exists a linear network code such that all data collectors can recover the file. Furthermore, randomized network coding allows all collectors to recover the file with high probability.

Proof: Similarly to the proof in [START_REF]Network Coding for Distributed Storage Systems[END_REF], since the reconstruction problem reduces to multicasting on all possible data collectors, the result follows from the results in network coding theory which are briefly discussed in Section II.

Lemma 4. For any information flow graph G compounded of initial devices that obtain α bits directly from the source S and of additional devices that join the graph in groups of t devices obtaining β from d existing devices and β from each of the other t -1 joining devices, any data collector DC that connects to a subset of k out-nodes of G satisfies: process described above. Consider a recovery scenario u ∈ P in which, a data collector DC connects to a subset of k nodes {x i,j out : (i, j) ∈ I}, where I is the set of contacted devices. As all incoming edges of DC have infinite capacity, we only examine cuts (U, Ū ) with S ∈ U and {x i,j out : (i, j) ∈ I} ⊂ Ū . Moreover some additional cases cannot happen since there is an order between x i,j in , x i,j coor and x i,j out (e.g., x i,j in ∈ Ū and x i,j coor ∈ U needs not be considered). Therefore, we only need to examine three cases in the rest of this proof.

mincut(S , DC ) ≥ (3) min u∈P   g-1 i=0 u i min{α, (d - i-1 j=0 u j )β + (t -u i )β }   with P = {u : 1 ≤ u i ≤ t ∧ g-1 i=0 u i = k}. Proof: Let us consider some graph G (see examples in
α α α α α α ∞ β α β ′ d{ t -1 ∞ β α β ′ d -1{ t -1 ∞ β α β ′ d -2{ t -1 β β β DC ∞ (b) G 2 for u = (1, 1, 1, . . . ) S . . . α α α α α α α β ′ β β β α α d{ d{ d{ β ′ β β β α d -2{ d -2{ d -2{ β ′ β β β α α α d -3{ d -3{ d -3{ β DC ∞ (c) G 3 for u = (2, 1, 3, . . . )
Let C denote the edges in the cut (i.e, the set of edges going from U to Ū ). Every directed acyclic graph has a topological sorting [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF], which is an ordering of its vertices such that the existence of an edge x → y implies x < y. In the rest of the analysis, we group nodes that were repaired simultaneously. Since nodes are sorted, nodes considered at one step cannot depend on nodes considered at the following steps.

First group. Let J 0 be a set of indexes such that {x 0,j out : j ∈ J 0 } are the topologically first output nodes in Ū corresponding to a first (same) repair. The set contains #{x 0,j out : j ∈ J 0 } = u 0 nodes. Consider a subset M 0 ⊂ J 0 of size m such that {x 0,j in : j ∈ M 0 } ⊂ U and {x 0,j in : j ∈ J 0 -M 0 } ⊂ Ū . m can take any value between 0 and u 0 .

First, consider the m nodes {x 0,j in : j ∈ M 0 }. For each node, x 0,j in ∈ U . We consider two cases.

• If x 0,j coor ∈ U , then x 0,j coor → x 0,j out ∈ C. The contribution to the cut is α.

• If x 0,j coor ∈ Ū , then x 0,j in → x 0,j coor ∈ C. The contribution to the cut is ∞.

Second, consider the u 0m other nodes {x 0,j in : j ∈ J 0 -M 0 } (third and last case: x i,j in , x i,j coor and x i,j out all belong to Ū ). For each node, the contribution comes from multiple sources.

• The cut contains d edges carrying β: since x 0,j out are the topologically first output nodes in Ū , edges come from output nodes in U .

• The cut contains t-u 0 +m edges carrying β thanks to the coordination step. The node x 0,j coor has t incoming edges x 0,k in → x 0,j coor . However, since #({x 0,k in } ∩ Ū ) = u 0m, the cut contains only t -(u 0m) such edges. Therefore, the total contribution of these nodes is

c 0 (m) ≥ m min(α, ∞) + (u 0 -m)(dβ + (t -u 0 + m)β )
Since the function c 0 is concave on the interval [0 : u 0 ], the contribution can be bounded thanks to Jensen's inequality. 1,j out : j ∈ J 1 } be the topologically second output nodes in Ū corresponding to a second (same) repair. We follow a similar reasoning.

c 0 (m) ≥ u 0 min{α, dβ + (t -u 0 )β } Second group. Let {x
First, consider the m nodes {x 1,j in : j ∈ M 1 } ⊂ U . Similarly to the above, the contribution of each node is min(α, ∞).

Second, consider the u 0m nodes {x 1,j in : j ∈ J 1 -M 1 } ⊂ Ū . For each node, the contribution comes from multiple sources.

• The cut contains at least du 0 edges carrying β: since x 1,j out are the topologically second output nodes in Ū , at most u 0 edges come from output nodes in Ū , and at least du 0 other edges come from output nodes in U and are in the cut.

• Similarly to the above, the cut contains tu 1 + m edges carrying β thanks to the coordination step. Therefore, the total contribution of these nodes is

c 1 (m) ≥ u 1 min{α, (d -u 0 )β + (t -u 1 )β } i-th group.
Following the same reasoning, we find that the i-th group of nodes (i = 0, . . . , g -1) in the sorted set Ū contributes

c i (m) ≥ u i min{α, (d - i-1 j=0 u j )β + (t -u i )β }
Summing these contributions for all i, and considering the worst case for u ∈ P leads to [START_REF] Ghemawat | The Google File System[END_REF].

Proof of Theorem 1: From Lemmas 3 and 4, a code is correct if it satisfies (1) and ( 2).

γ = dβ + (t -1)β (1)
∀u, such that

g-1 i=0 u i = k and 1 ≤ u i ≤ t, g-1 i=0 u i min{α, (d - i-1 j=0 u j )β + (t -u i )β } ≥ M (2)
From Lemma 2, a code is correct only if mincut(S, DC) ≥ M. Moreover, for any set of parameter (n, k, d, t, α, β, β ) and any scenario u, we can find a graph G u such that mincut(S, DC) = u i min{α, (d-

u j )β + (t-u i )β } (4)
The graph G u is built using the process described here after.

• The data collector gets all bits from a set U of k devices.

• The contacted devices repaired simultaneously are grouped in subsets U i of size u i such that U = g-1 i=0 U i . • Each device x ∈ U i gets β bits from all devices in i-1 j=0 U j , β from u i -1 devices taking part to the reconstruction, β from d -i-1 j=0 u j devices not in U , β from tu i devices not taking part to the reconstruction. Hence, a code is correct if and only if (1) and ( 2) are satisfied.

A code minimizing (α, γ) under constraints of ( 1) and ( 2) is optimal as any code with (ᾱ, γ) < (α, γ) would not satisfy at least one constraint and hence would not be correct.

D. Optimal tradeoffs

Determining the optimal tradeoffs boils down to minimizing storage cost α and repair cost γ, as defined by (1), under constraints of (2). k, d and t are constants and α, β and β are parameters to be optimized. In this subsection, we provide optimal tradeoffs (α, γ) between storage cost and repair cost (bandwidth).

1) MBCR codes: Minimum Bandwidth Coordinated Regenerating Codes correspond to optimal codes that provide the lowest possible repair cost (bandwidth consumption) γ while minimizing the storage cost α. Figure 10 compares MBCR codes to both Dimakis et al. 's MBR [START_REF]Network Coding for Distributed Storage Systems[END_REF] and erasure correcting codes with delayed repairs (ECC). Note that similarly to MBR, there is no expansion since every bit received is stored (i.e., α = γ).

α = M k 2d + t -1 2d -k + t β = M k 2 2d -k + t β = M k 1 2d -k + t
We determine the values for MBCR codes in two step. We study two particular cuts and find the minimal values required to ensure that the quantity of information going through the cuts is at least equal to the file size (thus proving the optimality of the solution if it is correct). We then prove that these quantities are enough for all possible cuts.

Proof of MBCR (Optimality): Let us consider two particular successions of repairs leading to the graphs shown on Figure 8. The repairs corresponding to such graphs are described in the Proof of Theorem 1. As we want to minimize γ before α, we assume α ≥ dβ + (t -1)β (i.e., the stored amount is always larger than the downloaded amount).

When ∀i, u i = t (Fig. 8a), it is required that

k/t-1 i=0 t   (d - i-1 j=0 t)β   ≥ M
which is equivalent to

β ≥ M k 2 2d -k + t When ∀i, u i = 1 (Fig. 8b), it is required that k-1 i=0   (d - i-1 j=0 1)β + (t -1)β   ≥ M which is equivalent to β ≥ 1 t -1 M k -β 2d -k + 1 2
If we consider the smallest possible value β =

1 t-1 M k -β 2d-k+1 2 , the associated repair cost is γ = M k + k-1 2 β.
The repair cost hence grows linearly with β. Hence, we should minimize β. The minimum value for β is

β = M k 2 2d-k+t .
Since lower values would lead to incorrect repair for the graphs depicted on Figure 8, these values are optimal.

Proof of MBCR (Correctness): We have proved that the aforementioned values are required for two particular cuts. We now prove that such values ensure that enough information flow through every cut and, hence, is correct. According to Theorem 1, the following condition is sufficient for the code to be correct. We show that the constraint is satisfied when α, β and β take the values defined for MBCR codes.

g-1 i=0   u i min{(d - i-1 j=0 u j )β + (t -u i )β , α}   ≥ M
since α (the stored part) is always larger than or equal to the transmitted data,

g-1 i=0 u i   (d - i-1 j=0 u j )β + (t -u i )β   ≥ M
replacing α, β and β by their values,

g-1 i=0 u i   (d - i-1 j=0 u j )2 + (t -u i )   ≥ k(2d -k + t)
which is equivalent to,

(2d + t) g-1 i=0 u i -2 g-1 i=0 u i i-1 j=0 u j - g-1 i=0 u 2 i ≥ k(2d -k + t) (2d + t) g-1 i=0 u i - g-1 i=0 u i 2 ≥ k(2d -k + t) as k = g-1 i=0 u i , it simplifies to (2d + t)k -k 2 ≥ k(2d -k + t)
which is always true. Hence, minimum bandwidth regenerating codes are correct. 2) MSCR codes: Minimum Storage Coordinated Regenerating Codes correspond to optimal codes that provide the lowest possible storage cost α while minimizing the repair cost γ. This point has been independently characterized by Hu et al. in [START_REF] Hu | Cooperative Recovery of Distributed Storage Systems from Multiple Losses with Network Coding[END_REF]; however, they assume that β = β without proving it. We present a simple derivation from Theorem 1 allowing to characterize this point. Figure 10 compares MSCR codes to both Dimakis et al.'s MSR [START_REF]Network Coding for Distributed Storage Systems[END_REF] and erasure correcting codes with delayed repairs (ECC). Note that for d = k, our MSCR codes share the same repair cost as erasure correcting codes delayed repair. Yet, in this case, our codes still have the advantage that they balance the load evenly thus avoiding bottlenecks.

α = M k β = M k 1 d -k + t β = M k 1 d -k + t
Proof of MSCR (Optimality): Let us consider two particular successions of repairs leading to the graphs shown on Figure 8. The repairs corresponding to such graphs are described in the Proof of Theorem 1.

We minimize α first. It is clear that α = M k is minimal since α < M k makes impossible to reconstruct a file of size M using only k blocks. Hence, what is important is now that each element of the sum is at least equal to M k .

∀i ∈ 0 . . . g -1, (d - i-1 j=0 u i )β + (t -u i )β ≥ M k When ∀i, u i = t (Fig. 8a), it is required that ∀i ∈ 0 . . . k/t -1, (d - i-1 j=0 t)β ≥ M k which is equivalent to β ≥ M k 1 d -k + t When ∀i, u i = 1 (Fig. 8b), it is required that ∀i ∈ 0 . . . k -1, (d - i-1 j=0 1)β + (t -1)β ≥ M k which is equivalent to β ≥ 1 (t -1) ( M k -β(d -k + 1))
If we consider the smallest possible value β = 1 (t-1) ( M kβ(dk + 1)), the associated repair cost is γ = M k + (k -1)β. The repair cost hence grows linearly with β. Hence, we should minimize β. The minimum value for

β is β = M k 1 d-k+t .
Since lower values would lead to incorrect repair for the graphs depicted on Figure 8, these values are optimal.

Proof of MSCR (Correctness): The proof of correctness is quite similar to the previous one. It consists in proving that

g-1 i=0 u i min{α, (d - i-1 j=0 u j )β + (t -u i )β } ≥ M
is always verified when α, β and β take the aforementioned values.

Since each element of the sum is at most u i M k , each element of the sum must satisfy the following constraint.

∀i < g, min{ M k , (d - i-1 j=0 u j )β + (t -u i )β } ≥ M k which simplifies to ∀i < g, (d - i-1 j=0 u j )β + (t -u i )β ≥ M k Applying values for MSCR codes, ∀i < g, 1 d -k + t (d i - i-1 j=0 u j + (t -u i )) ≥ 1 ∀i < g, d - i j=0 u j + t i ≥ d -k + t which is satisfied if ∀i ≤ g, i j=0 u j ≤ k
which is true since g-1 j=0 u j = k and u j > 0. Therefore, MSCR codes are correct. 3) General CR codes: The general case corresponds to all possible trade-offs in between MSCR and MBCR. Valid points (α, β, β ) can be determined by performing a numerical optimization of the objective function. Figure 11 shows the optimal tradeoffs (α, γ): coordinated regenerating codes (t > 1) can go beyond the optimal tradeoffs for independent repairs (t = 1) defined by regenerating codes by Dimakis et al. [START_REF]Network Coding for Distributed Storage Systems[END_REF].

E. Optimal threshold

As previously explained, in regenerating codes, the higher the number of devices being contacted d, the higher the savings on the repair cost γ. Moreover, when repairs are delayed, higher values for the number of devices being repaired t lead to higher savings on the repair cost γ. If we consider a system of constant size n = d+t, these two objectives are contradictory: the longer the delay, the lower the number of live devices d. An interesting question is what is the optimal threshold t for triggering repairs assuming that d + t is constant (i.e., is it useful to deliberately delay repairs?). This question is addressed hereafter by studying how MBCR codes and MSCR codes behave as t changes in a system of constant size.

Theorem 5. If we consider a system of size n = d + t, for MBCR codes, the optimal value is t = 1 while for MSCR codes any value t ∈ {1 . . . n -k} is optimal.

Proof: Let us consider the repair cost assuming that n = d + t is constant. For MBCR codes, the cost γ = M k 2n-t-1 2n-k-t increases when t increases. The optimal value of t for MBCR codes is the lowest possible value (i.e., t = 1). For MSCR codes, the cost γ = M k n-1 n-k does not depend on t. The repair cost of MSCR remains constant, and t can be set to any value as there is no optimum. Neither MSCR nor MBCR allow additional gains when deliberately delaying repairs (i.e., deliberately setting t > 1). Corollary 6. If we consider a system of size n = d + t where t can be freely chosen (i.e., the value of t is not constrained by the system) both MSR and MBR regenerating codes [START_REF]Network Coding for Distributed Storage Systems[END_REF] are optimal. Hence deliberately delaying repairs to force high values for t does not bring additional savings.

However, if several failures are detected simultaneously, coordinated regenerating codes remain more efficient as they leverage simultaneous failures by coordinating during repairs.

IV. ADAPTIVE REGENERATING CODES

In the previous section, we presented coordinated regenerating codes that assume t and d to remain constant across repairs. This is similar to regenerating codes [START_REF]Network Coding for Distributed Storage Systems[END_REF], in which d remains constant across repairs. Yet, in real systems, it is not realistic to assume that the failure rate remains constant over time, and to assume that every single failure can be repaired before a second one occurs.

In the particular case of Minimum Storage (α = M k ), such strong assumptions are not needed. Indeed, when minimizing the sum in (2), we can minimize the different elements of the sum, which correspond to repairs, independently. Therefore, repairs are independent. We propose to adapt the quantities to transfer β and β to the system state which is defined by the number t of devices being repaired and the number d of live devices.

Adaptive regenerating codes simplify the design of a system based on regenerating codes. Indeed, when designing such a system, at least two parameters must be fixed: the number k of devices needed to recover the file and the number d of devices needed to repair a file. The higher the d is, the lower the repair cost is. Hence, d should be chosen as high as possible. Yet, if less than d devices are alive, regenerating

C. Implementation

Our approach also has significant advantages over the MFR approach with respect to the implementation. The implementations are similar in principle to the one described in Subsection III-A and Figure 6. The only difference is that the values d and t may differ from one repair to the other. Each device stores sub-blocks of data and combines them to send the appropriate quantities of information. To be able to send β = 2 3 M k , each device must store z = 3 sub-blocks. To be able to send

β = 1 3 M k or β = 1 4 M
k , each device must store z = lcm {3, 4} = 12 sub-blocks. Hence, the length of any random linear code used to implement such a system is l = zk where z is the number of sub-blocks stored by each device. We now consider a system of constant size n = d + t and compare both implementations.

The implementation of the MFR approach implies that to support d ∈ {k . . . n -1}, each device must be able to send all quantities β ∈ {

1 1 M k . . . 1 n-k M k }. Hence, z = lcm {1 . . . n -k}. It can be shown that 2 n-k ≤ z ≤ 3 n-k .
Hence, the length of the codes required to implement such codes grows exponentially with nk.

The implementation of our approach implies that to support d ∈ {k . . . n -1}, each device must be able to send quantities

β = 1 n-k M k and β = 1 n-k M k . Hence, z = n -k.
Hence, the length of the codes required to implement such codes grows linearly with nk.

Even though simple adaptive regenerating codes (MFR) can be built from Dimakis et al.'s MSR codes, our adaptive regenerating codes have two clear advantages. First, their repair cost is always lower than any other approach (i.e., optimal) and is constant on systems of constant size. Second, an optimal implementation of our adaptive regenerating codes requires much shorter codes (i.e. smaller l). This is very important since l has a direct impact on the complexity of all operations (encoding, recoding, and decoding).

V. RELATED WORK

As already explained, our coordinated and adaptive regenerating codes, which allow optimal simultaneous repairs, outperform both regenerating codes [START_REF]Network Coding for Distributed Storage Systems[END_REF] and erasure correcting codes with lazy repairs [START_REF] Bhagwan | Total Recall: System Support for Automated Availability Management[END_REF], [START_REF] Datta | Internet-scale storage systems under churn -A Study of steady-state using Markov models[END_REF], [START_REF] Dalle | Analysis of Failure Correlation Impact on Peer-to-Peer Storage Systems[END_REF]. Another approach aiming at reducing the repair costs consists in contacting less devices while still downloading the same amount from each device [START_REF] Duminuco | Hierarchical Codes: How to Make Erasure Codes Attractive for Peer-to-Peer Systems[END_REF], [START_REF] Oggier | Self-repairing Homomorphic Codes for Distributed Storage Systems[END_REF]. Such approach requires structuring the code so that encoded blocks can be recovered without decoding by combining a few other encoded blocks. Even though this approach offers a reasonably low repair cost, it is neither optimal in storage nor optimal in repair cost. Moreover, these studies provide storage and repair costs that apply only to the specific codes proposed.

Regenerating codes [START_REF]Network Coding for Distributed Storage Systems[END_REF] and coordinated regenerating codes presented in this paper assume a symmetric role for all devices (i.e., they all transfer the same amounts of information). Since network connections between every device may not be equivalent, it is interesting to adapt the repair strategy to take into account the underlying network topology. A first study [START_REF] Li | Tree-structured Data Regeneration in Distributed Storage Systems with Regenerating Codes[END_REF] has focused on structuring the repair as a tree instead of a star. Indeed, with regenerating codes, repairs are performed by having the repaired device download directly from live devices. In [START_REF] Li | Tree-structured Data Regeneration in Distributed Storage Systems with Regenerating Codes[END_REF], a first live device can receive information from a second live device so as to forward this information to the repaired device. This is of interest in systems where devices are connected in a mesh network and cannot contact all other devices directly. In such case, this can avoid a potential bottleneck link between a live device and the repaired device. However, in our study, we assumed the most frequent case where all devices are connected to a regular network (e.g., a peer-to-peer system) allowing direct connection from one device to all other devices. Another study [START_REF] Shah | Explicit Codes Minimizing Repair Bandwidth for Distributed Storage[END_REF] has focused on downloading unequal amounts of information from other devices during repairs. They define the total amount of information that must be downloaded depending on the maximum amount of information that can be downloaded from each device. They show that the lowest repair cost is offered when all devices download the same amount of data (i.e., regular regenerating codes). This last study can also be applied to our codes and would show that allowing unequal downloads (i.e., non symmetric system) would also increase the global repair cost.

Independently from our result, the work [START_REF] Hu | Cooperative Recovery of Distributed Storage Systems from Multiple Losses with Network Coding[END_REF] addresses a subset of the problem we consider. They notice that regenerating codes can only repair single failures and come up with a solution that can handle multiple failures. They naturally define a similar repair method (i.e., they add a coordination step to the information flow graph). Yet, their solution is much more limited than ours as they only study the Minimum Storage case (MSR). Not only, we also study the Minimum Bandwidth (MBR) point, but this cannot be covered by their model since they assume all transfers are equal (i.e., β = β ). Finally, we also determine numerically the general case (i.e., points between Minimum Storage (MSR) and Minimum Bandwidth (MBR) points). Their paper is also restrictive with respect to system they consider as, they assume a system of constant size where all devices are involved (i.e., n = d + t). Finally, we do build upon our result to define an adaptive form of regenerating codes that is more flexible to use in practical systems while they do not consider such constructions. Hence, the previously published paper [START_REF] Hu | Cooperative Recovery of Distributed Storage Systems from Multiple Losses with Network Coding[END_REF], which is yet another proof of the importance of the considered problem, covers only a subset of our results even if it shares both the problem and some tools used (an adaptation of Information Flow Graphs from Dimakis et al. [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF], [START_REF]Network Coding for Distributed Storage Systems[END_REF]) .

VI. CONCLUSION

In this paper, we have proposed novel and optimal coordinated regenerating codes by considering simultaneous repairs in regenerating codes. This work has both theoretical and practical impacts. From a theoretical standpoint, we proved that deliberately delaying repairs cannot provide further gain in term of communication costs. In practical systems, however, where several failures are detected simultaneously, our coordinated regenerating codes outperform regenerating codes [START_REF]Network Coding for Distributed Storage Systems[END_REF] and are optimal. We also proposed adaptive regenerating codes that allow adapting the repair strategy to the current state of the system so that it always performs repairs optimally. For both codes, we provided and proved the minimum amounts of information that need to be transfered during the repair thus defining the fundamental tradeoffs between storage and repair costs for coordinately repairing multiple failures. Finally, our coordinated regenerating codes can also be viewed as a global class of codes that encompass erasure correcting codes with delayed repairs (d = k), regenerating codes (t = 1), erasure correcting codes (t = 1 and d = k), and new codes (t > 1 and d > k) that combine, previously incompatible, existing approaches of regenerating codes and delayed repairs (cf. Figure 4).

So far, our study has focused on the theoretical framework for performing multiple coordinated repairs in distributed storage. A straightforward implementation of such codes relies on random linear network codes (cf. Figure 6). Coordinated regenerating codes can therefore be used as they are for selfhealing distributed storage. Yet, the seminal paper on regenerating codes [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF] has been followed by studies of more constrained repairs (deterministic repairs known as exact repairs by opposition with functional repairs studied in this paper). In short, in functional repairs, the regenerated redundancy is not necessarily the same as the lost one while, in exact repairs, the regenerated redundancy is exactly the same as the lost one. A recent survey [START_REF] Dimakis | A Survey on Network Codes for Distributed Storage[END_REF] details the various works on exact repairs. Since our coordinated regenerating codes only consider the problem of functional repair (i.e., they leave open the problem of coordinated exact repair), an interesting extension of this work would be to study deterministic coordinated regenerating codes performing exact repair. Indeed, they would have appealing properties (simpler integrity checking, lower decoding complexity) when compared to coordinated regenerating codes based upon random linear network codes.

Figure 1 .

 1 Figure 1. Repairing failures with codes. In a n device network, failed devices are replaced by new ones. The new devices get a given amount of data from live devices to repair the redundancy. In our examples, k = 3, d = 4, B = 1, α = 1, and β = 1/2. Some example of gains for k = 32 are given in Table I

Figure 2 .

 2 Figure 2. Delaying repairs allows performing multiple repairs at once.

Figure 3 .

 3 Figure 3. Regenerating codes (MSR or MBR) offer improved performances when compared to erasure correcting codes (EC)

  for a minimum storage cost α = M k , and MBR (Minimum Bandwidth Regenerating codes) offer optimal storage cost α = M

Figure 4 .

 4 Figure 4. Our coordinated regenerating codes encompass all existing codes. Moreover, they allow the repair of multiple devices at once without decoding.

1 Figure 5 .

 15 Figure 5. Repairing failures in coordinated regenerating codes. In a network of n devices storing α bits, when t devices have failed, t new devices collect β bits from d live devices. They coordinate by exchanging (t -1)β bits with other new devices and store α bits.

Figure 6 .

 6 Figure 6. Coordinated regenerating codes based on linear codes. The system stores a file X and is compound of 5 devices. Device i stores 3 sub-blocks {y i,1 , y i,3 , y i,3 }. Devices 4 and 5 fail and are replaced by devices 6 and 7.

Figure 7 .

 7 Figure 7. Information flow graph of a of t = 3 devices. The internal nodes of the graph represent intermediary steps in the repair. First, each device collects β from d live devices. Second, devices coordinate by exchanging β with each other. Third, they store α. Plain edges correspond to network communication and dashed edges correspond to local communication.

Figure 8 )

 8 formed by adding devices according to the repair S

  α

Figure 8 .

 8 Figure 8. Information flow graphs for which bounds in (2) are matched with equality for some u.

Figure 9 .

 9 Figure 9. Total repair cost tγ for d = 48 and k = 32. MBCR codes permanently outperform both erasure correcting codes and regenerating codes

Figure 10 .

 10 Figure 10. Total repair cost tγ for d = 48 and k = 32. MSCR codes permanently outperform both erasure correcting codes and regenerating codes

Figure 11 .

 11 Figure 11. Optimal tradeoffs between storage and repair costs for k = 16 and d = 24. Regenerating codes (RC) [10] are depicted as t = 1. For each t, both MSCR and MBCR are shown. Costs are normalized by M/k.

Figure 12 .

 12 Figure 12. Average repair cost γ for n = 64 and k = 32. Adaptive Regenerating Codes (ARC) permanently outperform both erasure correcting codes (ECC) and the MFR codes.

Table I SOME

 I EXAMPLES OF REPAIRS OF CODES FOR A FILE OF 32 MB

	k	d	t	α	γ
	Erasure codes Erasure codes (delayed repair) 32 32 Dimakis et al.'s MSR 32 Dimakis et al.'s MBR 32 Our MSCR (cf. Sec. III-D2) 32 Our MBCR (cf. Sec. III-D1) 32	NA NA NA 4 36 NA 36 NA 36 4 36 4	1 MB 1 MB 1 MB 1.8 MB 1 MB 1.7 MB	32 MB 8.8 MB 7.2 MB 1.8 MB 4.9 MB 1.7 MB

In this paper, we always consider that (ā, b) < (a, b) means that either ā ≤ a and b < b, or ā < a and b ≤ b

We assume that t divides k, no result is known if t does not divide k.

codes cannot perform the repair, and the only proven but costly way to repair is to decode (gathering the whole file). Therefore, d should be fixed to reasonably low values (suboptimal) so that there are always at least d live devices. On the contrary, adaptive regenerating codes self-adapt by choosing, at each repair, the highest possible d (the lowest repair cost γ is achieved for the highest d). Hence, designing a system using adaptive regenerating codes implies setting only the right value for the parameter k thus leading to simpler designs.

A. Our approach

Theorem 7. Adaptive regenerating codes (k, Γ) are both correct and optimal. Γ is a function (t, d) → (β t,d , β t,d ) that maps a particular repair setting to the amounts of information to be transferred during a repair.

In this subsection, we prove they are correct and optimal.

Lemma 8. For any information flow graph G compounded of initial devices that obtain α bits directly from the source S and of additional devices that join the graph in groups of t i devices obtaining β ti,di from d i existing devices and β ti,di from each of the other t i -1 joining devices, any data collector DC that connects to a subset of k out-nodes of G satisfies:

The proof is similar to the proof of Lemma 4. Proof of Theorem 7 (Correctness): Using Lemmas 2, 3 and 8, we can define the following sufficient condition for the code to be correct. The condition is satisfied when β and β take the values defined in [START_REF] Bhagwan | Total Recall: System Support for Automated Availability Management[END_REF].

The condition must be satisfied for every u. For any u, since each element of the sum is at most u i M k , each element of the sum must satisfy the following constraint.

Applying formulas of (5), ∀i < g,

which is true since g-1 j=0 u j = k and u j > 0. Therefore, adaptive regenerating codes are correct.

Proof of Theorem 7 (Optimality): We prove by contradiction that the adaptive regenerating codes are optimal. Let us assume that there exists a correct code (k, Γ) such that Γ < Γ (i.e., for some (t, d), Γ(t, d) < Γ(t, d)). This is equivalent to (k, Γ) not being optimal.

Consider a set of failures such that all repairs are performed by groups of t devices downloading data from d devices. Consider the corresponding information flow graph. Assuming repairs are performed with a correct code (k, Γ), the information flow graph also corresponds to a correct code

). Moreover, according to the previous section, these failures can be repaired optimally using the MSCR code (d + t, k, t, d, α, β t,d , β t,d ). Therefore, there is a contradiction since the code (d + t, k, t, d, α, βt,d , β t,d ) cannot be correct if the code (d + t, k, t, d, α, β t,d , β t,d ) is optimal. A correct code (k, Γ) cannot exist, and the adaptive regenerating code (k, Γ) defined in this section is optimal.

Building on results from coordinated regenerating codes (especially MSCR), we have defined adaptive regenerating codes and proved that they are both correct and optimal. These codes are of particular interest for dynamic systems where failures may occur randomly and simultaneously.

B. Performance

We compare our approach to MFR codes defined in [START_REF] Wang | MFR: Multi-Loss Flexible Recovery in Distributed Storage Systems[END_REF]. This approach is built upon MSR codes defined by Dimakis et al. in [START_REF]Network Coding for Distributed Storage Systems[END_REF]. The coding scheme can be described as (k, Γ ) where Γ is a function d → β d . The t repairs needed are performed independently.

Let us consider the particular case where d + t = n. The average cost per repair of our codes remains constant γ = M k n-1 n-k . In the MFR approach, which requires repairs to be performed independently, the average repair cost γ = M k n-t n-t-k+1 increases with t. Therefore, the performance of our adaptive regenerating codes does not degrade as the number of failures increases, as opposed to the MFR constructed upon Dimakis et al. 's codes. This is also shown on Figure 12


AGOUZAL Abdelatif

Thierry Lafouge

On the relation between the Maximum Entropy Principle and the Principle of Least Effort: the continuous case

Keywords: Maximum Entropy Principle, Principle of Least Effort, Effort function, Inverse power function

The Maximum Entropy Principle (MEP) maximises the entropy provided that the effort remains constant. The Principle of Least Effort (PLE) minimises the effort provided that the entropy remains constant. The paper investigates the relation between these two principles. In some kinds of effort functions, called admissible, it is shown that these two principles are equivalent. The results are illustrated by the size-frequency statistical distribution met in infometry in Information Production Processes.

Introduction

The article is divided into two parts. In the first, through the signal theory, we mathematically formulate the equivalence of the two principles, Maximum Entropy Principle with constant effort, and the Principle of Least Effort with constant entropy. Then we situate these problems within the processes of producing and using information in infometry. In the second part, we mathematically demonstrate equivalence by introducing the concept of admissible effort function. To conclude, we return to the information production processes to clarify the properties of the usual functions that model the information production processes.

1

Definitions and context

Information theory

In 1948 Shannon (Shanon, 1993) worked out a statistical theory on the transmission of electrical signals. This statistical theory of information stipulates that the more the states of a system are equiprobable, the more the process produces information. The theoretical bases used in this article come from this theory. Here, we uniquely consider density functions of ) , ( f µ , we define two quantities, H1 average information content, called entropy and F average effort:

∫ ∫ ∞ ∞ = - = 1 1 , ) ( ) ( , )) ( ( ) ( dx x x f F dx x Ln x f H µ µ
F is necessarily positive. Let us now define two important optimization principles: Maximum Entropy Principle (MEP) and Principle of Least Effort (PLE). Maximum Entropy Principle (MEP)

The MEP maximises the entropy provided that the effort remains constant. Principle of Least Effort (PLE)

The PLE minimises the effort provided that the entropy remains constant. Mathematical formulation of the two principles With H , F positive, two real numbers, and f an effort function, we define the sets of functions:

∫ ∫ ∞ ∞ - = = ≥ = Α 1 1 ) ( ( ) ( , 1 ) ( , 0 ) ( dx x Ln x H dx x H µ µ µ µ ∫ ∫ ∞ ∞ = = ≥ = 1 1 ) ( ) ( , 1 ) ( , 0 ) ( dx x f x F dx x F C µ µ µ
With these notations, MEP and PLE are written:

∫ ∞ ∈ - ⇔ 1 ) ( ) )) ( ( ) ( ( dx x Ln x Max MEP F C µ µ µ ∫ ∞ ∈ ⇔ 1 ) ( ) ) ( ) ( ( dx x f x Min LEP H A µ µ
Our aim is to show, under certain conditions, that these two principles are equivalent. We will situate the problem within the sphere of infometry and recall results obtained in earlier work.

Informetrics and entropy aspects

Information Production Process and Inverse power law

Statistical regularities observed in producing or using information have been studied for a long time. In practice, the production function has similar characteristics in very diverse situations of production or use of information.

3

These models can be represented by the diagram of Fig. 1, introduced into informetric systems by Leo Egghe [START_REF] Egghe | On the duality of informetric systems with application to the empirical law[END_REF] and called "Information Production Process" (IPP). An IPP is a triplet made up of a bibliographical source, a production function, and all the elements (items) produced. In all quoted examples, if we quantify the production of the items by the sources with a size frequency function, this one is decreasing with a long tail and a gap between a high number of sources producing few items and a small number of sources producing a lot. Their most current mathematical formulation is that of an inverse power function, usually called a lotkaian informetric distribution [START_REF] Egghe | Power laws in the information production process: Lotkaian Informetrics[END_REF], the corresponding density probability λ ν is:

[ [ ∞ ∈ ,.. 1 x , 1 , 1 ) ( > - = λ λ ν λ λ x x
The calculation of the entropy [START_REF] Yablonsky | On fundamental regularities of the distribution of scientific productivity[END_REF] ) (λ H according to λ gives:

1 , 1 ) 1 1 ( ) ( > - + - = λ λ λ λ λ Ln

H

It is easy to show that the entropy is a decreasing function of λ . The classical interpretation of Lotka's law [START_REF] Lotka | The frequency distribution of scientific productivity[END_REF] is found, e.g. the higher λ is, the bigger is the gap between the number of scientists who produce a lot compared to the number of scientists who produce a little, knowing that there are few scientists who produce a lot compared to the number of scientists who produce a little. Thus, the two following questions arise:

s 1 s 2 s 3 i 1 i 2 i 3

Sources

Production Items 1) For a given quantity of effort, what is the connection between the random distribution of the sources and the effort function when the quantity of information produced by the sources is maximized?

2)

For a given quantity of information, what is the connection between the random distribution of the sources and the effort function when the quantity of effort produced by the source is maximized?

Previous results

Finite discrete case

Suppose µ is a finite discrete distribution, so we have . In () we prove the following result, if we suppose m p p p ,.., , 2 1 is a decreasing sequence MEP and PLE are equivalent. In the conclusion to this article we provided a complete explanation of Zip's law [START_REF] Egghe | On the Relation Between the Maximum Entropy Principle and the Principle of Least Effort[END_REF] or Lotka's law as a decreasing function.

An incomplete demonstration of the result of equivalence in the continuous case was subsequently proposed (see paragraph 1.2.2.2). The aim of this article is to generalize this result.

1.2.2.2

Exponential Informetric Process In Lafouge and Prime Claverie [START_REF] Lafouge | Production and use of information characterization of informetric distributions using effort function and density function[END_REF] we assume that an item produced requires a certain amount of effort and therefore we define the exponential informetric process by introducing the effort function (see Fig. 2). The effort function denotes the amount of effort from a source to produce items.

s 1 s 2 s 3 i 1 i 2 i 3

Sources

Effort Items

∞ < - ∫ ∞ 1 )) ( exp( ) ( dx x f x f λ [1]
Since f is strictly increasing, unbounded, we can easily show the condition:

∫ ∞ ∞ < - 1 )) ( exp( dx x f
λ Therefore, we call the following density function Exponential Informetric Process:

∫ ∞ - - = 1 )) ( exp( )) ( exp( ) ( dx x f x f x λ λ ν λ ∫ ∞ 1 ) ( ) ( dx x x f λ ν
corresponds to the average F of effort produced by the Exponential Informetric Process. The following results explain the relationship between average amount of effort and entropy. We have shown [START_REF] Lafouge | Production and use of information characterization of informetric distributions using effort function and density function[END_REF] the following results:

(i) λ ν is decreasing, (ii)
The two principles maximum MEP and PLE are verified simultaneously, (iii) This result partly resolves the problem of the equivalence of the two principles given in paragraph 1.1. In fact, the condition is sufficient for these two principles to be equivalent. In the two preceding demonstrations, finite and discrete cases (equivalence) and in the continuous case (sufficient condition), we calculate a solution for the MEP that plays a central role in mechanical statistic,

F k Ln H λ + = ) ( where ∫ ∞ - = 1 )) ( exp( dx x f k
)) ( exp( ) ( x f C x λ ν - =
where C is a constant, λ a positive number and f an effort function. This distribution, constructed with the MEP, is known under the name of Bolzmann distribution. To our knowledge, there is no mathematical demonstration of the equivalence of these two principles (MEP and PLE) in the continuous case. Note Demonstration (ii) of the preceding result supposes, when we write the equality

∫ ∞ - = 1 )) ( exp( ) ( dx x f x f F λ
, the existence of a unique λ verifying this inequality. The demonstration given in paragraph 2 will clarify this point.

Effort function and inverse power law

With the preceding formalism, the density function corresponding to an inverse power is written:

[ [ ∞ ∈ ,.. 1 x , 1 , )) ( ) 1 ( exp( ) 1 ( ) ( > - - - = λ λ λ ν λ x Ln x
The calculation of the amount of effort according to λ gives:

1 , 1 1 ) ( > - = λ λ λ

F

The logarithmic function is the effort function corresponding to the Lotka distributions. When we are interested for example in the production of words in a text and when we express this regularity using the formalism of Zipf's law (see Conclusion). In (Egghe and Lafouge, 2006, p 8), this hypothesis is formulated thus: the cost (effort) of using a word with

,....) 3 , 2 , 1 ( , = i i letters is proportional to i hence to ) (r Log N
where N is the number of different letters and r is the rank of a word with i letters.

Moreover the results presented in [START_REF] Lafouge | An interpretation of the effort function trough the mathematical formalism of Exponential Informetric Process[END_REF] show that if an effort function f verifies the condition,

1 , ) ( ) ( > = ∞ → λ λ x Ln x f Limit x
we have an Exponential Informetric Process. We will now directly demonstrate the equivalence of the two principles using the continuous case with effort functions, strictly increasing, unbounded and verifying the condition [1].

Characterising the Maximum Entropy Principle in terms of the Principle of Least Effort

Main results

Preliminary and notation

In all that follows f denotes a strictly increasing unbounded, effort function . f will be called admissible if there is also a real number 0

λ verifying the condition ∫ ∞ ∞ < - 1 0 )) ( exp( ) ( dx x f x f λ Lemma 2.0
With f an admissible effort function, there exists a reality 0

) ( ≥ f σ so that ∫ ∞ ∞ < - ≤ > ∀ 1 )) ( exp( ) ( 0 ), ( dx x f x f f λ σ λ Proof f being admissible, there exists ℜ ∈ 0 λ so that ∫ ∞ ∞ < - ≤ 1 0 )) ( exp( ) ( 0 dx x f x f λ f being increasing 0 λ λ > ∀ we have, ∫ ∫ ∞ ∞ ∞ < - < - ≤ 1 1 0 )) ( exp( ) ( )) ( exp( ) ( 0 dx x f x f dx x f x f λ λ Moreover, it is clear that ∫ ∞ ∞ + = 1 ) ( dx x f
, consequently 0 λ is strictly positive. We can then define the following real number:

∫ ∞ ∞ < - < > = 1 )) ( exp( ) ( 0 , 0 inf ) ( dx x f x f f λ λ σ
We will now define two functions H and F quantifying the entropy and effort of a density function µ ,

∫ ∞ = 1 1 ) ( dx x ν We define the entropy of µ , ∫ ∞ - = 1 )) ( ( ) ( ) ( dx x Ln x H µ µ µ
which can be infinite and the quantity of effort of µ ,

∫ ∞ = 1 ) ( ) ( ) ( dx x f x F µ µ Let H and F two constants, ) (H A and ) (F C the set of functions defined in the introduction, ) ( f σ λ > ∀ we put: ∫ ∞ - = 1 )) ( exp( dx x f k λ k x f x )) ( exp( ) ( λ ν λ - = ∫ ∞ - = 1 )) ( ( ) ( ) ( dx x Ln x H λ λ ν ν λ ∫ ∞ = 1 ) ( ) ( ) ( dx x x f F λ ν λ
The following results are simple consequences of the preceding definitions.

Lemma 2.1 ), ( f σ λ > ∀ the entropy ) (λ H of λ ν is finite. Proof ∫ ∫ ∞ ∞ + - = - - - = 1 1 )) ( ) ( ))( ( exp( 1 ) )) ( exp( ( )) ( exp( 1 ) ( dx k Ln x f x f k dx k x f Ln x f k H λ λ λ λ λ ) (k Ln F + = λ
Also, the two functions are defined:

∫ ∞ - - - = 1 )) ) ( ( exp( ( ) ( dx F x f Ln Z λ λ ∫ ∞ - - - = 1 ) ) ) ( exp( ( 1 ) ( dx H x f Ln R λ λ λ Lemma 2.2 With ) (F C ∈ µ , ) ( f σ λ > , we have: ∫ ∞ = 1 ) ( )) ( ( ) ( λ ν µ λ Z dx x Ln x Proof ∫ ∫ ∫ ∞ ∞ ∞ - - - = 1 1 1 ) )) ( exp( ( ) ( )( ( )) ( ( ) ( dx dx x f Ln x f x dx x Ln x λ λ µ ν µ λ ) ) ( exp( ) (exp( ) )) ( exp( ( . 1 1 ∫ ∫ ∞ ∞ - - = - - - = dx x f F Ln dx x f Ln F λ λ λ λ dx F x f Ln )) ) ( ( exp( ( 1 ∫ ∞ - - - = λ Lemma 2.3 Let ) (F C ∈ λ ν , we have 0 )) ( exp( ) ) ( ( 1 = - - ∫ ∞ dx x f F x f λ Proof ) (F C ∈ λ ν , hence F k dx x f x f = - ∫ ∞ 1 )) ( exp( ) ( λ ∫ ∫ ∞ ∞ - - = - - 1 1 )) ( exp( ) ( )) ( exp( ) ) ( ( F k dx x f x f dx x f F x f λ λ 0 = - = F k F k

Equivalence theorem

We can now state the equivalence theorem of the two principles by characterizing the solutions of the MEP and the PLE using the functions

) (λ Z and ) (λ R .

Theorem

With f an admissible effort function, we have the following results:

(i) ) ( ) ( )) ( ( ) ( 0 f F C Z Sup H Max σ λ µ λ µ > ∈ ≥ ≥ Also, if there is a a real number 0 λ so that ) ( 0 F C ∈ λ ν
then this real number is unique and we have:

) ( )) ( ( ) ( ) ( 0 ) ( ) ( 0 λ λ µ λ σ λ µ Z Z Sup H Max H f F C = = = > ∈ (ii) ) ( ) ( )) ( ( ) ( 0 f H A R Sup F Min σ λ µ λ µ > ∈ ≥ ≥ Also, if there is a a real number 1 λ so that ) ( 1 H A ∈ λ ν
then this real number is unique and we have:

) ( )) ( ( ) ( ) ( 1 ) ( ) ( 1 λ λ µ λ σ λ µ R R Sup MinF F f H A = = = > ∈ (iii) If ) ( 1 λ Z H - = or ) ( 0 λ R F = then 1 0 λ λ ν ν = (i)
characterizes the solution of the MEP, in other words maximizing the entropy subject to a constant effort, (ii) characterizes the solution of the PLE, in other words minimizing the effort subject to constant entropy. Finally, if the information content H and quantity of effort F are linked, in other words if

) ( 1 λ Z H - = or if ) ( 0 λ R F =
, the two principles are equivalent. We note that in this case we find the result (iii) of paragraph 1.2.2.2,

) ( 1 k Ln F H + = λ or ) ( 0 k Ln F H + = λ
.

Before solving this problem, we will give arguments by a formal result to demonstrate (i) as follows.

We have,

∫ ∫ ∞ ∞ - - - - - = 1 1 )) ) ( ( exp( )) ) ( ( exp( ) ( dx F x f dx F x f F f d dZ λ λ λ With ) ( 0 F C ∈ λ ν , according to lemma 2.3, we have λ d dZ ( 0 ) 0 = λ , which means that ) ( 0 λ Z is an extremum of function Z .

Demonstration of the equivalence theorem

Preliminary

For this problem to be of mathematical interest, we need to show that ) (H A and ) (F C are not empty and to suppose additional hypotheses regarding the effort function f so that the maximum entropy is finite. Readers should refer to points 1,2 and 3 in the appendix for these demonstrations.

We will solve this problem uniquely through the use of elementary analytical arguments.

Lemma 2.4

Let two real numbers 0 ≥ y and 0 > z , we have: For any admissible function, we have:

(i) ) ( ) ( z
) ( ) ( ) ( ) ( 0 f F C Z Sup H Max σ λ µ λ µ > ∈ ≥ ≥ Proof With ) (F C ∈ µ , ) ( f σ λ > using the result (i) of lemma 2.
∫ ∫ ∫ ∞ ∞ ∞ + - ≥ 1 1 1 )) ( ( ) ( )) ( ) ( ( )) ( ( ) ( dx x Ln x dx x v x dx x Ln x λ λ ν µ µ µ µ we know, 0 1 1 )) ( ) ( ( 1 = - = - ∫ ∞ dx x v x λ µ , consequently dx x Ln x H ∫ ∞ ≥ - 1 )) ( ( ) ( ) ( λ ν µ µ thus according to lemma 2.2 ) ( ) ( λ µ Z H ≥ - hence ) ( ) ( ), ( ), ( λ µ σ λ µ Z H f F C ≥ - > ∀ ∈ ∀
Also, according to point 2 in the appendix, there is a function

) (F C z ∈ µ verifying 1 ≤ z µ , consequently 0 ) ( ≤ z z Ln µ µ and thus, ) ( ) ( ) ( ) ( 0 f F C Z Sup H Max σ λ µ λ µ > ∈ ≥ ≥ Proposition 2.2
With f an admissible effort function, for any density function µ we have

µ ν σ λ λ ≠ > ∀
), ( f , the following inequality: )

dx x f x x dx x Ln x dx x Ln x ) ( )) ( ) ( ( )) ( ( ) ( )) ( ( ) ( 1 1 1 ∫ ∫ ∫ ∞ ∞ ∞ - > - µ ν λ ν ν µ µ λ λ λ Proof With ) ( f σ λ > so that , µ ν λ ≠ using lemma 2.4 (ii) with
) ( ( 1 ))( ( ) ( ( )) ( ( ) ( )) ( ( ) ( x Ln x x x Ln x x Ln x λ λ λ λ ν ν µ ν ν µ µ + - ≥ -
By integrating the right member, we obtain:

∫ ∫ ∞ ∞ - + - 1 1 )) ( ( )) ( ) ( ( )) ( ) ( ( dx x Ln x x dx x x λ λ λ ν ν µ ν µ However 0 1 1 )) ( ) ( ( 1 = - = - ∫ ∞ dx x x λ ν µ Consequently, dx k Ln x f x x dx x Ln x x )) ( ) ( ( )) ( ) ( ( )) ( ( )) ( ) ( ( 1 1 - - - = - ∫ ∫ ∞ ∞ λ ν µ ν ν µ λ λ λ Hence dx x f x x )) ( ( )) ( ) ( ( 1 λ ν µ λ - - = ∫ ∞ Lemma 2.5
For any couple of real numbers , , 2 1 z z we have the following inequality:

) exp( ) ( ) exp( ) exp( 1 2 1 1 2 z z z z z - - ≥ - - - Proof We have the strict inequality if 2 1 z z ≠ . Let us suppose 2 1 z z < , according to the mean theorem, there is z , 2 1 z z z < <
, verifying the equality:

) exp( ) ( ) exp( ) exp( 1 2 1 2 z z z z z - - - = -
The inequality is then written:

) exp( ) ( ) exp( ) ( 1 2 1 2 1 z z z z z z - - ≥ - - with ) exp( ) exp( 1 z z - ≤ -
We do the same if

) ( ) ( 0 ) ( λ λ σ λ Z Z Sup f = > Proof 1) Uniqueness Let us suppose 2 1 λ λ ≠ so that ) ( , 2 1 F C ∈ λ λ ν ν
, according to lemma 2.1 we know that the entropy of λ ν is finite, by applying proposition 2.2 twice, we obtain

0 ) ( )) ( ) ( ( )) ( ( ) ( )) ( ( ) ( 1 1 1 1 2 1 1 1 2 2 = - > - ∫ ∫ ∫ ∞ ∞ ∞ dx x f x x dx x Ln x dx x Ln x λ λ λ λ λ λ ν ν λ ν ν ν ν
And in the same way

0 ) ( )) ( ) ( ( )) ( ( ) ( )) ( ( ) ( 1 2 1 1 1 2 2 2 1 1 = - > - ∫ ∫ ∫ ∞ ∞ ∞ dx x f x x dx x Ln x dx x Ln x λ λ λ λ λ λ ν ν λ ν ν ν ν
which is contradictory and consequently there is at most one item belonging to

) (F C . 2) Existence Let a function ) ( 0 F C ∈ λ ν
, according to lemma 2.5, we can write

y z y z 0 1 2 , λ λ = = , ) exp( ) ( ) exp( ) exp( 0 0 0 y y y y λ λ λ λ λ - - - - ≥ - By putting F x f y - = ) ( and integrating, dx F x f F x f dx F x f dx F x f )) ) ( ( exp( ) ) ( ( ) ( )) ) ( ( exp( )) ) ( ( exp( 0 1 1 1 0 0 - - - - - - - ≥ - - ∫ ∫ ∫ ∞ ∞ ∞ λ λ λ λ λ ) ( 0 F C v ∈ λ we know according to lemma 2.3, 0 )) ) ( ( exp( ) ) ( ( 1 0 = - - - ∫ ∞ dx F x f F x f λ consequently, ∫ ∫ ∞ ∞ - - ≥ - - 1 1 0 )) ) ( ( exp( )) ) ( ( exp( dx F x f dx F x f λ λ hence ) ( ) ( 0 λ λ Z Z ≤ and thus ) ( ) ( 0 ) ( λ λ σ λ Z Z Sup f ≤ >
We can now demonstrate the result (i) of the equivalence theorem.

Theorem 2.1

We suppose that there is a real number

) ( 0 f σ λ > so that ) ( 0 F C ∈ λ ν
, then this real number is unique and moreover:

∫ ∞ ∈ > - = = = 1 ) ( 0 ) ( )) ( ( ) ( ) ( ) ( ) ( ( 0 0 dx x Ln x MaxH Z Z Sup F C f λ λ µ σ λ ν ν µ λ λ
dx x f x x dx x Ln x dx x Ln x ) ( )) ( ) ( ( )) ( ( ) ( )) ( ( ) ( 1 1 1 0 0 ∫ ∫ ∫ ∞ ∞ ∞ - > - µ ν λ ν ν µ µ λ λ λ However 0 ) ( )) ( ) ( ( 1 0 = - = - ∫ ∞ F F dx x f x x µ ν λ Thus ∫ ∫ ∞ ∞ - < - 1 1 )) ( ( ) ( )) ( ( ) ( 0 0 dx x Ln x dx x Ln x λ λ ν ν µ µ
)), 1 ( ( ) 1 ( ) ( 2 + + + = x Ln Ln x Ln x f we show ∫ ∞ ∞ < - 1 ) ( exp( dx x f , therefore ) 1 ( Z is well defined whereas ∞ = - ∫ ∞ dx x f x f )) ( exp( ) ( 1 .
In the same way, with H a real number we consider the function ) (λ R , we demonstrate proposition 2.4 using the same techniques as previously.

Proposition 2.4

With f an admissible function, there is at most a function

) ( ) ( 1 ) ( λ λ σ λ R R Sup f = >
We can now demonstrate the result (ii) of the equivalence theorem.

Theorem 2.2

We suppose that there is a reality

) ( 1 f σ λ > so that ) ( 1 H A ∈ λ ν
, then this reality is unique and also:

∫ ∞ ∈ > = = = 1 ) ( 1 ) ( ) ( ) ( ) ( ) ( )) ( ( 1 dx x f x F Min R Z Sup H A f λ µ σ λ ν µ λ λ
dx x f x x dx x Ln x dx x Ln x ) ( )) ( ) ( ( )) ( ( ) ( )) ( ( ) ( 1 1 1 1 1 1 ∫ ∫ ∫ ∞ ∞ ∞ - > - µ ν λ ν ν µ µ λ λ λ dx x f x x H H ) ( )) ( ) ( ( 0 1 1 ∫ ∞ - > - = µ ν λ λ consequently, since 0 > λ , ∫ ∫ ∞ ∞ < 1 1 ) ( ) ( ) ( ) ( 1 dx x x f dx x x f µ ν λ
using theorems 2.1 and 2.2, we obtain the equivalence theorem. 1.

There is a real number ) ( f σ so that:

), ( f σ λ > ∀ ∞ < - ≤ ∫ ∞ 1 )) ( exp( ) ( 0 dx x f x f λ 2.
We have

) ( ) ( ) ( ) ( 0 f F C Z Sup H Max σ λ µ λ µ > ∈ ≥ ≥
Also, if there is a real number 0 λ so that

) ( 0 F C ∈ λ ν
then this real number is unique and we have:

) ( ) ( ) ( ) ( 0 ) ( ) ( 0 λ λ µ λ σ λ µ Z Z Sup H Max H f F C = = = > ∈ where ∫ ∞ - - - = 1 )) ) ( ( exp( ( ) ( dx F x f Ln Z λ λ 3.
We have

) ( ) ( ) ( ) ( 0 f H A R Sup F Min σ λ µ λ µ > ∈ ≥ ≥ Also, if there is a reality 1 λ so that ) ( 1 H A ∈ λ ν
then this real number is unique and we have:

) ( ) ( ) ( ) ( 1 ) ( ) ( 1 λ λ µ λ σ λ µ R R Sup MinF F f H A = = = > ∈

Examples

The most common distributions in infometry are: -linear effort functions

x x f = ) (
, in other words exponential distributions [START_REF] Lafouge | The source-item coverage of the exponential distribution[END_REF]

Conclusion

One of the most intriguing phenomena in infometry, and widely studied in quantitative linguistics, is Zipf's law. The name of Zipf's law has been given to the following approximation of the rank frequency function:

Figure 1 :

 1 Figure 1: Schematic representation of an Information Production Process

Figure 2 :

 2 Figure 2: Schematic representation of an informetric process using the effort function

λ

  and H corresponds to the entropy.

  We will show the most important intermediate result, namely the sets

Proof

  Uniqueness and characterization by the function Z are consequences of proposition 2

  following example shows. With the effort function

Proof

  Uniqueness and characterization by the function R are consequences of proposition 2inequality of proposition 2.2 we obtain,

  Let a positive, unbounded, strictly increasing, continuous function, we suppose that there exists

Unlike the discrete case, the entropy may be negative

where r is the rank of a word type, ) (r g is the occurrence of the word type and C is a constant. The Principle of Least Effort is attributed to Zipf in linguistics. Zipf thinks that the reason for this regularity is linked to the behaviour of the individuals. More precisely, he defines this principle philosophically thus (comment of Zipf quoted in (Ronald E. [START_REF] Wyllis | Empirical and Theoretical Bases of Zipf's Law[END_REF]):

The Principle of Least Effort means .. that a person.. will strive to solve his problem in such a way as to minimize the total work that he must expend in solving both his immediate problems and his probabilistic future problems…. We noted in [START_REF] Egghe | On the Relation Between the Maximum Entropy Principle and the Principle of Least Effort[END_REF]) that several authors confuse MEP and PLE. In the first article on the subject, introducing another principle (PME: Principle of Most Effort), we give a complete explanation of Zipf's law as a decreasing distribution, in the discrete and finite case. We place ourselves here in the case where the infometric statistical distributions are formulated in the shape of frequency-size. We refer readers interested in the rank-frequency formulation of Zipf's law given above in Egghe's work [START_REF] Egghe | Power laws in the information production process: Lotkaian Informetrics[END_REF] where the place within Lotka infometric distributions is studied with precision. In the continuous case, the two principles are equivalent if the effort function is strictly increasing, unbounded and admissible, which is the case of the logarithmic function, effort function of inverse power distributions and the linear function, effort function of exponential distributions. In practice, the admissibility condition is not very restrictive (Readers should refer to points 4 in the appendix). To completely cover the problem of equivalence, we must now study the infinite discrete case.

Appendix 1)

) (H A is not empty. Proof -Let H a real number and the function µ ,

, the function f being unbounded, strictly increasing and continuous, there is 1 > y , unique so that ) ( y f F = . Let us fix y z > , with z µ the density function defined by the three constants

It is easy to verify that we have:

Also, the function z µ is positive because f is strictly increasing and we have

. For each value of z we thus define a function z µ .

3) Additional conditions required for f .

Proof

With the effort function

The properties of the lognormal law imply:

, it is easy to see that this function is strictly increasing. We can then define its inverse f we then put

. g is also increasing, continuous, positive and unbounded, let us show that it is not admissible. Let λ any positive number, we put