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
(only showing first 100 items - show all)- Anticode-based locally repairable codes with high availability
- Universal secure rank-metric coding schemes with optimal communication overheads
- Architecture-aware coding for distributed storage: repairable block failure resilient codes
- Locally recoverable codes from rational maps
- Locally recoverable \(J\)-affine variety codes
- RS-like locally recoverable codes with intersecting recovering sets
- Good polynomials for optimal LRC of low locality
- Locally repairable codes with high availability based on generalised quadrangles
- The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes
- Johnson graph codes
- Infinite families of optimal linear codes and their applications to distributed storage systems
- On the locality of quasi-cyclic codes over finite fields
- Application of optimal \(p\)-ary linear codes to alphabet-optimal locally repairable codes
- Optimal cyclic locally repairable codes with unbounded length from their zeros
- Locally recoverable codes from algebraic curves with separated variables
- Linear programming bounds for distributed storage codes
- Linearized decomposition codes and finite integer set coverings
- Two classes of optimal LRCs with information (r, t)-locality
- Constructions of optimal locally recoverable codes via Dickson polynomials
- The complete hierarchical locality of the punctured simplex code
- New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
- Optimal cyclic \((r, \delta )\) locally repairable codes with unbounded length
- A new piggybacking design for systematic MDS storage codes
- Self-repairing codes
- Locality of optimal binary codes
- On the locality of codeword symbols in non-linear codes
- A study of the performance of novel storage-centric repairable codes
- On binary locally repairable codes with distance four
- A class of almost MDS codes
- Optimal selection for good polynomials of degree up to five
- The minimum locality of linear codes
- Perfect LRCs and k-optimal LRCs
- Optimal quaternary \((r,\delta)\)-locally recoverable codes: their structures and complete classification
- Constructions of near MDS codes which are optimal locally recoverable codes
- Higher Hamming weights for locally recoverable codes on algebraic curves
- Outlaw distributions and locally decodable codes
- High-entropy dual functions over finite fields and locally decodable codes
- Constructions of \((r,t)\)-LRC based on totally isotropic subspaces in symplectic space over finite fields
- Locality via partially lifted codes
- scientific article; zbMATH DE number 7378653 (Why is no real title available?)
- Constructions of maximally recoverable local reconstruction codes via function fields
- Construction of optimal locally recoverable codes and connection with hypergraph
- A general family of MSRD codes and PMDS codes with smaller field sizes from extended Moore matrices
- Sparse hypergraphs with applications to coding theory
- Optimal binary linear locally repairable codes with disjoint repair groups
- Locally recoverable codes from planar graphs
- Relaxed locally correctable codes
- Rank-metric codes and their applications
- Codes for Distributed Storage
- Codes in the sum-rank metric: fundamentals and applications
- A characterization of optimal locally repairable codes
- Three new constructions of optimal linear codes with few weights
- Near MDS codes of non-elliptic-curve type from Reed-Solomon codes
- New upper bounds and constructions of multi-erasure locally recoverable codes
- A construction of optimal locally recoverable codes
- A family of codes with variable locality and availability
- Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
- Locally recoverable codes from towers of function fields
- New constructions of optimal \((r, \delta)\)-LRCs via good polynomials
- Constructions of cyclic codes and extended primitive cyclic codes with their applications
- Near MDS codes with dimension 4 and their application in locally recoverable codes
- New infinite families of near MDS codes holding \(t\)-designs
- Near-MDS codes from maximal arcs in \(\mathrm{PG}(2,q)\)
- A characterization of optimal constacyclic 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
- Locally repairable codes with multiple repair sets based on packings of block size 4
- Clay and product-matrix MSR codes with locality
- Extension-based constructions of locally repairable fractional repetition codes
- Optimal (r, )-LRCs from monomial-Cartesian codes and their subfield-subcodes
- Optimal ternary locally repairable codes
- 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
- On information-theoretic secure multiparty computation with local repairability
- On finding the largest minimum distance of locally recoverable codes: a graph theory approach
- Optimal (2, ) locally repairable codes via punctured simplex codes
- Storage codes and recoverable systems on lines and grids
- Some new constructions of optimal and almost optimal locally repairable codes
- Cyclic locally recoverable LCD codes with the help of cyclotomic polynomials
- Easy repair via codes with simplex locality
- Locally recoverable algebro-geometric codes from projective bundles
- Weight distributions of two classes of optimal (r, )-locally repairable codes
- Quantum (r, )-locally recoverable codes
- Codes with hierarchical locality on Artin-Schreier surfaces
- The augmented codes of a family of linear codes with locality 2
- A class of locally recoverable codes over finite chain rings
- Bounds on the size of (r,)-locally repairable codes for fixed values q and d
- A new construction of maximally recoverable codes with hierarchical locality
- Introducing locality in some generalized AG codes
- A family of self-orthogonal divisible codes with locality 2
- Optimal locally repairable codes with multiple repair sets based on 2-regular packings
- Two families of optimal quantum locally recoverable codes
- Algebraic hierarchical locally recoverable codes with nested affine subspace recovery
- Infinite families of linear codes over finite fields with new parameters and their hull dimensions
- Explicit constructions of optimal vector locally repairable codes
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)
