Repair Optimal Erasure Codes Through Hadamard Designs
Authors:
Top Cited Papers
- 21 January 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 59 (5) , 3021-3037
Abstract
In distributed storage systems that employ erasure coding, the issue of minimizing the total communication required to exactly rebuild a storage node after a failure arises. This repair bandwidth depends on the structure of the storage code and the repair strategies used to restore the lost data. Designing high-rate maximum-distance separable (MDS) codes that achieve the optimum repair communication has been a well-known open problem. Our work resolves, in part, this open problem. In this study, we use Hadamard matrices to construct the first explicit two-parity MDS storage code with optimal repair properties for all single node failures, including the parities. Our construction relies on a novel method of achieving perfect interference alignment over finite fields with a finite number of symbol extensions. We generalize this construction to design $m$-parity MDS codes that achieve the optimum repair communication for single systematic node failures.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Locally repairable codes2012
- Simple regenerating codes: Network coding for cloud storage2012
- Distributed Storage Codes With Repair-by-Transfer and Nonachievability of Interior Points on the Storage-Bandwidth TradeoffIEEE Transactions on Information Theory, 2011
- Self-repairing homomorphic codes for distributed storage systems2011
- Optimal recovery of single disk failure in RDP code storage systems2010
- Reducing repair traffic for erasure coding-based storage via interference alignment2009
- Interference Alignment and Degrees of Freedom of the $K$-User Interference ChannelIEEE Transactions on Information Theory, 2008
- Pyramid Codes: Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems2007
- A Random Linear Network Coding Approach to MulticastIEEE Transactions on Information Theory, 2006
- Randomized algorithmsACM Computing Surveys, 1996