On the Locality of Codeword Symbols
From MaRDI portal
Publication:2989710
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.
Cited in
(89)- Linearized decomposition codes and finite integer set coverings
- A class of almost MDS codes
- Optimal binary linear locally repairable codes with disjoint repair groups
- Locality via partially lifted codes
- Locally recoverable codes from algebraic curves with separated variables
- Codes in the sum-rank metric: fundamentals and applications
- Near MDS codes of non-elliptic-curve type from Reed-Solomon codes
- Optimal cyclic locally repairable codes with unbounded length from their zeros
- Universal secure rank-metric coding schemes with optimal communication overheads
- Two classes of optimal LRCs with information \((r, t)\)-locality
- Sparse hypergraphs with applications to coding theory
- scientific article; zbMATH DE number 7561561 (Why is no real title available?)
- A characterization of optimal locally repairable codes
- Locally recoverable \(J\)-affine variety codes
- Optimal cyclic \((r, \delta )\) locally repairable codes with unbounded length
- Recursive methods for some problems in coding and random permutations
- On the locality of quasi-cyclic codes over finite fields
- Anticode-based locally repairable codes with high availability
- On binary locally repairable codes with distance four
- Good polynomials for optimal LRC of low locality
- Optimal RS-like LRC codes of arbitrary length
- The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes
- Higher Hamming weights for locally recoverable codes on algebraic curves
- Codes for Distributed Storage
- Computing sharp recovery structures for locally recoverable codes
- Hamming and simplex codes for the sum-rank metric
- Linear programming bounds for distributed storage codes
- Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
- Relaxed locally correctable codes
- A family of codes with variable locality and availability
- scientific article; zbMATH DE number 7378653 (Why is no real title available?)
- Locally recoverable codes from planar graphs
- Self-repairing codes
- RS-like locally recoverable codes with intersecting recovering sets
- The complete hierarchical locality of the punctured simplex code
- Constructions of near MDS codes which are optimal locally recoverable codes
- On the locality of codeword symbols in non-linear codes
- Rank-metric codes and their applications
- A general family of MSRD codes and PMDS codes with smaller field sizes from extended Moore matrices
- A construction of optimal locally recoverable codes
- Constructions of optimal locally recoverable codes via Dickson polynomials
- Optimal quaternary \((r,\delta)\)-locally recoverable codes: their structures and complete classification
- The minimum locality of linear codes
- 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
- Infinite families of optimal linear codes and their applications to distributed storage systems
- Locally repairable codes with high availability based on generalised quadrangles
- Locality of optimal binary codes
- A study of the performance of novel storage-centric repairable codes
- Optimal selection for good polynomials of degree up to five
- Johnson graph codes
- A new piggybacking design for systematic MDS storage codes
- Perfect LRCs and \(k\)-optimal LRCs
- Architecture-aware coding for distributed storage: repairable block failure resilient codes
- Locally recoverable codes from rational maps
- scientific article; zbMATH DE number 7561591 (Why is no real title available?)
- Galois geometries and coding theory
- Storage codes and recoverable systems on lines and grids
- Optimal \((r,\delta )\)-LRCs from monomial-Cartesian codes and their subfield-subcodes
- Optimal ternary locally repairable codes
- New constructions of optimal \((r, \delta)\)-LRCs via good polynomials
- Outlaw distributions and locally decodable codes
- Near-MDS codes from maximal arcs in \(\mathrm{PG}(2,q)\)
- 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
- Constacyclic locally recoverable codes from their duals
- Optimal binary and ternary locally repairable codes with minimum distance 6
- High-entropy dual functions over finite fields and locally decodable codes
- Clay and product-matrix MSR codes with locality
- On finding the largest minimum distance of locally recoverable codes: a graph theory approach
- Extension-based constructions of locally repairable fractional repetition codes
- A characterization of optimal constacyclic locally repairable codes
- Locally recoverable codes from towers of function fields
- 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
- Locally repairable codes with multiple repair sets based on packings of block size 4
- New infinite families of near MDS codes holding \(t\)-designs
- New upper bounds and constructions of multi-erasure locally recoverable codes
- On Singleton-type bound of locally repairable codes
- On locality of binary distance-optimal codes
- Constructions of cyclic codes and extended primitive cyclic codes with their applications
- Three new constructions of optimal linear codes with few weights
- Near MDS codes with dimension 4 and their application in locally recoverable codes
- Curve-lifted codes for local recovery using lines
- On information-theoretic secure multiparty computation with local repairability
- Constructions of \((r,t)\)-LRC based on totally isotropic subspaces in symplectic space over finite fields
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)
