Locally Repairable Codes. (arXiv:1206.3804v1 [cs.IT])

from cs.NI updates on arXiv.org http://arxiv.org/abs/1206.3804

One main challenge in the design of distributed storage codes is the {\it
Exact Repair Problem}: if a node storing encoded information fails, to maintain
the same level of reliability, we need to exactly regenerate what was lost in a
new node. A major open problem in this area has been the design of codes that
{\it i)} admit exact and low cost repair of nodes and {\it ii)} have
arbitrarily high data rates.

In this paper, we are interested in the metric of {\it repair locality},
which corresponds to the the number of disk accesses required during a node
repair. Under this metric we characterize an information theoretic trade-off
that binds together locality, code distance, and storage cost per node. We
introduce {\it Locally repairable codes} (LRCs) which are shown to achieve this
tradeoff. The achievability proof uses a “locality aware” flow graph gadget
which leads to a randomized code construction. We then present the {\it first}
explicit construction of LRCs that can achieve arbitrarily high data-rates.

Advertisements