Minimum Storage Regenerating Codes For All Parameters

Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an [n, k, d]-(alpha) MSR code C over F-q is defined as follows. Using such a code C, a file F consisting of a k symbols over F-q can be distributed among n nodes, each storing alpha symbols, in such a way that: the file F can be recovered by downloading the content of any k of the n nodes; and the content of any failed node can be reconstructed by accessing any d of the remaining n - 1 nodes and downloading alpha / (d-k+1) symbols from each of these nodes. A common practical requirement for regenerating codes is to have the original file F available in uncoded form on some k of the n nodes, known as systematic nodes. In this case, several authors relax the defining node-repair condition above, requiring the optimal repair bandwidth of d alpha / (d-k+1) symbols for systematic nodes only. We shall call such codes systematic-repair MSR codes. Unfortunately, explicit constructions of [n, k, d] MSR codes are known only for certain special cases: either low rate, namely k / n <= 0.5, or high repair connectivity, namely d = n - 1. Although setting d = n - 1 minimizes the repair bandwidth, it may be impractical to connect to all the remaining nodes in order to repair a single failed node. Our main result in this paper is an explicit construction of systematic-repair [n, k, d] MSR codes for all possible values of parameters n, k, d. In particular, we construct systematic-repair MSR codes of high rate k / n > 0.5 and low repair connectivity k <= d <= n - 1. Such codes were not previously known to exist. In order to construct these codes, we solve simultaneously several repair scenarios, each of which is expressible as an interference alignment problem. Extension of our results beyond systematic repair remains an open problem.