Repair Optimal Erasure Codes Through Hadamard Designs

DOI10.1109/TIT.2013.2241819MaRDI QIDQ2989268zbMATH OpenOpenAlexFDO

Authors Dimitris S. Papailiopoulos, Alexandros G. Dimakis, Viveck R. Cadambe

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.1634

Mathematics Subject Classification ID

Other designs, configurations (05B30) Other types of codes (94B60)

Abstract: 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}.

Cited in

(14)

• A new hybrid coding scheme: homomorphic minimum bandwidth repairing codes
• Architecture-aware coding for distributed storage: repairable block failure resilient codes
• Construction of minimum bandwidth regenerating codes with combinatorial design
• Erasures Repair for Decreasing Monomial-Cartesian and Augmented Reed-Muller Codes of High Rate
• Determinant Codes With Helper-Independent Repair for Single and Multiple Failures
• Codes for Distributed Storage
• A class of minimum storage cooperative regenerating codes with low access property
• Constructing leakage-resilient Shamir's secret sharing: over composite order fields
• Towards breaking the half-barrier of local leakage-resilient Shamir's secret sharing
• Physical-bit leakage resilience of linear code-based secret sharing
• Construction of binary cooperative MSR codes with multiple repair degrees
• A new repair-efficient piggybacking design for systematic nodes
• Distributed repairing multiple erasures in Reed-Solomon codes
• (1+)-optimal MDS codes: contacting any set of helper nodes smaller than n-1

This page was built for publication: Repair Optimal Erasure Codes Through Hadamard Designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989268)