Back to Search
Start Over
A New Design of Binary MDS Array Codes With Asymptotically Weak-Optimal Repair.
- Source :
- IEEE Transactions on Information Theory; Nov2019, Vol. 65 Issue 11, p7095-7113, 19p
- Publication Year :
- 2019
-
Abstract
- Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provides fault tolerance with minimum storage redundancy but also achieves 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, then our goal is to minimize the repair bandwidth by downloading the least amount of bits from $d$ healthy columns, where $k\leq d\leq k+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 the $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., $r\geq 3$) that achieve asymptotically weak-optimal repair, where $k+1\leq d\leq k+\lfloor (r-1)/2\rfloor $ , 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 anyone information failure, while codes in the second construction have even number of parity columns and asymptotically weak-optimal repair for any one column failure. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 65
- Issue :
- 11
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 139229539
- Full Text :
- https://doi.org/10.1109/TIT.2019.2923992