Locally Repairable Codes
By Dimitris Papailiopoulos, A. Dimakis. IEEE Transactions on Information Theory, 2012
542 citations recorded by the source corpus.
Distributed storage systems for large-scale applications typically use replication for reliability. Recently, erasure codes were used to reduce the large storage overhead, while increasing data reliability. A main limitation of off-the-shelf erasure codes is their high-repair cost during single node failure events. A major open problem in this area has been the design of codes that: 1) are repair efficient and 2) achieve arbitrarily high data rates. In this paper, we explore the repair metric of locality, which corresponds to the number of disk accesses required during a single node repair. Under this metric, we characterize an information theoretic tradeoff that binds together the locality, code distance, and storage capacity of each node. We show the existence of optimal locally repairable codes (LRCs) that achieve this tradeoff. The achievability proof uses a locality aware flow-graph gadget, which leads to a randomized code construction. Finally, we present an optimal and explicit LRC that achieves arbitrarily high data rates. Our locality optimal construction is based on simple combinations of Reed-Solomon blocks.
Subfields: Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/0a5e26f4bc91585ba0938676edd0f55d1c169072
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Ankit Singh Rawat
- A. Dimakis
- Sriram Vishwanath
- Dimitris Papailiopoulos
- Itzhak Tamo
- Zhao Song
- Alexander Barg
- Sennur Ulukus
Citations in the corpus
- Private information retrieval for coded storage (2014, background): “For example, one may require that for any k ∈ K, there exists a subset α ⊆ K \ {k} of size at most r such that H(Xk|Xj , j ∈ α) = 0 [3], [15].”
- Locality and Availability in Distributed Storage (2014, background): “Note that for t = 1, the bound in (6) reduces to the distance bound for codes with r-locality [10], [12], i.”
- A Family of Optimal Locally Recoverable Codes (2013, background): “Remark: The bound on the distance is due to [9], [20], where it appears with a different proof.”
- Batch codes through dense graphs without short cycles (2014, background): “This was re-4 cently further generalized for nonlinear codes [25] and several explicit constructions of locally repairable codes have been investigated ( e.g. [18, 24, 30, 37, 38]).”