Optimal Locally Repairable Codes and Connections to Matroid Theory
From MaRDI portal
Abstract: 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.
Recommendations
- On the Combinatorics of Locally Repairable Codes via Matroid Theory
- A characterization of optimal locally repairable codes
- Optimal Locally Repairable Codes: An Improved Bound and Constructions
- On Optimal Locally Repairable Codes With Multiple Disjoint Repair Sets
- An Integer Programming-Based Bound for Locally Repairable Codes
- Optimal Locally Repairable Codes Via Elliptic Curves
- Constructions of two classes of optimal locally repairable codes
- Bounds and Constructions of Locally Repairable Codes: Parity-Check Matrix Approach
- On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes
- Application of optimal \(p\)-ary linear codes to alphabet-optimal locally repairable codes
Cited in
(32)- RS-like locally recoverable codes with intersecting recovering sets
- Good polynomials for optimal LRC of low locality
- The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes
- Optimal cyclic locally repairable codes with unbounded length from their zeros
- Linear programming bounds for distributed storage codes
- New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
- Optimal cyclic \((r, \delta )\) locally repairable codes with unbounded length
- Perfect LRCs and k-optimal LRCs
- Optimal quaternary \((r,\delta)\)-locally recoverable codes: their structures and complete classification
- Constructions of \((r,t)\)-LRC based on totally isotropic subspaces in symplectic space over finite fields
- scientific article; zbMATH DE number 7378653 (Why is no real title available?)
- Constructing Partial MDS Codes from Reducible Algebraic Curves
- Construction of optimal locally recoverable codes and connection with hypergraph
- Optimal binary linear locally repairable codes with disjoint repair groups
- Codes for Distributed Storage
- Codes in the sum-rank metric: fundamentals and applications
- A characterization of optimal locally repairable codes
- Parametric matroid interdiction
- Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
- Optimal binary and ternary locally repairable codes with minimum distance 6
- On Singleton-type bound of locally repairable codes
- Constacyclic locally recoverable codes from their duals
- Optimal (r, )-LRCs from monomial-Cartesian codes and their subfield-subcodes
- On finding the largest minimum distance of locally recoverable codes: a graph theory approach
- Locally recoverable algebro-geometric codes from projective bundles
- Quantum (r, )-locally recoverable codes
- Bounds on the size of (r,)-locally repairable codes for fixed values q and d
- Efficient representation of lattice path matroids
- Two families of optimal quantum locally recoverable codes
- Hull dimension of optimal binary LRCs with availability
- LRCS: duality, LP bounds, and field size
- Optimal RS-like LRC codes of arbitrary length
This page was built for publication: Optimal Locally Repairable Codes and Connections to Matroid Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976387)
