Asymptotic Interference Alignment for Optimal Repair of MDS Codes in Distributed Storage
The high repair bandwidth cost of (<i>n</i>,<i>k</i>) 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 (<i>n</i>,<i>k</i>,<i>d</i>) exact repair MDS codes, which allow for any single failed node to be repaired exactly with access to any arbitrary set of <i>d</i> survivor nodes. We show the existence of exact repair MDS codes that achieve minimum repair bandwidth (matching the cut-set lower bound) for arbitrary admissible (<i>n</i>,<i>k</i>,<i>d</i>), i.e., <i>k</i> ≤ <i>d</i> ≤ <i>n</i>-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set of <i>r</i> ≤ <i>n</i>-<i>k</i> failed 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.