New Constructions of MDS Codes with Asymptotically Optimal Repair
Ameera Chowdhury, Alexander Vardy · 2018
An (n,k, l) MDS code of length n, dimension k, and sub-packetization l over a finite field F is a set of n column vectors of length l over F with the property that any k vectors can recover the entire data of kl symbols. If one of the n nodes fails, we can recover it by downloading symbols from the surviving nodes, and the total number of symbols downloaded in the worst case is the repair bandwidth of the code. By the cut-set bound, the repair bandwidth of an (n,k, l) MDS code is at least (n-1)l/(n-k). There are several constructions of (n,k, l) MDS codes whose repair bandwidths meet or asymptotically meet the cut-set bound. For example, letting r=n-k denote the number of parities, Ye and Barg constructed (n,k,rn) Reed-Solomon codes that asymptotically meet the cut-set bound. Ye and Barg also constructed optimal bandwidth and optimal update (n, k, rn) MDS codes. Wang, Tamo, and Bruck constructed optimal bandwidth (n,k,rn/(r+1)) MDS codes, and these codes have the smallest known sub-packetization for optimal bandwidth MDS codes. A key idea in all these constructions is to expand integers in base r. When r is an integral power, we demonstrated in a previous paper how this technique can be refined to improve the sub-packetization of the two (n,k, l) MDS code constructions by Ye and Barg while achieving asymptotically optimal repair bandwidth. Herein, we present an extension of this idea that leads to a significant reduction in the sub-packetization of the Wang-Tamo-Bruck construction while achieving a repair-by-transfer scheme that has asymptotically optimal repair bandwidth. Specifically, when r=sm, we obtain an (n,k,sk/r+m-1) MDS code which has a repair-by-transfer scheme with asymptotically optimal repair bandwidth. If r=2m, for example, we achieve the sub-packetization of 2k/r+m-1, which improves upon the sub-packetization of 2mn/(r+1)in the Wang- Tamo-Bruck construction. Having demonstrated how to improve the sub-packetizations of three quite different (n,k, l) MDS code constructions, we believe that our approach will be generally useful in reducing the sub-packetizations of (n,k, l) MDS code constructions that utilize r-ary expansion.