PaperlayerView exact revision on arXiv

Source-linked AI summary

A family of optimal locally recoverable codes

Itzhak Tamo, Alexander Barg

arXiv:1311.3284v2cs.IT

TL;DR

Large-scale storage needs efficient repair with low locality, but prior optimal LRC constructions often require impractically large alphabets. The paper constructs polynomial-evaluation LRC codes that meet the Singleton-like distance bound, use alphabets comparable to code length, and support multiple disjoint recovery sets.

  • Problem

    Storage systems need efficient single-failure repair and high availability, while prior optimal LRC constructions commonly used alphabets exponential in code length.

  • Method

    The paper constructs LRC codes by evaluating specially structured polynomials over finite fields and extends them with multiple disjoint recovering sets.

  • Results

    The constructed codes meet the Singleton-like minimum-distance bound for 1 < r < k, and the main construction uses q ≥ n.

  • Takeaways & Limitations

    The codes provide local recovery through r-symbol interpolation, while disjoint recovering sets support simultaneous recovery of frequently accessed data.

Abstract

from arXiv · show

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").

I. INTRODUCTION

The paper studies repair locality in large-scale storage, where failures and availability requirements motivate redundancy and coding. It develops optimal LRC codes that address locality limits while using alphabets comparable to code length.

  • Storage motivation: Distributed storage uses redundancy because large systems regularly recover from failures while requiring high data availability.Replication is widespread, whereas Reed-Solomon coding can reduce storage overhead; Facebook’s (14, 10) code uses 40% overhead versus 200% for threefold replication.
  • Repair locality: Repair locality measures how many other codeword symbols must be accessed to recover a failed symbol, and the paper focuses on this metric.Existing work also considers repair bandwidth and disk I/O, but their fundamental limits remain incompletely understood.
  • Repair locality: LRC codes recover each symbol from at most r other symbols, enabling single-failure repair with only r reads.The locality parameter satisfies 1 ≤ r ≤ k; MDS codes have locality r = k.
  • Optimality: The Singleton-like distance bound asks how much minimum distance an (n, k, r) LRC code can achieve, and equality defines an optimal LRC code.When r = k, the bound becomes the classical Singleton bound, so optimal LRC codes are MDS codes such as Reed-Solomon codes.
  • Prior work and contribution: Earlier optimal LRC constructions used exponentially large alphabets, complicating implementation, while the paper targets alphabet size comparable to n.The construction is presented as a natural generalization of Reed-Solomon codes.
  • Prior work and contribution: The paper constructs optimal (n, k, r) LRC codes over finite fields with q ≥ n and also gives codes with multiple disjoint recovering sets.The latter support simultaneous recovery from different portions of the encoding and can serve frequently accessed data.

A. General construction

The construction evaluates specially structured polynomials on field points partitioned into recovering sets. It achieves locality through interpolation and, under stated assumptions, attains the Singleton-like distance bound.

  • General construction: The codewords are evaluations of message-dependent polynomials at a specially chosen set A of n field points.A polynomial g of degree r + 1 is chosen to be constant on each block of a partition of A into sets of size r + 1.
  • General construction: The encoding polynomial combines coefficient polynomials with powers of g, allowing the construction to impose locality while retaining a polynomial-evaluation form.The resulting code is defined as the evaluation vector of f_a over A.
  • Local recovery: An erased symbol is recovered by interpolating a degree-less-than-r polynomial from the r remaining symbols in its recovering set.The interpolated decoding polynomial is evaluated at the erased location.
  • Optimality: Theorem 3.1 states that the constructed linear code has dimension k and minimum distance meeting the Singleton-like bound with equality.Thus the construction is an optimal (n, k, r) LRC code.
  • Example: For n = 9, k = 4, r = 2, the example uses F13 and obtains minimum distance d = 5.The example recovers f_a(1) = 4 by accessing the symbols at locations 3 and 9.
  • Extensions and relation to Reed-Solomon: When r = k, the construction reduces to Reed-Solomon codes because the coefficient polynomials become constants and no good polynomial is needed.The restriction that r divides k can be lifted, with encoding-polynomial degree at most k + ⌈k/r⌉ − 2.

B. Constructing optimal LRC codes using algebraic structure of the field

The construction uses specially chosen polynomials that are constant on partition blocks, enabling optimal LRC codes over fields whose size is comparable to the code length. Multiplicative, additive, and combined field structures provide constructions for broad parameter families, with explicit unresolved cases and general existence results.

  • Polynomial construction: The construction seeks a degree-r + 1 polynomial that is constant on disjoint blocks of evaluation points, enabling local recovery.The polynomial and its partition are the central ingredients of the algebraic construction.
  • Multiplicative structure: Multiplicative subgroup annihilators yield partitions into cosets, allowing code lengths that are multiples of r + 1 within field-size constraints.For these constructions, n is bounded by q − 1, or by q for additive groups.
  • Combined structures: Additive subgroups and combined additive-multiplicative constructions extend the method to larger sets of parameters over field extensions.The combined method uses additive subgroups closed under multiplication by a subfield and unions of cosets.
  • Parameter regimes: For t = 0, t > 0 with m = 1, or t and m > 1 with l dividing t, the paper gives corresponding multiplicative, additive, or combined constructions.Here l is the smallest integer satisfying p^l mod m = 1.
  • Parameter limitations: The method cannot construct locality r = 5 over extensions of F2, although counting shows that suitable polynomials exist over sufficiently large fields.This identifies a construction limitation rather than nonexistence in all finite fields.
  • Existence result: For q = 211, a degree-5 polynomial gives an optimal code of length n = 18, locality r = 5, and any dimension k ≤ 15.The polynomial is constant on at least three disjoint sets of size 6.

C. A general view of the LRC code family

The general framework defines LRC codes through polynomial algebras associated with partitions of evaluation points. Encoding polynomials are evaluated on the partitioned set, and blockwise interpolation provides locality while the construction supplies distance guarantees.

  • Polynomial algebra: The polynomial space consists of degree-bounded polynomials that are constant on each block of a partition of the evaluation set.Its dimension equals the number of partition blocks.
  • Algebraic basis: When a degree-r + 1 polynomial g exists, the powers 1, g, ..., g^(m−1) form a basis of the polynomial algebra.The degree sequence is then d_i = i(r + 1).
  • Code construction: An injective message-to-polynomial mapping followed by evaluation on n points produces an (n, k, r) LRC code whenever k ≤ nr/(r + 1).The mapping may be linear, in which case the resulting code is linear.
  • Distance: Theorem 3.7 states that the general construction gives an (n, k, r) LRC code with a minimum-distance bound determined by the construction.The supplied passage identifies this as the general distance theorem.
  • Local recovery: A lost symbol is recovered by interpolating a degree-at-most-r − 1 polynomial from the other r values in its partition block.Because the encoding polynomial is constant on each block through its coefficient-polynomial representation, blockwise interpolation recovers the missing value.

D. Systematic encoding of LRC codes

The constructions can be modified into systematic LRC codes without sacrificing distance in the applicable cases. Lagrange interpolation places information symbols directly in selected coordinates while preserving locality.

  • Systematic form: All described constructions can be modified to systematic form with no loss in code distance.The modification changes the encoding polynomials used by the construction.
  • Information placement: Information symbols are assigned to r selected coordinates within each of the first k/r partition blocks.For each block B_i, the message occupies a subset of size r.
  • Encoding polynomials: Lagrange interpolation constructs degree-bounded polynomials that realize the desired coordinate values on those information positions.These polynomials are combined with the partition basis to form the encoding polynomial.
  • Locality and systematicity: The resulting code remains locally recoverable because its encoding polynomial belongs to the partition-constant polynomial space.Each information coordinate satisfies f_a(β_i,j) = a_i,j, so the code is systematic.
  • Optimality: When the algebra is generated by powers of a good polynomial g, the systematic construction can also achieve optimal distance.The degree bound on the encoding polynomial yields the optimality claim.

IV. LRC CODES WITH MULTIPLE RECOVERING SETS

The paper extends LRC codes so every symbol has multiple disjoint recovering sets, supporting simultaneous access through different portions of the codeword. Orthogonal partitions and related algebraic constructions provide recovery and distance guarantees, with comparisons showing reduced storage overhead relative to repetition.

  • Motivation and definition: Multiple-recovery LRC codes give each symbol disjoint recovering sets, allowing independent recovery processes for frequently accessed data.The paper focuses on disjoint sets because simultaneous users can access different data portions.
  • Construction methods: Two construction methods are presented: orthogonal partitions, and product or graph codes combining several LRC codes.The exposition restricts examples to two recovering sets, although the constructions extend to more.
  • Two recovering sets: Orthogonal partitions give every symbol two disjoint recovering sets of sizes r and s, and Theorem 4.1 guarantees distance at least n − m + 1.Recovery uses the block containing the symbol in either partition.
  • Orthogonality condition: Coset partitions are orthogonal exactly when their subgroups intersect trivially, yielding algebraic constructions with disjoint recovery sets.For cyclic groups, trivial intersection is equivalent to coprime subgroup sizes.
  • Storage trade-off: Compared with three-fold repetition, the (12, 6) LRC(2) code has 100% rather than 200% overhead and tolerates any three erasures.This lower overhead requires recovery subsets of sizes 2 and 3 instead of singleton subsets.

B. LRC Product Codes

The product construction combines LRC codes to obtain codes with two locality parameters and distance equal to the product of component distances. Compared with an alternative construction, it trades minimum-distance performance against flexibility and field size.

  • The product of two LRC codes with parameters (n_i, k_i, r_i) yields an LRC(2) code with parameters (n_1n_2, k_1k_2, {r_1, r_2}) and distance d_1d_2.
  • Each symbol in the product code has two disjoint recovering sets, obtained by interpolating along either coordinate.Recovery uses r_1 symbols in one coordinate direction or r_2 symbols in the other.
  • For a product of two identical optimal component codes, the construction specializes to an (81, 16, {2, 2}) code over F_13.The component code is the optimal (9, 4, 2) code with encoding polynomial fa(x) = a_0 + a_1x + a_2x^3 + a_3x^4.
  • A product-code symbol can be recovered by interpolating from two points in either of its coordinate directions.For fa(1, 2), recovery uses values at (3, 2) and (9, 2), or at (1, 6) and (1, 5).
  • Construction 3 has higher minimum distance than the product of two optimal codes when the target rate satisfies the stated condition.
  • The product construction offers disjoint recovering sets by design and requires a field of size about √n, whereas Construction 3 uses a field of size about n.Construction 3 may be difficult because it requires several mutually orthogonal partitions with corresponding good polynomials.

V. GENERALIZATIONS OF THE MAIN CONSTRUCTION

The paper generalizes its main LRC construction beyond the original setting. These extensions address arbitrary lengths, arbitrary recovering-set sizes, and additional construction variants.

  • The generalizations remove the assumption that code length n is a multiple of r + 1.
  • The paper gives a general method for constructing LRC codes with recovering sets of arbitrary specified size.
  • The section also considers further extensions of the single-recovering-set construction.

A. Arbitrary code length

The paper extends the construction to lengths that are not multiples of r + 1 by using a smaller final partition set and modified encoding maps. The resulting distance is generally within one of the best possible value.

  • The generalized construction allows n mod (r + 1) ≠ 1, rather than requiring n to be a multiple of r + 1.
  • The evaluation set is partitioned into sets of size r + 1 and a final set of size s, with 1 < s < r + 1.
  • The encoding uses injective mappings, including one whose image consists of polynomials vanishing on the smaller final set.
  • Construction 5 defines an (n, k, r) LRC code, while Construction 6 provides a minimum-distance guarantee for the generalized setting.
  • Symbols in the full-size partition sets are recovered from r other symbols, while symbols in the final set are recovered by interpolation from s − 1 values.
  • The designed minimum distance is at most one less than the maximum possible value, and the codes are optimal in the parameter regime where the best bound is also one less.

B. LRC codes as Redundant Residue Codes

The redundant-residue-code construction partitions codeword coordinates into disjoint local MDS codes using Chinese Remainder Theorem structure. It supports flexible local parameters while retaining a distance lower bound determined by the local codes.

  • The Chinese Remainder Theorem supplies the underlying combination principle through pairwise coprime polynomials and prescribed residues.
  • It constructs a degree-less-than-n encoding polynomial satisfying congruences fa(x) ≡ M_i(x) mod G_i(x), then evaluates it on n points.
  • The construction partitions the codeword symbols into t disjoint local codes C_i, each an (n_i, k_i) MDS code.
  • Each coordinate subset A_i yields an (n_i, k_i) MDS code because the encoding polynomial restricts to M_i on A_i.
  • The constructed code has distance at least min_{1≤i≤t}(n_i − k_i + 1).
  • The method can combine arbitrary local MDS codes, with earlier constructions recovered as the special case of (r + 1, r) local codes.

C. (r + ρ −1, r) Local MDS Codes

This construction partitions coordinates into local groups supporting (r + ρ − 1, r) MDS codes, so each symbol can be recovered from any r other symbols. The resulting code attains the minimum-distance bound with equality.

  • Local recovery: Any symbol in a local group can be recovered from any r of the remaining r + ρ − 2 symbols.This follows from the local MDS property and increases the number of available recovery subsets.
  • Construction: The construction partitions the coordinate set into groups of size r + ρ − 1, each carrying an (r + ρ − 1, r) MDS code.The construction assumes n divides r + ρ − 1 and r divides k, though the latter restriction is stated to be unessential.
  • Encoding: The encoding maps each information vector to evaluations of a polynomial constructed from powers of a group-constant polynomial g.The polynomials 1, g, ..., g^(m−1) span the algebra associated with the partition, and the code is the image under an evaluation map.
  • Optimality: Construction 8 yields an optimal (n, k, r, ρ) LRC code.The local recoverability proof reconstructs the restricted polynomial from any r values in its local group.
  • Optimality: The encoding polynomial has degree at most k − 1 + (⌈k/r⌉ − 1)(ρ − 1), yielding equality in the minimum-distance bound.The distance optimality conclusion uses linearity together with this degree bound.

VI. CONCLUSIONS

The paper constructs optimal LRC codes meeting the Singleton-like distance bound and extends them to multiple independent recovering sets. It identifies algebraic decoding and algebraic-geometric generalizations as future directions.

  • Conclusions: The codes meet the Singleton-like bound on minimum distance for every locality parameter satisfying 1 < r < k.The construction is described as a natural generalization of Reed-Solomon codes that incorporates locality.
  • Conclusions: Multiple independent recovering sets allow a lost symbol to be corrected through several different r-subsets of codeword coordinates.This extension supports simultaneous recovery processes from different portions of the encoding.
  • Future directions: Algebraic decoding for correcting up to ⌊(d − 1)/2⌋ errors and generalization to algebraic geometric codes remain future research directions.These directions are stated as extensions related to the code family studied in the paper.

APPENDIX PROOF OF THEOREM 2.1

The appendix proves the Singleton-like locality bound by representing recovering relationships as a directed graph. An induced acyclic subgraph identifies coordinates determined by its complement, leaving at least r + 1 redundant coordinates per recovery group.

  • APPENDIX PROOF OF THEOREM 2.1: A directed graph contains an induced acyclic subgraph on a sufficiently large vertex subset, established using a random vertex ordering.The appendix derives this result through indicator variables and an arithmetic–harmonic mean inequality.
  • APPENDIX PROOF OF THEOREM 2.1: A directed graph represents the code coordinates, with an edge from i to j when j belongs to i's recovering set.Because locality is at most r, every vertex has outgoing degree at most r.
  • APPENDIX PROOF OF THEOREM 2.1: Every coordinate in the acyclic subset is a function of the coordinates outside that subset.The proof removes vertices without outgoing edges iteratively, preserving the determination relationship.
  • APPENDIX PROOF OF THEOREM 2.1: r + 1 coordinates are redundant, so the number of information coordinates satisfies k ≤ rn/(r + 1).This counting step establishes the locality-based dimension bound.
  • APPENDIX PROOF OF THEOREM 2.1: The minimum distance is defined through the code's coordinate-recovery structure before the bound is concluded.The appendix introduces the distance characterization and then applies the graph argument to obtain the result.
Loading 1311.3284v2…