[Jump to code hierarchy]

Code with locality

Description

A code has \((r,\delta)\) locality if each codeword coordinate belongs to a repair group of size at most \(r+\delta-1\) whose restricted code has minimum distance at least \(\delta\) [1; Sec. 31.3.4.5]. Equivalently, given a codeword \(c\) and coordinate \(c_i\), there exists a coordinate set \(S_i\) of size \(\leq r+\delta-1\) containing \(i\) such that the restriction \(C_{|S_i}\) has minimum distance at least \(\delta\).

Protection

There is a generalized Singleton minimum distance bound [2], \begin{align} d\leq n-k+1-(\left\lceil k/r\right\rceil -1)(\delta-1)~, \tag*{(1)}\end{align} with codes saturating this bound being optimal codes with locality. The \(\delta=2\) case recovers optimal LRCs.

Member of code lists

Primary Hierarchy

Classical Domain
Error-correcting code (ECC)
Block code
Distributed-storage code
Parents
Distributed-storage code
Code with locality
Children
Locally recoverable code (LRC)LCC GRM MDS GRS \(q\)-ary LDPC
An LRC of locality \(r\) is a code with \((r,2)\) locality [1; Sec. 31.3.4.5].
Maximally recoverable (MR) code

References

[1]
V. Ramkumar, M. Vajha, S. B. Balaji, M. Nikhil Krishnan, B. Sasidharan, P. Vijay Kumar, “Codes for Distributed Storage.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[2]
N. Prakash, G. M. Kamath, V. Lalitha, and P. V. Kumar, “Optimal Linear Codes with a Local-Error-Correction Property”, (2012) arXiv:1202.2414
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: code_with_locality

Cite as:
“Code with locality”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/code_with_locality
BibTeX:
@incollection{eczoo_code_with_locality, title={Code with locality}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/code_with_locality} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/code_with_locality

Cite as:

“Code with locality”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/code_with_locality

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/block/distributed_storage/lrc/code_with_locality.yml.