Explicit MDS Codes for Optimal Repair Bandwidth
Preprint
Abstract
MDS codes are erasure-correcting codes that can correct the maximum number of erasures for a given number of redundancy or parity symbols. If an MDS code has $r$ parities and no more than $r$ erasures occur, then by transmitting all the remaining data in the code, the original information can be recovered. However, it was shown that in order to recover a single symbol erasure, only a fraction of $1/r$ of the information needs to be transmitted. This fraction is called the repair bandwidth (fraction). Explicit code constructions were given in previous works. If we view each symbol in the code as a vector or a column over some field, then the code forms a 2D array and such codes are especially widely used in storage systems. In this paper, we address the following question: given the length of the column $l$, number of parities $r$, can we construct high-rate MDS array codes with optimal repair bandwidth of $1/r$, whose code length is as long as possible? In this paper, we give code constructions such that the code length is $(r+1)\log_r l$.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code ConstructionsIEEE Transactions on Information Theory, 2011
- Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix ConstructionIEEE Transactions on Information Theory, 2011
- Permutation code: Optimal exact-repair of a single failed node in MDS code based distributed storage systems2011
- Exact-Repair MDS Code Construction Using Interference AlignmentIEEE Transactions on Information Theory, 2011
- Network Coding for Distributed Storage SystemsIEEE Transactions on Information Theory, 2010
- Reducing repair traffic for erasure coding-based storage via interference alignment2009
- Combinatorial NullstellensatzCombinatorics, Probability and Computing, 1999
- Low-density MDS codes and factors of complete graphsIEEE Transactions on Information Theory, 1999
- X-code: MDS array codes with optimal encodingIEEE Transactions on Information Theory, 1999
- EVENODD: an efficient scheme for tolerating double disk failures in RAID architecturesIEEE Transactions on Computers, 1995