On the Locality of Codeword Symbols
From MaRDI portal
Publication:2989710
DOI10.1109/TIT.2012.2208937zbMATH Open1364.94603arXiv1106.3625OpenAlexW1993830711MaRDI QIDQ2989710FDOQ2989710
Authors: Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin 
Publication date: 8 June 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: Consider a linear [n,k,d]_q code C. We say that that i-th coordinate of C has locality r, if the value at this coordinate can be recovered from accessing some other r coordinates of C. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n-k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst-case distance and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality for parity checks and the ability to correct erasures beyond the minimum distance.
Full work available at URL: https://arxiv.org/abs/1106.3625
Cited In (89)
- Codes for Distributed Storage
- A construction of optimal locally recoverable codes
- Johnson graph codes
- Constructions of near MDS codes which are optimal locally recoverable codes
- Infinite families of optimal linear codes and their applications to distributed storage systems
- A study of the performance of novel storage-centric repairable codes
- Locally recoverable codes from algebraic curves with separated variables
- Recursive methods for some problems in coding and random permutations
- Universal secure rank-metric coding schemes with optimal communication overheads
- Optimal cyclic \((r, \delta )\) locally repairable codes with unbounded length
- Title not available (Why is that?)
- The complete hierarchical locality of the punctured simplex code
- The minimum locality of linear codes
- A new piggybacking design for systematic MDS storage codes
- Perfect LRCs and \(k\)-optimal LRCs
- 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
- 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
- Optimal cyclic locally repairable codes with unbounded length from their zeros
- Codes in the Sum-Rank Metric: Fundamentals and Applications
- Locality via Partially Lifted Codes
- Good polynomials for optimal LRC of low locality
- Rank-Metric Codes and Their Applications
- Title not available (Why is that?)
- Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
- Constructions of optimal locally recoverable codes via Dickson polynomials
- Architecture-aware coding for distributed storage: repairable block failure resilient codes
- Self-repairing codes
- On binary locally repairable codes with distance four
- A class of almost MDS codes
- A General Family of MSRD Codes and PMDS Codes with Smaller Field Sizes from Extended Moore Matrices
- Galois geometries and coding theory
- Sparse Hypergraphs with Applications to Coding Theory
- Optimal selection for good polynomials of degree up to five
- Optimal RS-like LRC codes of arbitrary length
- On the locality of codeword symbols in non-linear codes
- Linearized decomposition codes and finite integer set coverings
- Linear programming bounds for distributed storage codes
- A family of codes with variable locality and availability
- Locally repairable codes with high availability based on generalised quadrangles
- Computing sharp recovery structures for locally recoverable codes
- Hamming and simplex codes for the sum-rank metric
- Locality of optimal binary codes
- Anticode-based locally repairable codes with high availability
- Title not available (Why is that?)
- Optimal Binary Linear Locally Repairable Codes with Disjoint Repair Groups
- Optimal quaternary \((r,\delta)\)-locally recoverable codes: their structures and complete classification
- The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes
- Two classes of optimal LRCs with information \((r, t)\)-locality
- Locally recoverable \(J\)-affine variety codes
- Locally recoverable codes from rational maps
- Title not available (Why is that?)
- High-entropy dual functions over finite fields and locally decodable codes
- 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
- Clay and product-matrix MSR codes with locality
- Extension-based constructions of locally repairable fractional repetition codes
- New infinite families of near MDS codes holding \(t\)-designs
- Constructions of (r,t)-LRC Based on Totally Isotropic Subspaces in Symplectic Space Over Finite Fields
- 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
- Outlaw distributions and locally decodable codes
- Near MDS codes with dimension 4 and their application in locally recoverable codes
- Near-MDS codes from maximal arcs in \(\mathrm{PG}(2,q)\)
- Four new families of NMDS codes with dimension 4 and their applications
- Locally maximal recoverable codes and LMR-LCD codes
- Some new constructions of optimal linear codes and alphabet-optimal \((r, \delta)\)-locally repairable codes
- Curve-lifted codes for local recovery using lines
- Three new constructions of optimal linear codes with few weights
- On information-theoretic secure multiparty computation with local repairability
- A characterization of optimal constacyclic locally repairable codes
- Constructions of cyclic codes and extended primitive cyclic codes with their applications
- On finding the largest minimum distance of locally recoverable codes: a graph theory approach
- Storage codes and recoverable systems on lines and grids
- 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
- On locality of binary distance-optimal codes
- Constacyclic locally recoverable codes from their duals
This page was built for publication: On the Locality of Codeword Symbols
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989710)
