Exact-repair MDS code construction using interference alignment

Abstract

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: (a) k/n <= 1/2 and d >= 2k -1(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.