Repair Optimal Erasure Codes through Hadamard Designs

Original · EN

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. 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 et al. Tamo and Cadambe et al. PermCodesᵢSIT, PermCodes.