2011/06/08 by Papailiopoulos, Dimitris S., Dimakis, Alexandros G., Cadambe, Viveck R. · 2 citations
#Distributed #FOS: Computer and information sciences #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1106.1634
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. \citeTamo and Cadambe \it et al. \citePermCodesISIT, PermCodes.