In a distributed storage system, recovering from multiple failures is a critical and frequent task that is crucial for maintaining the system's reliability and fault-tolerance. In this work, we focus on the problem of repairing multiple failures in a centralized way, which can be desirable in many data storage configurations, and we show that a significant repair traffic reduction is possible. First, the fundamental tradeoff between the repair bandwidth and the storage size for functional repair is established. Using a graph-theoretic formulation, the optimal tradeoff is identified as the solution to an integer optimization problem, for which a closed-form expression is derived. Expressions of the extreme points, namely the minimum storage multi-node repair (MSMR) and minimum bandwidth multi-node repair (MBMR) points, are obtained. Second, we describe a general framework for converting single erasure minimum storage regenerating codes to MSMR codes. The repair strategy for @math failures is similar to that for single failure, however certain extra requirements need to be satisfied by the repairing functions for single failure. For illustration, the framework is applied to product-matrix codes and interference alignment codes. Furthermore, we prove that the functional MBMR point is not achievable for linear exact repair codes. We also show that exact-repair minimum bandwidth cooperative repair (MBCR) codes achieve an interior point, that lies near the MBMR point, when @math , @math being the minimum number of nodes needed to reconstruct the entire data. Finally, for @math and @math , where @math is the number of helper nodes during repair, we show that the functional repair tradeoff is not achievable under exact repair, except for maybe a small portion near the MSMR point, which parallels the results for single erasure repair by
Consider a linear [n,k,d]q code C. We say that the ith coordinate of C has locality r , if the value at this coordinate can be recovered from accessing some other r coordinates of C. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper, we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n-k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst case distance, and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality and the ability to correct erasures beyond the minimum distance. A code over a finite alphabet is called locally recoverable (LRC) if every symbol in the encoding is a function of a small number (at most r ) other symbols. We present a family of LRC codes that attain the maximum possible value of the distance for a given locality parameter and code cardinality. The codewords are obtained as evaluations of specially constructed polynomials over a finite field, and reduce to a Reed-Solomon code if the locality parameter r is set to be equal to the code dimension. The size of the code alphabet for most parameters is only slightly greater than the code length. The recovery procedure is performed by polynomial interpolation over r points. We also construct codes with several disjoint recovering sets for every symbol. This construction enables the system to conduct several independent and simultaneous recovery processes of a specific symbol by accessing different parts of the codeword. This property enables high availability of frequently accessed data (“hot data”). In this paper, we study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. By a local parity-check computation, we mean recovery via a single parity-check equation associated to small Hamming weight. Earlier approaches considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. These codes, which we refer to as locally 2-reconstructible codes, are a natural generalization along one direction, of codes with all-symbol locality introduced by Gopalan , in which recovery from a single erasure is considered. By studying the Generalized Hamming Weights of the dual code, we derive upper bounds on the minimum distance of locally 2-reconstructible codes and provide constructions for a family of codes based on Tur 'an graphs, that are optimal with respect to this bound. The minimum distance bound derived here is universal in the sense that no code which permits all-symbol local recovery from @math erasures can have larger minimum distance regardless of approach adopted. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. We consider the problem of designing [n; k] linear codes for distributed storage systems (DSS) that satisfy the (r, t)-Local Repair Property, where any t'(<=t) simultaneously failed nodes can be locally repaired, each with locality r. The parameters n, k, r, t are positive integers such that r<k<n and t <= n-k. We consider the functional repair model and the sequential approach for repairing multiple failed nodes. By functional repair, we mean that the packet stored in each newcomer is not necessarily an exact copy of the lost data but a symbol that keep the (r, t)-local repair property. By the sequential approach, we mean that the t' newcomers are ordered in a proper sequence such that each newcomer can be repaired from the live nodes and the newcomers that are ordered before it. Such codes, which we refer to as (n, k, r, t)-functional locally repairable codes (FLRC), are the most general class of LRCs and contain several subclasses of LRCs reported in the literature. In this paper, we aim to optimize the storage overhead (equivalently, the code rate) of FLRCs. We derive a lower bound on the code length n given t belongs to 2,3 and any possible k, r. For t=2, our bound generalizes the rate bound proved in [14]. For t=3, our bound improves the rate bound proved in [10]. We also give some onstructions of exact LRCs for t belongs to 2,3 whose length n achieves the bound of (n, k, r, t)-FLRC, which proves the tightness of our bounds and also implies that there is no gap between the optimal code length of functional LRCs and exact LRCs for certain sets of parameters. Moreover, our constructions are over the binary field, hence are of interest in practice.