Bounds on the Size of Locally Recoverable Codes

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 (er...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2015-11, Vol.61 (11), p.5787-5794
Main Authors: Cadambe, Viveck R., Mazumdar, Arya
Format: Article
Language:English
Subjects:
Binary codes
Codes
Coding
Concatenated codes
Constants
Information theory
Linear codes
Maintenance engineering
Mathematical models
Optimization
Parity check codes
Symbols
Upper bound
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2015.2477406