A family of optimal locally recoverable codes

Abstract

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

Minor changes. This is the final published version of the paper

References in corpus (3)

• Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction
• Optimal Repair of MDS Codes in Distributed Storage via Subspace Interference Alignment
• Codes with Local Regeneration

Cited by in corpus (110)

• Binary Cyclic Codes that are Locally Repairable
• Cooperative Local Repair in Distributed Storage
• Cyclic LRC Codes, binary LRC codes, and upper bounds on the distance of cyclic codes
• Locally recoverable codes from algebraic curves and surfaces
• Optimal Linear and Cyclic Locally Repairable Codes over Small Fields
• Constructions and Properties of Linear Locally Repairable Codes
• Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes
• Constructions of Locally Recoverable Codes which are Optimal
• Locally Repairable Codes with Functional Repair and Multiple Erasure Tolerance
• Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
• Codes with Locality for Two Erasures
• Bounds and Constructions of Locally Repairable Codes: Parity-check Matrix Approach
• Construction of optimal locally repairable codes via automorphism groups of rational function fields
• Construction of optimal locally recoverable codes and connection with hypergraph
• Coding theory package for Macaulay2
• Polar decreasing monomial-Cartesian codes
• Erasure codes with simplex locality
• Binary Codes with Locality for Multiple Erasures Having Short Block Length
• Explicit optimal-length locally repairable codes of distance 5
• Rack-Aware Regenerating Codes with Multiple Erasure Tolerance
• Locally Repairable Codes with Unequal Local Erasure Correction
• Monomial-Cartesian codes and their duals, with applications to LCD codes, quantum codes, and locally recoverable codes
• Higher Hamming weights for locally recoverable codes on algebraic curves
• Optimal Binary Locally Repairable Codes via Anticodes
• High-rate storage codes on triangle-free graphs
• Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization
• Locally Repairable Convolutional Codes with Sliding Window Repair
• Alphabet-Dependent Bounds for Linear Locally Repairable Codes Based on Residual Codes
• Optimal repairing schemes for Reed-Solomon codes with alphabet sizes linear in lengths under the rack-aware model
• Achieving Arbitrary Locality and Availability in Binary Codes
• Some Improvements on Locally Repairable Codes
• A Construction of Maximally Recoverable Codes with Order-Optimal Field Size
• Locally recoverable codes on algebraic curves
• Optimal binary linear locally repairable codes with disjoint repair groups
• A locality-based approach for coded computation
• Binary Linear Locally Repairable Codes
• PMDS Array Codes With Small Sub-packetization, Small Repair Bandwidth/Rebuilding Access
• Explicit Construction of Minimum Bandwidth Rack-Aware Regenerating Codes
• Codes With Hierarchical Locality
• Weight Enumerators and Higher Support Weights of Maximally Recoverable Codes
• On minimum distance of locally repairable codes
• Algebraic geometry codes and some applications
• Rack-Aware Regenerating Codes with Fewer Helper Racks
• Binary Codes with Locality for Four Erasures
• Optimal locally repairable codes of distance $3$ and $4$ via cyclic codes
• Erasure Coding for Distributed Storage: An Overview
• A Connection Between Locally Repairable Codes and Exact Regenerating Codes
• Binary Locally Repairable Codes ---Sequential Repair for Multiple Erasures
• Centralized Multi-Node Repair Regenerating Codes
• Linear Locally Repairable Codes with Random Matrices
• On Partial Maximally-Recoverable and Maximally-Recoverable Codes
• On Optimal Ternary Locally Repairable Codes
• A New Piggybacking Design for Systematic MDS Storage Codes
• Optimal $(2,\delta )$ Locally Repairable Codes via Punctured Simplex Codes
• Optimal $(r,\delta )$-LRCs from monomial-Cartesian codes and their subfield-subcodes
• Cyclic Codes with Locality and Availability
• On Locally Recoverable (LRC) Codes
• Constructions of Optimal Cyclic $(r,\delta )$ Locally Repairable Codes
• Bounds on the Parameters of Locally Recoverable Codes
• The minimum linear locality of linear codes
• Bounds on Codes with Locality and Availability
• A Function Field Approach Toward Good Polynomials for Further Results on Optimal LRC Codes
• Constructing Partial MDS Codes from Reducible Curves
• New MDS codes with small sub-packetization and near-optimal repair bandwidth
• Locally rewritable codes for resistive memories
• Irregular Recovery and Unequal Locality for Locally Recoverable Codes with Availability
• Uniform Minors in Maximally Recoverable Codes
• Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes
• Bounds and Constructions for Linear Locally Repairable Codes over Binary Fields
• On the Weight Hierarchy of Locally Repairable Codes
• Construction of asymptotically good locally repairable codes via automorphism groups of function fields
• On Sequential Locally Repairable Codes
• Bandwidth Cost of Code Conversions in Distributed Storage: Fundamental Limits and Optimal Constructions
• Constructions of Binary Optimal Locally Repairable Codes via Intersection Subspaces
• Lower Rate Bounds for Hermitian-Lifted Codes for Odd Prime Characteristic
• CausalEC: A Causally Consistent Data Storage Algorithm based on Cross-Object Erasure Coding
• Storage Codes with Flexible Number of Nodes
• New Constructions of Optimal Locally Repairable Codes with Super-Linear Length
• A Tight Rate Bound and Matching Construction for Locally Recoverable Codes with Sequential Recovery From Any Number of Multiple Erasures
• On Optimal Locally Repairable Codes with Super-Linear Length
• Efficiently repairing algebraic geometry codes
• Generalized and Extended Product Codes
• Erasure codes with symbol locality and group decodability for distributed storage
• A Study on the Impact of Locality in the Decoding of Binary Cyclic Codes
• How arithmetic and geometry make error correcting codes better
• Locally Repairable Codes with Multiple $(r_i,{\delta }_i)$-Localities
• New Bounds on the Field Size for Maximally Recoverable Codes Instantiating Grid-like Topologies
• Locality and Availability of Array Codes Constructed from Subspaces
• Codes with Combined Locality and Regeneration Having Optimal Rate, $d_{\text{min}}$ and Linear Field Size
• Optimal cyclic $(r,\delta )$ locally repairable codes with unbounded length
• Multi-Block Interleaved Codes for Local and Global Read Access
• Repeated-root Constacyclic Codes with Optimal Locality
• Optimal Locally Repairable Systematic Codes Based on Packings
• Duality between erasures and defects
• Integrated Interleaved Codes as Locally Recoverable Codes: Properties and Performance
• Erasure Codes for Distributed Storage: Tight Bounds and Matching Constructions
• The group structures of automorphism groups of elliptic function fields over finite fields and their applications to optimal locally repairable codes
• New Constructions of Optimal Cyclic (r,δ) Locally Repairable Codes from Their Zeros
• Cyclic and convolutional codes with locality
• Codes for distributed storage from 3-regular graphs
• Mathematical LoRE: Local Recovery of Erasures using Polynomials, Curves, Surfaces, and Liftings
• Convertible Codes: Efficient Conversion of Coded Data in Distributed Storage
• Three New Infinite Families of Optimal Locally Repairable Codes from Matrix-Product Codes
• Locally Recoverable Codes with availability from a family of fibered surfaces
• Multi-Erasure Locally Recoverable Codes Over Small Fields For Flash Memory Array
• A new construction of nonlinear codes via rational function fields
• Codes with Unequal Disjoint Local Erasure Correction Constraints
• The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
• Locally recoverable codes from automorphism groups of function fields of genus $g\ge 1$
• On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes