A New Design of Binary MDS Array Codes With Asymptotically Weak-Optimal Repair

DOI10.1109/TIT.2019.2923992MaRDI QIDQ5211494zbMATH OpenWikidataFDO

Authors Hanxu Hou, Yunghsiang Sam Han, Patrick P. C. Lee, Yuchong Hu, Hui Li

Publication date 28 January 2020

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

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Abstract: Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provide fault tolerance with minimum storage redundancy but also achieve low computational complexity. They are constructed by encoding $k$ information columns into $r$ parity columns, in which each element in a column is a bit, such that any $k$ out of the $k+r$ columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance in practical applications. Specifically, if a single column fails, our goal is to minimize the repair bandwidth by downloading the least amount of bits from $d$ healthy columns, where $kleqdleqk+r-1$. If one column of an MDS code is failed, it is known that we need to download at least $1/(d-k+1)$ fraction of the data stored in each of $d$ healthy columns. If this lower bound is achieved for the repair of the failure column from accessing arbitrary $d$ healthy columns, we say that the MDS code has optimal repair. However, if such lower bound is only achieved by $d$ specific healthy columns, then we say the MDS code has weak-optimal repair. In this paper, we propose two explicit constructions of binary MDS array codes with more parity columns (i.e., $rgeq3$) that achieve asymptotically weak-optimal repair, where $k+1leqdleqk+lfloor(r-1)/2floor$, and "asymptotic" means that the repair bandwidth achieves the minimum value asymptotically in $d$. Codes in the first construction have odd number of parity columns and asymptotically weak-optimal repair for any one information failure, while codes in the second construction have even number of parity columns and asymptotically weak-optimal repair for any one column failure.

Cited in

(5)

• Asymptotic Interference Alignment for Optimal Repair of MDS Codes in Distributed Storage
• Zigzag Codes: MDS Array Codes With Optimal Rebuilding
• Modified Low-Density MDS Array Codes for Tolerating Double Disk Failures in Disk Arrays
• Binary MDS Array Codes With Optimal Repair
• MDS array codes with efficient repair and small sub-packetization level

This page was built for publication: A New Design of Binary MDS Array Codes With Asymptotically Weak-Optimal Repair

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