Source-linked AI summary
Locally Repairable Codes
Dimitris S. Papailiopoulos, Alexandros G. Dimakis
TL;DR
Distributed storage needs lower-overhead reliability without the high repair cost of conventional erasure codes. The paper develops locally repairable codes, proves a universal locality-distance-storage trade-off and its achievability, and constructs explicit optimal-locality codes.
Problem
The open problem is designing repair-efficient erasure codes that also support arbitrarily high data rates, because conventional erasure codes can have high node-repair costs.
Method
The paper combines an information-theoretic bound with a locality-aware flow-graph achievability proof and explicit vector-linear constructions.
Results
The paper establishes a universal bound linking distance, locality, and per-node storage, proves achievability when (r + 1) divides n, and presents explicit optimal-locality LRCs.
Takeaways & Limitations
LRCs provide a repair-locality-optimized code family, including explicit constructions with small field size and simple XOR-based repairs.
Takeaways & Limitations
Tightness of the distance bound beyond the case where (r + 1) divides n remains an open question.
Abstract
from arXiv · showhide
Distributed storage systems for large-scale applications typically use replication for reliability. Recently, erasure codes were used to reduce the large storage overhead, while increasing data reliability. A main limitation of off-the-shelf erasure codes is their high-repair cost during single node failure events. A major open problem in this area has been the design of codes that {\it i)} are repair efficient and {\it ii)} achieve arbitrarily high data rates. In this paper, we explore the repair metric of {\it locality}, which corresponds to the number of disk accesses required during a {\color{black}single} node repair. Under this metric we characterize an information theoretic trade-off that binds together locality, code distance, and the storage capacity of each node. We show the existence of optimal {\it locally repairable codes} (LRCs) that achieve this trade-off. The achievability proof uses a locality aware flow-graph gadget which leads to a randomized code construction. Finally, we present an optimal and explicit LRC that achieves arbitrarily high data-rates. Our locality optimal construction is based on simple combinations of Reed-Solomon blocks.
1 Introduction
The paper studies locally repairable codes for distributed storage, characterizing a universal trade-off among locality, distance, and per-node storage. It proves achievability under divisibility conditions and gives explicit constructions with optimal locality.
- Motivation: Erasure coding reduces replication’s storage overhead, but classical codes can impose high node-repair costs.In one deployment, Reed-Solomon coding for 8% of stored data generated approximately 20% of total network traffic.
- Motivation: Repair locality measures the number of other coded symbols accessed to reconstruct a failed symbol, with all-symbol locality requiring this for every coded symbol.The paper contrasts locality with repair bandwidth and disk-I/O as distinct repair metrics.
- Contributions: The paper derives an information-theoretic distance bound tying code distance d, locality r, and coded-symbol size α for linear and nonlinear scalar or vector codes.The bound generalizes prior scalar linear-code results.
- Contributions: When (r + 1) divides n, the distance bound is achievable over a sufficiently large finite field.The existence proof uses a finite, locality-aware flow-graph gadget and capacity-achieving multicast schemes, producing vector codes.
- Contributions: The explicit constructions are vector-linear LRCs with all-symbol locality, small per-symbol representations, and simple XOR-based node repairs.They are stated to be optimal when (r + 1) does not divide k.
2 Preliminaries
The preliminaries define the entropy-based framework for analyzing codes beyond linear scalar designs. They formalize encoding, storage cost, rate, minimum distance, and repair locality.
- Code model: The encoding function maps an M-bit file to n coded symbols, each with entropy α, which represents the storage cost per coded symbol.The file is modeled as an M-dimensional vector of independent uniform binary variables.
- Code model: The effective data rate is defined as total source entropy divided by the aggregate entropy of the stored encoded information.The framework keeps the discussion in bits while allowing q-ary generalization.
- Minimum code distance: Entropy characterizes code distance as the minimum erasures leaving non-erased coded symbols with entropy below the file size M.Equivalently, distance d means the file remains reconstructible after any d −1 erasures.
- Minimum code distance: The entropy-based distance definition applies to linear and nonlinear codes with arbitrary input and output symbol sizes and scalar or vector representations.This avoids dependence on generator-matrix rank arguments restricted to linear codes.
- Repair locality: A coded symbol Yi has repair locality r when a function reconstructs it from a set of r other coded symbols.The reconstruction is expressed as Yi = gi(YR(i)).
3 A Universal bound between code distance, locality, and storage cost
The paper derives a universal information-theoretic upper bound on the minimum distance of locally repairable codes, linking distance, locality, and per-symbol storage. The proof constructs a large low-entropy set using repair dependencies and establishes tightness when r + 1 divides n, while broader tightness remains open.
- Proof strategy: The proof lower-bounds the size of a largest coded-symbol set S whose joint entropy is below the file size M, then converts |S| into the distance bound d ≤ n − |S|.The construction iteratively collects repair-dependent (r + 1)-groups, whose joint entropy is at most r · α.
- Proof strategy: Each (r + 1)-group contains a coded symbol reconstructible from at most r others, yielding the dependencies used to grow S while controlling entropy.The argument uses only the structural property that every coded symbol has locality r.
- Universal distance bound: Theorem 1 bounds the minimum distance d of an (n,r,d,M,α)-LRC in terms of code length n, locality r, file size M, and symbol size α.The bound applies to locally repairable codes with all-symbol locality and is derived as an upper bound on minimum distance.
- Proof strategy: The algorithm terminates either after collecting complete (r + 1)-groups or after adding a partial final group, and both cases establish the theorem’s bound.The case analysis controls group sizes, entropy increments, and the number of iterations before the entropy threshold is reached.
- Tightness and scope: The distance bound is tight when (r + 1) divides n, but tightness under more general assumptions remains an open question.The paper also notes additional construction impossibilities for optimal linear all-symbol LRCs under certain parameter conditions.
4 Achievability of the Bound: Random LRCs
The paper proves that the locality–distance bound is achievable when r + 1 divides n by mapping capacity-achieving network schemes to locally repairable codes. Random linear network coding on a finite, locality-aware flow graph establishes distance, rate, and repair locality simultaneously.
- Existence result: Theorem 2 establishes the existence of (n,r,d,M,α)-LRCs when (r + 1)|n and r ≤ n − d, over a sufficiently large finite field.The resulting codes attain the stated distance bound.
- Flow-graph construction: The flow graph is directed, acyclic, finite, and locality aware, with decoding requirements designed for both global reconstruction and local repair.Its destinations represent subsets of n − d + 1 coded symbols, while additional local requirements operate within (r + 1)-groups.
- Network-to-code mapping: A capacity-achieving scheme on G(n,r,d,α) maps to a length-n code with α-bit coded symbols, distance d, and file size determined by the network capacity.Any n − d + 1 coded symbols can reconstruct the file.
- Capacity achievement: Random linear network coding achieves multicast capacity because it satisfies all destination decoding requirements with nonzero probability over a sufficiently large finite field.The construction uses local encoding functions on the flow graph and invokes the multicast capacity theorem.
- Locality conclusion: The resulting global encoding functions define an (n,r,d,M,α)-LRC because each coded symbol can be reconstructed from a subset of r other coded symbols.Locality follows from the additional local decoding requirements in the graph.
5 Locally Repairable Codes: Explicit Constructions
The explicit LRC construction combines MDS-encoded file parts with XOR parity blocks and circular placement to obtain low-locality repairs while retaining MDS-level distance. Its rate approaches the MDS rate as locality grows, while repair uses only block transfers and destination-side XORs.
- Construction goals: The construction targets distance d = n − k + 1 while providing locality r << n and sacrificing only a small fraction of the code rate.The construction is presented for the regime in which any k coded nodes reconstruct the k file symbols.
- Construction: Each of r file parts is independently encoded by an outer (n,k) MDS code, producing r coded vectors that are combined with one XOR parity vector.The MDS pre-codes use Reed-Solomon codes over a finite field of size at least n.
- Construction: The resulting (r + 1)n blocks are placed as r + 1 blocks per node, with each node storing r coded blocks from distinct vectors and one parity symbol.The placement is organized into (r + 1)-repair groups with circular index patterns.
- Repair: A failed node is repaired by contacting r nodes, downloading same-index blocks, and XORing them at the newcomer; no sender-side block combinations are needed.Repair is confined to one repair group, so the construction has locality r.
- Data reconstruction: Any k nodes reconstruct the file because they provide k coded blocks from each MDS-coded file part, enabling separate erasure decoding.The construction therefore has distance d = n − k + 1.
- Distance and code rate: The code rate is r/(r + 1) of the (n,k) MDS coding rate, with the loss caused by the extra XOR stripe required for local repairs.Choosing sub-linear locality r = f(k) yields r << k while the excess storage cost vanishes as n and k grow.
6 Conclusions
The paper introduces locally repairable codes that optimize repair locality while preserving reliability and storage efficiency. It establishes a bound linking code distance, locality, and storage cost, then gives achievable and explicit constructions.
- Locally repairable codes optimize repair efficiency according to the locality metric.The paper studies reconstruction of a failed coded symbol from a small number of other symbols.
- An information-theoretic bound links code distance, locality, and storage cost.This bound characterizes the best possible reliability under locality requirements.
- Vector-linear codes achieve the bound.
- An explicit construction recovers the encoded file from any k nodes while providing optimal locality.The construction uses a small field size and supports simple XOR-based repairs.