Local recovery properties of capacity achieving codes

Arya Mazumdar, Venkat Chandar, Gregory W. Wornell

Abstract

A code is called locally recoverable or repairable if any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure. A common objective is to repair the node by downloading data from as few other storage node as possible. In this paper we study the basic error-correcting properties of a locally recoverable code. We provide tight upper and lower bound on the local-recoverability of a code that achieves capacity of a symmetric channel. In particular it is shown that, if the code-rate is e less than the capacity then for the optimal codes, the maximum number of codeword symbols required to recover one lost symbol must scale as log 1/ϵ.
BibTeX
@inproceedings{mazumdar2013local,
  author = {Arya Mazumdar and Venkat Chandar and Gregory W. Wornell},
  title = {{Local recovery properties of capacity achieving codes}},
  booktitle = {ITA},
  year = {2013},
  doi = {10.1109/ita.2013.6502958},
}

Loading related content...

Figure