PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Locally Repairable Codes and Connections to Matroid Theory

Itzhak Tamo, Dimitris S. Papailiopoulos, Alexandros G. Dimakis

arXiv:1301.7693v3cs.IT

TL;DR

Distributed storage needs codes that reduce repair costs without the storage overhead of replication, while classical Reed-Solomon codes can generate substantial repair traffic. The paper constructs an explicit LRC family by locally re-encoding grouped Reed-Solomon symbols, proves optimality through generator-matrix matroids, and generalizes the construction to tolerate multiple local erasures.

  • Problem

    Distributed storage requires repair-efficient codes because replication has high storage overhead and classical Reed-Solomon codes can be highly suboptimal for distributed repairs.

  • Method

    The paper groups Reed-Solomon coded symbols, re-encodes each group with an MDS local code, and analyzes the generator matrix through matroid properties.

  • Results

    The construction is an explicit family of optimal (n, k, r) LRCs with locality r and the optimal minimum distance.

  • Takeaways & Limitations

    The codes provide a simple construction based on re-encoding Reed-Solomon symbols, with a generalization to optimal (n, k, r, δ) LRCs.

Abstract

from arXiv · show

Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes like Reed-Solomon are highly sub-optimal 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 optimal LRCs that are simple to construct. Our construction is based on grouping Reed-Solomon (RS) coded symbols to obtain RS coded symbols over a larger finite field. We then partition these RS symbols in small groups, and re-encode them using a simple local code that offers low repair locality. For the analysis of the optimality of the code, we derive a new result on the matroid represented by the code generator matrix.

I. INTRODUCTION

The paper motivates locally repairable codes as a response to the storage overhead and repair inefficiency of traditional replication and classical erasure codes. It introduces an explicit optimal LRC family built by re-encoding Reed-Solomon symbols with local MDS codes and analyzes optimality through matroid properties.

  • Triple replication creates a threefold storage overhead that becomes a major data-center cost bottleneck as stored data outpaces infrastructure.
  • Reed-Solomon coding can impose disproportionate repair traffic in distributed storage, motivating codes designed for distributed repairs.In Facebook’s Hadoop analytics cluster, Reed-Solomon protected 8% of stored data but generated approximately 20% of total network traffic during repairs.
  • Repair locality measures the number of nodes participating in repair, alongside repair-bandwidth and disk-I/O, and is the metric emphasized here for high-connectivity clusters.
  • An LRC recovers each coded symbol from at most r other symbols; optimal LRCs meet the known distance bound when r + 1 divides n.
  • Optimality is established through a minimum-distance result for the matroid represented by the generator matrix, combined with determinant and finite-field polynomial properties.
  • The construction re-encodes groups of r Reed-Solomon symbols with (r + 1, r) MDS local codes, enabling locality r while retaining a simple design.

II. CODE CONSTRUCTION

The construction starts from Reed-Solomon symbols, partitions them into nonoverlapping groups, and locally re-encodes each group. The resulting code has locality r and the optimal minimum distance under the stated divisibility condition.

  • For r + 1 dividing n and 1 < r < k, the construction targets an optimal (n, k, r) locally repairable code.
  • The encoder partitions Reed-Solomon output into m/r nonoverlapping groups of r symbols and re-encodes each group into r + 1 symbols with an MDS local code.
  • Each missing symbol can be recovered from the remaining r coded symbols in its local group, giving locality r.
  • The generator matrix can be transformed into systematic form by selecting k linearly independent columns without changing locality or distance properties.
  • The Reed-Solomon symbols may be grouped to operate over a larger field, so the construction’s finite-field representation requirement is not strict.
  • Theorem 1 states that the constructed code has locality r and optimal minimum distance d = n − k − … .
  • The optimality proof reduces the problem to invertibility of selected k × k generator submatrices and establishes it using determinants and finite-field polynomials.

III. MATROIDS AND LOCALLY REPAIRABLE CODES

This section connects linear-code minimum distance to the matroid represented by the generator matrix. The connection yields sufficient conditions for constructing optimal locally repairable codes.

  • The paper expresses a linear code’s minimum distance using circuits of the matroid represented by its generator matrix.The result applies to any linear code, not only locally repairable codes.
  • The matroid-based characterization provides sufficient conditions for a generator matrix to produce an optimal locally repairable code.
  • The section frames matroid theory through definitions of rank, independence, dependence, and circuits before applying the framework to code distance.

A. Overview of Matroid Theory

The paper defines matroids through a rank function on subsets and uses rank to distinguish independent sets, dependent sets, and circuits. For a generator matrix, the rank of a subset is the rank of its corresponding columns.

  • A matroid consists of a ground set [n] and an integer-valued rank function defined on every subset of that set.
  • The rank function is nonnegative, bounded above by subset size, monotone under inclusion, and satisfies submodularity.
  • A set is independent when its rank equals its size; otherwise it is dependent, and a circuit is a dependent set whose proper subsets are independent.
  • For a code generator matrix, the matroid rank of a column subset is defined as the rank of the corresponding generator-matrix submatrix.

B. Connections to Code Distance

The paper connects linear-code locality and minimum distance to circuits in the matroid represented by the generator matrix. This characterization yields necessary and sufficient conditions for optimal linear LRCs.

  • Matroid connection: A new matroid result expresses a linear code’s minimum distance through parameters of the matroid represented by its generator matrix.This connection applies without assuming locality, distinguishing it from the related framework cited by the authors.
  • Matroid connection: The parameter µ is the smallest positive integer for which every nontrivial union of µ circuits has size at least k + µ.The paper establishes that µ is well defined and at most n + 1.
  • Matroid connection: A code has locality r exactly when every coordinate lies in a circuit of size at most r + 1, and its distance is d = n − k − µ + 2.The locality criterion follows from the circuit definition, while the distance formula holds for any linear code.
  • Optimal LRC characterization: An optimal linear LRC has locality r and d = n − k − ⌈k/r⌉ + 2 exactly when every coordinate lies in a circuit of size at most r + 1 and every nontrivial union of ⌈k/r⌉ circuits is sufficiently large.The conditions combine the matroid characterization with the known upper bound for codes of locality r.
  • Optimal LRC characterization: A simpler sufficient condition is that all nontrivial circuits have size r + 1 and partition the coordinate set [n].Under this condition, the code has locality r and achieves the optimal distance formula.

IV. OPTIMALITY OF THE CODE CONSTRUCTION

The construction proves optimality by identifying the generator-matrix matroid’s nontrivial circuits. Local MDS codes create repair groups, while polynomial arguments establish that no other nontrivial circuits exist.

  • Repair-group circuits: The proof of optimality reduces to showing that these repair-group circuits are the only nontrivial circuits of the generator-matrix matroid.Corollary 1 then directly gives optimal minimum distance.
  • Repair-group circuits: Each group of r + 1 symbols forms a circuit and supports locality r through an (r + 1, r)-MDS local code.Any symbol is repaired from the other r symbols in its group, and the groups partition [n].
  • Determinant argument: The permanent of every relevant submatrix is a monic polynomial in ω of degree at most t, ensuring a unique nonzero leading determinant term.This property follows from the block-diagonal structure and multiplicativity of the permanent across blocks.
  • Determinant argument: For a selected k-subset avoiding complete repair groups, the corresponding generator submatrix is shown invertible by proving its determinant is a nonzero polynomial in ω.Because ω has minimum-polynomial degree k + 1 over Fp, a nonzero polynomial of degree at most k cannot vanish at ω.
  • Determinant argument: Expanding determinants using Vandermonde columns turns each determinant into a polynomial in ω whose coefficients are determinants over Fp.The nonzero highest-degree term is controlled by the permanent of a block-diagonal matrix.
  • Conclusion: Combining the circuit characterization with the determinant proof establishes that the construction is an optimal (n, k, r) LRC.The generator matrix is therefore shown to achieve the required locality and optimal distance.

A. Encoding top of existing Reed-Solomon stripes

The construction reuses existing Reed-Solomon-coded data by grouping symbols into larger-field symbols, then re-encodes small groups to add locality with limited computation.

  • Local re-encoding: Construction 1 re-encodes groups of r RS-coded symbols using an (r + 1, r)-MDS local code.The resulting groups provide locality r while retaining the RS-based first encoding step.
  • Encoding over existing data: Existing RS symbols can be used directly because the first encoding step is implemented by grouping symbols, while only the second step performs new coding.This avoids decoding all previously stored information before adding locality.
  • Grouping Reed-Solomon symbols: Grouping k + 1 RS-coded symbols over Fp yields one equivalent RS symbol over Fp^(k+1).The representation concatenates the k + 1 component symbols evaluated at the same point.
  • Example: In the Figure 2 example, four RS stripes over F2^4 are stored in six nodes, and symbol pairs are transformed into three symbols over F2^16.Each node is viewed as storing one RS symbol over (F2^4)^4.

B. Decoding beyond the minimum distance: tolerating asymptotically as many erasures as an MDS code.

Although Construction 1 has lower minimum distance than an MDS code, its structure allows most k-symbol subsets to decode the file when locality grows logarithmically with code length.

  • Distance versus decoding: Construction 1 has minimum distance one less than an (n, k) MDS code.The paper studies decoding behavior beyond this worst-case distance guarantee.
  • Typical erasure patterns: When n/k is fixed and r = Ω(log(n)), the probability of reconstructing the file from k randomly selected symbols tends to 1 as n and k grow.The probability is analyzed through the full-rank condition on selected generator-matrix columns.
  • Failure characterization: Decoding fails for selected k-subsets containing a complete local repair group, while subsets avoiding those circuits are full-rank.The exact decoding probability can be expressed using inclusion-exclusion and bounded using a union bound.
  • Typical erasure patterns: For r = Ω(log(n)), a fraction 1 − o(1) of all k-subsets of coded symbols can decode the file.This is an asymptotic statement for the construction.

VI. GENERALIZATION OF THE CONSTRUCTION

The construction is generalized to tolerate multiple local erasures by replacing each local code with an MDS code of distance δ, while matroid arguments establish the resulting distance optimality.

  • Generalized locality: Each symbol in an (n, k, r, δ) LRC belongs to an (r + δ − 1, r) MDS local code.Each local code can tolerate up to δ − 1 simultaneous local erasures.
  • Construction: The generalized construction changes the second encoding step to use an r × (r + δ − 1) matrix whose r × r submatrices are invertible.The matrix is built from powers of a primitive field element, with a sufficiently large field extension ensuring nonzero determinants.
  • Matroid structure: The represented matroid has no nontrivial circuits outside individual MDS local codes.This confines the dependencies relevant to the distance proof within repair groups.
  • Matroid structure: For admissible circuit unions, generator submatrices are invertible because their determinants are nonzero polynomials of degree below the primitive element’s minimum-polynomial degree.This establishes full rank for the subsets used in the matroid argument.
  • Optimality proof: The minimum-distance proof computes μ as (⌈k/r⌉ − 1)(δ − 1) + 1, then derives the distance from the matroid proposition.The lower and upper bounds are obtained by analyzing unions of circuits across local codes.

VII. CONCLUSIONS

The paper presents simple optimal LRC constructions based on re-encoded Reed-Solomon symbols, proves optimality through matroid properties, and extends the design to multiple local erasures.

  • Contributions: The proposed family provides simple explicit optimal (n, k, r) LRC constructions based on re-encoding Reed-Solomon-coded symbols.The construction adds locality without abandoning the RS-based coding framework.
  • Contributions: Optimality is established by connecting code minimum distance to properties of the matroid represented by the generator matrix.The same framework supports the generalized (n, k, r, δ) construction.
  • Scope and limitations: The constructions require a large finite field, while each field element has a representation of O(k log n) bits.The paper presents this representation cost as not a significant practical problem.
  • Scope and limitations: Explicit optimal constructions remain open when r + 1 does not divide n and when small finite fields are required.These are the paper’s stated open problems.
Loading 1301.7693v3…