Source-linked AI summary
Optimal Locally Repairable Codes via Rank-Metric Codes
Natalia Silberstein, Ankit Singh Rawat, O. Ozan Koyluoglu, Sriram Vishwanath
TL;DR
Distributed storage needs codes that tolerate node failures while keeping repair local and bandwidth efficient. The paper uses MRD Gabidulin codes with MDS array codes to construct optimal scalar and vector LRCs, including all-symbol locality without a divisibility restriction, and combines them with regenerating codes for bandwidth-efficient repair.
Problem
Distributed storage codes must provide resilience to node failures while reducing repair bandwidth or the number of nodes participating in repair.
Method
The paper applies a two-stage construction using Gabidulin MRD codes together with MDS array codes, and discusses regenerating codes within local groups for repair.
Results
The construction provides optimal scalar and vector LRCs with maximal minimum distance, including explicit all-symbol locality when (r + δ −1) does not divide n.
Takeaways & Limitations
The resulting codes achieve the paper’s optimal locality–distance target and can be extended toward repair-bandwidth-efficient LRCs.
Abstract
from arXiv · showhide
This paper presents a new explicit construction for locally repairable codes (LRCs) for distributed storage systems which possess all-symbols locality and maximal possible minimum distance, or equivalently, can tolerate the maximal number of node failures. This construction, based on maximum rank distance (MRD) Gabidulin codes, provides new optimal vector and scalar LRCs. In addition, the paper also discusses mechanisms by which codes obtained using this construction can be used to construct LRCs with efficient repair of failed nodes by combination of LRC with regenerating codes.
I. INTRODUCTION
Distributed storage codes must balance resilience to node failures with locality and repair efficiency. The paper generalizes scalar LRCs to vector codes and constructs optimal all-symbol locality codes without a divisibility restriction.
- Motivation: Distributed storage systems add coding redundancy so data can be recovered despite node failures.An (n, k) code encodes k information blocks into n blocks stored on distinct nodes.
- Motivation: Locality reduces the number of nodes involved in repair, while regenerating codes target lower repair bandwidth.These goals motivate two distinct code families for distributed storage.
- Contributions: Vector LRCs store α symbols per node and permit repair using at most r other nodes within a local group of size r + δ −1.The paper generalizes scalar LRCs and relates minimum distance to node-failure resilience and per-node storage.
- Contributions: A code with minimum distance dmin tolerates dmin −1 node failures and allows reconstruction from any n−dmin+1 surviving nodes.The paper seeks this resilience throughout repeated failures and repairs.
- Contributions: An LRC has (r, δ) locality when each node belongs to a set with minimum distance at least δ and bounded local information content.The locality definition implies each node can be expressed using at most r others in its local group.
- Contributions: The construction gives explicit optimal scalar LRCs with all-symbol locality even when (r + δ −1) does not divide n.Earlier existence results required divisibility, whereas this construction removes that restriction.
C. Maximum Rank Distance (MRD) Codes
MRD codes measure distance through matrix rank over an extension field. Gabidulin codes attain the rank-metric Singleton bound using evaluations of linearized polynomials at Fq-linearly independent points.
- Rank metric: Elements of Fqm are represented as m-dimensional vectors over Fq, and codewords become m × N matrices over Fq.This representation defines the rank used by the rank metric.
- Rank metric: The rank of a vector is the rank of its associated matrix over Fq, while rank distance is rank(V − U).These definitions convert extension-field vectors into a matrix-based distance measure.
- MRD codes: An MRD code attains the rank-metric Singleton bound D ≤ N − K + 1.Gabidulin codes provide such MRD codes when m ≥ N.
- Gabidulin codes: Linearized polynomial evaluation is Fq-linear, preserving linear combinations with coefficients from Fq.For a, b ∈ Fq, evaluation satisfies f(aγ1 + bγ2) = af(γ1) + bf(γ2).
- Gabidulin codes: Gabidulin codewords evaluate a q-degree K −1 linearized polynomial at Fq-linearly independent points.The polynomial coefficients encode the information message.
- Erasure correction: An MRD code with minimum distance D corrects any D−1 rank erasures.Gabidulin erasure-correction algorithms are available for this task.
D. MDS Array Codes
MDS array codes are linear array codes whose code size and minimum distance satisfy the MDS relation. In matrix representation, MRD codes also form MDS array codes.
- Array-code definition: A linear [α × n, k, dmin] array code is a linear subspace over Fq with α symbols per node across n nodes.Its minimum distance is measured using Hamming distance over length-n vectors whose entries are α-dimensional blocks.
- MDS property: An array code is MDS when its size is q^αk and k = n − dmin + 1.Thus the code meets the corresponding distance-dimension relation.
- MDS property: MRD codes in matrix representation are also MDS array codes.This connection lets the construction combine rank-metric and array-code properties.
E. Regenerating Codes
Regenerating codes support reconstruction from any k of n nodes while repairing a failed node by downloading β ≤ α symbols from d surviving nodes. They expose a storage–repair-bandwidth trade-off.
- Regenerating-code model: Regenerating codes repair failed nodes by downloading β ≤ α symbols from each of d surviving nodes, where k ≤ d ≤ n −1.A data collector reconstructs the file from any k of n nodes.
- Storage–bandwidth trade-off: Repair bandwidth is γ = dβ, and its trade-off with per-node storage α has MSR and MBR codes as two extreme points.MSR and MBR represent minimum-storage and minimum-bandwidth endpoints, respectively.
III. OPTIMAL LOCALLY REPAIRABLE CODES
The paper derives an upper bound on minimum distance for vector LRCs and proposes a two-stage Gabidulin–MDS array construction that attains it.
- The construction targets optimal minimum distance for (r, δ, α) locally repairable codes.It follows an upper-bound derivation presented in the same section.
- The approach uses two-stage encoding with Gabidulin codes and MDS array codes.Gabidulin codes are used as a rank-metric analogue of Reed–Solomon codes.
- The construction generalizes an earlier construction proposed in [27].
A. Upper Bound on dmin for an (r, δ, α) LRC
This section establishes a generic minimum-distance upper bound for vector LRCs with multiple local parities and identifies a trade-off between storage and failure resilience.
- Upper Bound on dmin for an (r, δ, α) LRC: The bound generalizes the vector-LRC bound for one local parity to codes with multiple local parities.The single-parity case is δ = 2, while the generalized setting allows δ ≥ 2.
- Upper Bound on dmin for an (r, δ, α) LRC: The proof constructs a node set whose total stored-symbol entropy is less than the file size M.The argument follows proof techniques used for scalar and vector LRC bounds.
- Upper Bound on dmin for an (r, δ, α) LRC: The theorem follows from the code definition and equation (5).
- Upper Bound on dmin for an (r, δ, α) LRC: Increasing per-node storage α can increase minimum distance dmin, creating a trade-off with node-failure resilience.The trade-off is relevant to codes requiring both locality and strong resilience.
- Upper Bound on dmin for an (r, δ, α) LRC: For δ = 2, the bound matches the earlier vector-LRC bound; for α = 1, it reduces to the established scalar-LRC expression.The scalar specialization is dmin ≤ n−M+1+(⌈M/r⌉−1)(δ−1).
B. Construction of dmin-Optimal Vector LRCs
Construction I combines a Gabidulin code with local MDS array codes in two encoding stages, producing vector and scalar LRCs that attain the minimum-distance bound under stated divisibility conditions. The construction also gives an explicit optimal scalar LRC when the local-group size does not divide n.
- Construction I: Construction I first encodes the file with a Gabidulin code, partitions its codeword into local groups, and applies an MDS array code to each group.The MDS array codes operate over Fq while the Gabidulin code operates over Fqm.
- Construction I: For α ≡ 0 (mod r), Gabidulin symbols are partitioned into groups of rα symbols, stored on r nodes, and augmented with δ −1 local parity nodes.Each local group uses an [α × (r + δ −1), r, δ] MDS array code over Fq.
- Construction I: When N/α leaves a remainder β0 modulo r, the construction uses g −1 full groups and one β0-sized group with its own MDS array code.The final group is stored on β0 nodes before adding δ −1 parity nodes.
- Distance argument: Any s ≤ rα symbols within a local group correspond to evaluations at s points linearly independent over Fq, linking node erasures to rank erasures correctable by the Gabidulin code.This relationship is the basis for proving the minimum-distance guarantee.
- Optimality: If (rα) divides N, Cloc attains bound (4); additional congruence conditions likewise guarantee bound attainment for the general case.The theorem assumes N ≥ M and α divides N.
- Optimality: If (r + δ −1) divides n, Cloc is optimal with Gabidulin length N = nrα/(r + δ −1) and field size |F| ≥ q^N.For α = 1, the construction is also the first explicit optimal scalar all-symbol locality construction without requiring (r + δ −1) to divide n.
- Examples: The scalar example uses r = 4, δ = 2, α = 1, n = 14, M = 9, and achieves dmin = 4 while allowing single-node repair within each group.The construction partitions the Gabidulin codeword into groups and adds one MDS parity to each group.
- Examples: The vector example uses r = 3, δ = 3, α = 4, n = 15, and achieves dmin = 5 after four node failures induce at most eight rank erasures.The underlying Gabidulin code has minimum rank distance 9.
IV. REPAIR EFFICIENT LRCS
The paper combines locally repairable and regenerating codes to reduce repair bandwidth while preserving optimal minimum distance and local storage requirements.
- Hybrid codes combine locally repairable codes with regenerating codes to minimize repair bandwidth for fixed locality parameters.
- A naïve LRC repair contacts r local nodes and downloads all data stored on them.
- The bandwidth-efficient repair variant contacts d ≥ r local nodes and downloads only β ≤ α symbols from each contacted node.
- Replacing each local MDS array code with an (r + δ −1, r, d, α, β) MSR code yields MSR-LRCs with maximal minimum distance, local minimum storage per node, and minimized repair bandwidth.The maximal minimum distance follows because an MSR code is also an MDS array code.
- Optimal scalar Construction I codes can also be used to construct MBR-LRCs with an MBR code in each local group.
V. CONCLUSION
The paper presents a maximum-rank-distance-based construction for scalar and vector locally repairable codes, proves its optimality, and extends it toward repair-bandwidth-efficient LRCs.
- The construction is based on maximum rank distance codes and applies to both scalar and vector locally repairable codes.
- The paper derives an upper bound on minimum distance for vector LRCs and proves that the construction attains it in both scalar and vector cases.
- The construction also supports repair-bandwidth-efficient LRCs.
APPENDIX A PROOF OF THEOREM 10
The appendix proves optimal minimum distance by showing that worst-case node erasures translate into at most D −1 correctable rank erasures of the underlying Gabidulin code.
- The proof considers erasure patterns concentrated in the smallest possible number of local groups, with as many erasures as possible inside each group.
- The parameters decompose N and M into full groups, remainders, and a residual term γ1, yielding D −1 = N −M = rα(α0 −α1) + α(β0 −β1) −γ1.
- The bound is analyzed through inequalities involving the numbers of fully erased groups and one partially erased group.
- When the residual case gives α1 groups, the distance bound reduces to (r + δ −1)(α0 −α1) + δ −1, corresponding to rα(α0 −α1) rank erasures.
- Because D −1 = rα(α0 −α1), the corresponding erasures are correctable by the Gabidulin code.
- Other remainder cases yield rank-erasure counts rα(α0 −α1) − αβ1 or less than D −1, so the Gabidulin code corrects them.