Bounds on the Size of Locally Recoverable Codes

Viveck R. Cadambe, Arya Mazumdar

Research output: Contribution to journalArticlepeer-review

82 Scopus citations

Abstract

In a locally recoverable or repairable code, 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 (erasure). A common objective is to repair the node by downloading data from as few other storage nodes as possible. In this paper, we bound the minimum distance of a code in terms of its length, size, and locality. Unlike the previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence, the Simplex codes are the first example of an optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds.

Original languageEnglish (US)
Article number7247728
Pages (from-to)5787-5794
Number of pages8
JournalIEEE Transactions on Information Theory
Volume61
Issue number11
DOIs
StatePublished - Nov 1 2015

Bibliographical note

Funding Information:
This work was supported by NSF through the Division of Computing and Communication Foundations under Grant 1318093 and Grant 1453121.

Keywords

  • Locally recoverable codes
  • binary codes
  • distributed storage
  • erasure correction

Fingerprint Dive into the research topics of 'Bounds on the Size of Locally Recoverable Codes'. Together they form a unique fingerprint.

Cite this