text: Typically, locally repairable codes (LRCs) and regenerating codes have been studied independently of each other, and it has not been clear how the parameters of one relate to those of the other. In this paper, a novel connection between locally repairable codes and exact regenerating codes is established. Via this connection, locally repairable codes are interpreted as exact regenerating codes. Further, some of these codes are shown to perform better than time-sharing codes between minimum bandwidth regenerating and minimum storage regenerating codes.
  @cite_26: Locally rapairable codes (LRCs) are ingeniously designed distributed storage codes with a (usually small) bounded number of helper nodes participating in repair. Since most existing LRCs assume exact repair and allow full exchange of the stored data (β = α), they can be viewed as a generalization of the traditional erasure codes (ECs) with a much desired feature of local repair. However, it also means that they lack the features of functional repair and partial information-exchange (β < α) in the original regenerating codes (RCs). Motivated by the significant bandwidth (BW) reduction of RCs over ECs, existing works by and by Hollmann studied “locally repairable regenerating codes (LRRCs)” that simultaneously admit all three features: local repair, partial information-exchange, and functional repair. Significant BW reduction was observed. One important issue for any local repair schemes (including both LRCs and LRRCs) is that sometimes designated helper nodes may be temporarily unavailable, the result of multiple failures, degraded reads, or other network dynamics. Under the setting of LRRCs with temporary node unavailability, this work studies the impact of different helper selection methods. It proves, for the first time in the literature, that with node unavailability, all existing methods of helper selection, including those used in RCs and LRCs, are strictly repair-BW suboptimal. For some scenarios, it is necessary to combine LRRCs with a new helper selection method, termed dynamic helper selection, to achieve optimal BW. This work also compares the performance of different helper selection methods and answers the following fundamental question: whether one method of helper selection is intrinsically better than the other? for various different scenarios.
  @cite_7: This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters @math of LRCs are generalized to matroids, and the matroid analog of the generalized singleton bound by for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters @math and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given by
  @cite_9: 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.
  @cite_1: This paper aims to go beyond resilience into the study of security and local-repairability for distributed storage systems (DSSs). Security and local-repairability are both important as features of an efficient storage system, and this paper aims to understand the trade-offs between resilience, security, and local-repairability in these systems. In particular, this paper first investigates security in the presence of colluding eavesdroppers, where eavesdroppers are assumed to work together in decoding the stored information. Second, this paper focuses on coding schemes that enable optimal local repairs. It further brings these two concepts together to develop locally repairable coding schemes for DSS that are secure against eavesdroppers. The main results of this paper include: 1) an improved bound on the secrecy capacity for minimum storage regenerating codes; 2) secure coding schemes that achieve the bound for some special cases; 3) a new bound on minimum distance for locally repairable codes; 4) code construction for locally repairable codes that attain the minimum distance bound; and 5) repair-bandwidth-efficient locally repairable codes with and without security constraints.
  @cite_5: 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.
  @cite_16: Regenerating codes and codes with locality are two coding schemes that have recently been proposed, which in addition to ensuring data collection and reliability, also enable efficient node repair. In a situation where one is attempting to repair a failed node, regenerating codes seek to minimize the amount of data downloaded for node repair, while codes with locality attempt to minimize the number of helper nodes accessed. This paper presents results in two directions. In one, this paper extends the notion of codes with locality so as to permit local recovery of an erased code symbol even in the presence of multiple erasures, by employing local codes having minimum distance >2. An upper bound on the minimum distance of such codes is presented and codes that are optimal with respect to this bound are constructed. The second direction seeks to build codes that combine the advantages of both codes with locality as well as regenerating codes. These codes, termed here as codes with local regeneration, are codes with locality over a vector alphabet, in which the local codes themselves are regenerating codes. We derive an upper bound on the minimum distance of vector-alphabet codes with locality for the case when their constituent local codes have a certain uniform rank accumulation property. This property is possessed by both minimum storage regeneration (MSR) and minimum bandwidth regeneration (MBR) codes. We provide several constructions of codes with local regeneration which achieve this bound, where the local codes are either MSR or MBR codes. Also included in this paper, is an upper bound on the minimum distance of a general vector code with locality as well as the performance comparison of various code constructions of fixed block length and minimum distance.
  @cite_25: 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.
summary: Locally repairable codes for several parameter sets @math are constructed in @cite_9 , @cite_16 , @cite_25 , @cite_5 , @cite_1 , @cite_7 . In @cite_9 it was proved that bound is not achievable for all parameters @math . Codes with local regeneration are studied in @cite_16 . In a completely different direction, connections between regenerating codes and LRCs have been made in @cite_26 , where local repairability is exploited to select helpers in a regenerating code.