Constructions of optimal locally repairable codes (LRCs) in the case of (r + 1) l n and over small finite fields were stated as open problems for LRCs in [I. , “Optimal locally repairable codes and connections to matroid theory”, 2013 IEEE ISIT]. In this paper, these problems are studied by constructing almost optimal linear LRCs, which are proven to be optimal for certain parameters, including cases for which (r + 1) l n. More precisely, linear codes for given length, dimension, and all-symbol locality are constructed with almost optimal minimum distance. ‘Almost optimal’ refers to the fact that their minimum distance differs by at most one from the optimal value given by a known bound for LRCs. In addition to these linear LRCs, optimal LRCs which do not require a large field are constructed for certain classes of parameters.
As mentioned above, in the all-symbol locality case the information theoretic trade-off between locality and code distance for any (linear or nonlinear) code was derived in @cite_2 . Furthermore, constructions of optimal LRCs for the case when @math and over small finite fields when @math is large were stated as open problems for LRCs in @cite_9 . In @cite_9 it was proved that there exists an optimal LRC for parameters @math over a field @math if @math divides @math and @math with @math large enough. In @cite_7 and @cite_3 the existence of optimal LRCs was proved for several parameters @math . Good codes with the weaker assumption of information symbol locality are designed in @cite_5 . In @cite_4 it was shown that there exist parameters @math for linear LRCs for which the bound of Eq. is not achievable.
@cite_4 @cite_7 @cite_9 @cite_3 @cite_2 @cite_5
1993830711 2155418912 2006551665 2595628957 1995147907 1996042140
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. Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n,k,d] linear code having all-symbol (r,δ)-locality, denoted as (r,δ)_a, is considered optimal if it has the actual highest minimum distance of any code of the given parameters n,k,r and δ. A minimum distance bound is given in . The existing results on the existence and the construction of optimal (r, δ)_a linear codes are limited to only two small regions within this special case, namely, i) m=0 and ii) m≥ (v+δ-1)>(δ-1) and δ=2, where m=n mod(r+δ-1) and v=k mod r. This paper investigates the properties and existence conditions for optimal (r,δ)_a linear codes with general r and δ. First, a structure theorem is derived for general optimal (r,δ)_a codes which helps illuminate some of their structure properties. Next, the entire problem space with arbitrary n, k, r and δ is divided into eight different cases (regions) with regard to the specific relations of these parameters. For two cases, it is rigorously proved that no (r,δ)_a linear code can achieve the minimum distance bound in . For four other cases the optimal (r,δ)_a codes are shown to exist over a field of size q≥( n k-1 ), deterministic constructions are proposed. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on optimal (r,δ)_a linear codes, leaving only two cases in which the construction of optimal codes are not yet known. Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes like Reed-Solomon are highly suboptimal for distributed environments due to their high overhead in single-failure events. Locally Repairable Codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs during which they generate small network traffic. Two large-scale distributed storage systems have already implemented different types of LRCs: Windows Azure Storage and the Hadoop Distributed File System RAID used by Facebook. The fundamental bounds for LRCs, namely the best possible distance for a given code locality, were recently discovered, but few explicit constructions exist. In this work, we present an explicit and simple to implement construction of optimal LRCs, for code parameters previously established by existence results. For the analysis of the optimality of our code, we derive a new result on the matroid represented by the code's generator matrix. One main challenge in the design of distributed storage codes is the Exact Repair Problem: if a node storing encoded information fails, to maintain the same level of reliability, we need to exactly regenerate what was lost in a new node. A major open problem in this area has been the design of codes that i) admit exact and low cost repair of nodes and ii) have arbitrarily high data rates. In this paper, we are interested in the metric of repair locality, which corresponds to the the number of disk accesses required during a node repair. Under this metric we characterize an information theoretic trade-off that binds together locality, code distance, and storage cost per node. We introduce Locally repairable codes (LRCs) which are shown to achieve this tradeoff. The achievability proof uses a “locality aware” flow graph gadget which leads to a randomized code construction. We then present the first explicit construction of LRCs that can achieve arbitrarily high data-rates. We design flexible schemes to explore the tradeoffs between storage space and access efficiency in reliable data storage systems. Aiming at this goal, two new classes of erasure-resilient codes are introduced -- Basic Pyramid Codes (BPC) and Generalized Pyramid Codes (GPC). Both schemes require slightly more storage space than conventional schemes, but significantly improve the critical performance of read during failures and unavailability. As a by-product, we establish a necessary matching condition to characterize the limit of failure recovery, that is, unless the matching condition is satisfied, a failure case is impossible to recover. In addition, we define a maximally recoverable (MR) property. For all ERC schemes holding the MR property, the matching condition becomes sufficient, that is, all failure cases satisfying the matching condition are indeed recoverable. We show that GPC is the first class of non-MDS schemes holding the MR property.