Asymptotic Interference Alignment for Optimal Repair of MDS Codes in Distributed Storage
Viveck R. Cadambe, Syed A. Jafar, Hamed Maleki, Kannan Ramchandran, Changho Suh · IEEE Transactions on Information Theory · 2013
The high repair bandwidth cost of (n,k) maximum distance separable (MDS) erasure codes has motivated a new class of codes that can reduce repair bandwidth over that of conventional MDS codes. In this paper, we address (n,k,d) exact repair MDS codes, which allow for any single failed node to be repaired exactly with access to any arbitrary set ofdsurvivor nodes. We show the existence of exact repair MDS codes that achieve minimum repair bandwidth (matching the cut-set lower bound) for arbitrary admissible (n,k,d), i.e.,k≤d≤n-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set ofr≤n-kfailed nodes needs to repaired. Our approach is based on asymptotic interference alignment proposed by Cadambe and Jafar. As a byproduct, we also characterize the capacity of a class of multisource nonmulticast networks.