Exact-Repair MDS Code Construction Using Interference Alignment

The high repair cost of (n, k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of MDS codes, called Repair MDS codes, that can significantly reduce repair bandwidth over conventional MDS codes. In this paper, we describe (n, k, d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to d survivor nodes, where k ≤ d ≤ n-1. We construct Exact-Repair MDS codes that are optimal in repair bandwidth for the cases of: (α) k/n ≤ 1/2 and d ≥ 2k - 1¹; (b) k ≤ 3. Our codes are deterministic and require a finite-field size of at most 2(n - k). Our constructive codes are based on interference alignment techniques.