Asymptotic Interference Alignment for Exact Repair in Distributed Storage Systems

Abstract—In this paper, we consider a distributed storage system where a file of size M is stored in n distributed storage nodes using an (n, k) systematic maximum distance separable (MDS) code. The (n, k) MDS code can protect the storage system from data loss in in case of failure (erasure) of storage nodes, as long as the number of failures is smaller than or equal to (n − k), because of the MDS property of the code. The problem of interest of this paper is to repair failed nodes in the storage system, by replacing them by their replicas (exact repair), as efficiently as possible, i.e., by downloading the minimum possible amount of data from the surviving nodes. Recently, the problem, termed as the exact repair bandwidth problem, has been solved for the special case of r = 1 failure using the asymptotic interference alignment scheme developed by Cadambe and Jafar in the context of the wireless interference channel. In this paper, we extend this result to find the minimum repair bandwidth for the more general case of r> 1 failures, as long as the number of failures r is smaller than (n − k)- the maximum number of failures that can be tolerated by the system. I