Explicit Codes Minimizing Repair Bandwidth for Distributed Storage

Abstract—We consider the setting of data storage across n nodes in a distributed manner. A data collector (DC) should be able to reconstruct the entire data by connecting to any k out of the n nodes and downloading all the data stored in them. When a node fails, it has to be regenerated back using the existing nodes. An obvious means of accomplishing this is to use a Reed-Solomon type MDS code where each node stores a single finite field symbol and where one downloads the entire file for regeneration of a failed node. However, storing vectors in place of symbols makes it easy to extract partial information from a node, and helps in reducing the amount of download required for regeneration of a failed node, termed as repair bandwidth. Recently, there has been additional interest in storing data in systematic form as no post processing is required when the DC connects to the k systematic nodes. On failure of a systematic node, there is a need to regenerate it back quickly and exactly due to their preferred status. Replacement of a failed node by an exact replica is termed exact regeneration. In this paper, we consider the problem of minimizing the repair bandwidth for exact regeneration of the systematic nodes. The file to be stored is of size B and each node can store α = B/k units of data. A failed systematic node is regenerated by downloading β units of data each from d existing nodes. We give a lower bound for the repair bandwidth for exact regeneration of the systematic nodes which matches with the bound given by Wu et al. For d ≥ 2k − 1 we give an explicit code construction which achieves the lower bound on repair bandwidth when the existing k − 1 systematic nodes participate in the regeneration. We show the existence and construction of codes that achieve the bound for d ≥ 2k − 3. Here we also establish the necessity of interference alignment. We prove that the bound is not achievable for d ≤ 2k − 4 when β = 1, except for the case when α = 1 for which any [n, k] MDS code will trivially achieve the bound. We also give a coding scheme which can be used for any d and k, which is optimal for d ≥ 2k − 1