TY - GEN
T1 - Repair optimal erasure codes through Hadamard designs
AU - Papailiopoulos, Dimitris S.
AU - Dimakis, Alexandros G.
AU - Cadambe, Viveck R.
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2011
Y1 - 2011
N2 - 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 parity nodes. Our construction relies on a novel method of achieving perfect interference alignment over finite fields with a finite file size, or number of symbol extensions.
AB - 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 parity nodes. Our construction relies on a novel method of achieving perfect interference alignment over finite fields with a finite file size, or number of symbol extensions.
UR - http://www.scopus.com/inward/record.url?scp=84856083898&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84856083898&partnerID=8YFLogxK
U2 - 10.1109/Allerton.2011.6120328
DO - 10.1109/Allerton.2011.6120328
M3 - Conference contribution
AN - SCOPUS:84856083898
SN - 9781457718168
T3 - 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
SP - 1382
EP - 1389
BT - 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
T2 - 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
Y2 - 28 September 2011 through 30 September 2011
ER -