A Family of Optimal Locally Recoverable Codes

DOI10.1109/TIT.2014.2321280zbMATH Open1360.94385arXiv1311.3284OpenAlexW1997044393MaRDI QIDQ2986212FDOQ2986212

Authors: Itzhak Tamo, Alexander Barg 

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1311.3284

Recommendations

• A construction of optimal locally recoverable codes
• Constructions of Locally Recoverable Codes Which are Optimal
• Bounds on the Parameters of Locally Recoverable Codes
• Explicit Maximally Recoverable Codes With Locality
• A characterization of optimal locally repairable codes
• Bounds on the size of locally recoverable codes
• Construction of optimal locally recoverable codes and connection with hypergraph
• Constructions of optimal locally recoverable codes via Dickson polynomials
• Locally recoverable codes correcting many erasures over small fields
• New Constructions of Optimal Locally Recoverable Codes via Good Polynomials

zbMATH Keywords

LRC codescode cardinalitycodes with several disjoint recovering setslocality parametermaximum possible value of distance

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear codes (general theory) (94B05)

Cited In (75)

• Locally recoverable codes from towers of function fields
• Locally repairable codes with multiple repair sets based on packings of block size 4
• New constructions of optimal \((r, \delta)\)-LRCs via good polynomials
• Number theoretical locally recoverable codes
• New upper bounds and constructions of multi-erasure locally recoverable codes
• Optimal \((r,\delta )\)-LRCs from monomial-Cartesian codes and their subfield-subcodes
• Optimal ternary locally repairable codes
• The service rate region polytope
• Some new constructions of optimal linear codes and alphabet-optimal \((r, \delta)\)-locally repairable codes
• Some new classes of additive MDS and almost MDS codes over finite fields
• On information-theoretic secure multiparty computation with local repairability
• A characterization of optimal constacyclic locally repairable codes
• Toward good families of codes from towers of surfaces
• On finding the largest minimum distance of locally recoverable codes: a graph theory approach
• Optimal \((2, \delta)\) locally repairable codes via punctured simplex codes
• Cyclic locally recoverable LCD codes with the help of cyclotomic polynomials
• Some new constructions of optimal and almost optimal locally repairable codes
• Private information retrieval from locally repairable databases with colluding servers
• 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
• Codes for Distributed Storage
• Coding theory package for Macaulay2
• Locally recoverable codes from algebraic curves with separated variables
• Universal secure rank-metric coding schemes with optimal communication overheads
• Optimal cyclic \((r, \delta )\) locally repairable codes with unbounded length
• The complete hierarchical locality of the punctured simplex code
• The minimum locality of linear codes
• A new piggybacking design for systematic MDS storage codes
• A characterization of optimal locally repairable codes
• Title not available (Why is that?)
• On the locality of quasi-cyclic codes over finite fields
• Higher Hamming weights for locally recoverable codes on algebraic curves
• Coding for locality in reconstructing permutations
• Codes for distributed storage from 3-regular graphs
• Optimal binary linear locally repairable codes with disjoint repair groups
• RS-like locally recoverable codes with intersecting recovering sets
• New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
• Application of optimal \(p\)-ary linear codes to alphabet-optimal locally repairable codes
• Near MDS codes of non-elliptic-curve type from Reed-Solomon codes
• The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
• Optimal cyclic locally repairable codes with unbounded length from their zeros
• Good polynomials for optimal LRC of low locality
• Constructing Partial MDS Codes from Reducible Algebraic Curves
• A function field approach toward good polynomials for further results on optimal LRC codes
• Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
• Relaxed locally correctable codes
• Constructions of optimal locally recoverable codes via Dickson polynomials
• Architecture-aware coding for distributed storage: repairable block failure resilient codes
• Regular \((k, R, 1)\)-packings with \(\max(R)=3\) and their locally repairable codes
• On binary locally repairable codes with distance four
• Lifted Multiplicity Codes and the Disjoint Repair Group Property
• A class of almost MDS codes
• Constructions of \((r,t)\)-LRC based on totally isotropic subspaces in symplectic space over finite fields
• Optimal selection for good polynomials of degree up to five
• Codes in the sum-rank metric: fundamentals and applications
• Optimal RS-like LRC codes of arbitrary length
• Maximally Recoverable Codes for Grid-like Topologies
• Linear programming bounds for distributed storage codes
• Rank-metric codes and their applications
• Computing sharp recovery structures for locally recoverable codes
• Monomial-Cartesian codes and their duals, with applications to LCD codes, quantum codes, and locally recoverable codes
• Locality of optimal binary codes
• A new minimize matrix computation coding method for distributed storage systems
• Anticode-based locally repairable codes with high availability
• Sparse MDS matrices over small fields: a proof of the GM-MDS conjecture
• Title not available (Why is that?)
• Locality via partially lifted codes
• Optimal quaternary \((r,\delta)\)-locally recoverable codes: their structures and complete classification
• Minimum distance and parameter ranges of locally recoverable codes with availability from fiber products of curves
• The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes
• Integrated interleaved codes as locally recoverable codes: properties and performance
• Codes with locality from cyclic extensions of Deligne-Lusztig curves
• Locally recoverable \(J\)-affine variety codes
• Locally recoverable codes from rational maps

This page was built for publication: A Family of Optimal Locally Recoverable Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986212)