Computer Science – Information Theory
Scientific paper
2011-06-08
Computer Science
Information Theory
19 pages, 9 figures
Scientific paper
In distributed storage systems that employ erasure coding, the issue of minimizing the total {\it 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. In this work, we use Hadamard matrices to construct the first explicit 2-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 file size, or number of extensions. We generalize this construction to design $m$-parity MDS codes that achieve the optimum repair communication for single systematic node failures and show that there is an interesting connection between our $m$-parity codes and the systematic-repair optimal permutation-matrix based codes of Tamo {\it et al.} \cite{Tamo} and Cadambe {\it et al.} \cite{PermCodes_ISIT, PermCodes}.
Cadambe Viveck R.
Dimakis Alexandros G.
Papailiopoulos Dimitris S.
No associations
LandOfFree
Repair Optimal Erasure Codes through Hadamard Designs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Repair Optimal Erasure Codes through Hadamard Designs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Repair Optimal Erasure Codes through Hadamard Designs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-320888