Asymptotic Interference Alignment for Optimal Repair of MDS Codes in Distributed Storage

摘要

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 of $d$ 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 $(n,k,d)$, i.e., $k leq d leq n-1$. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set of $r leq n-k$ 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.