Consider the very simple (n=3,k=2) binary MDS code shown. This is a single parity (as used in RAID 5): one disk storing the parity of the others.

Clearly, this code has the property it can tolerate any single node failure. This means that even after one node fails, a data collector (shown as a laptop) can communicate the information from the remaining two nodes and reconstruct the file. This is shown here:

In the picture it is assumed that each block has size 1GB and the arrows show how much information is communicated. This is simply reconstruction of the whole data object. Clearly reconstruction costs 2GB of communication in this example.

We are now interested in repair which is slightly different. For repair, a new node is no longer interested in reconstructing all the data, but rather only a single block. This is shown here:

Two different notions of repair are shown. Exact repair corresponds to building exactly the lost block. Functional Repair corresponds to simply reconstructing a new block that combined with the existing ones still forms an (n,k) MDS code. In linear algebra terms this means that the new block is in general position (maximally linearly independent) with respect to the existing blocks. Exact repair is a special case of functional repair and is strictly harder.

While dealing with repair, apart from the paramters n and k, a third parameter is used to specify the number of nodes a replacement node connects to during the repair process. In the following examples, the parameter d is assumed to be n-1, i.e., the node replacing a failed node connects to all the remaining nodes for repair.

For the case of a single parity code, repairing also requires communication of 2GB– both blocks have to be recovered, to recover one.

Beyond the single parity case, codes can be constructed to tolerate any number of failures if enough redundancy is allowed. This an Evenodd code ((by Blaum and Bruck), a binary (4,2) MDS code that can tolerate two failures:

One observation is that each node is now storing two blocks. This sub-packetization is necessary to create binary codes with more than one parity. Assuming each block has size 1/2 GB so that each node is storing 1GB, reconstructing the whole file would, of course require 4 blocks of total size 2GB of communication.

However repairing a node failure can be done by communicating 1.5GB. See [9].

Interestingly Evenodd codes can be repaired by matching the cutset bound for the n=4,k=2 case. Another case of repairing another node failure is shown here:

Observe that in this case the two packets at the second node are XORed and c+d is communicated. This idea of making linear combinations locally at the nodes and then transmitting linear combinations allows the reduction in repair bandwidth.

The concept of Regenerating Codes was proposed in [1] where it is shown conceptually that an increase in the storage per node as compared to the MDS case can lower the amount of data downloaded for repair. Also in [1] , lower bounds on the repair communication are derived using cut-set arguments.

The case when the code is MDS is called the Minimum Storage Regenerating (MSR) case. [2] showed that for rate the cut-set bound can be matched when repairing the systematic parts of the code. Subsequently [3] developed a complete framework that guarantees exact regeneration of all nodes while achieving the cut-set bound for MSR codes. The results in [2] and [3] cover the case of .

The explicit codes presented in [5] cover the case of . These codes, constructed using a new Product-Matrix framework, is the first exact-MSR codes that do not have the constraint of requiring a replacement node to download data from all the remaining nodes during repair (i.e., allow ). This property is valuable in geographically distributed / peer-to-peer systems where connectivity may be low, and when the number of nodes in the system may vary with time and need not be restricted by the parameter .

The high rate case of and is covered in [6] , [7] and [8] when . Such codes are especially useful in co-located storage systems which typically have low redundancy levels and a fixed number of nodes. The special case of in the high rate regime was earlier covered in [4] , [3] and [5] . [11] and [12] show asymptotic existence of exact-MSR codes for all [n, k, d], while [2] shows the non-existence of scalar linear exact-MSR codes for the high rate case of d < 2k-3.

The case when the amount of download for repair is minimized (by allowing greater storage than MDS codes) is the Minimum Bandwidth Regenerating (MBR) case. Explicit codes for [n, k ,d=n-1] are constructed in [10] , and explict codes for all values of the parameters [n, k, d] are constructed in [5] . The latter code, constructed using the Product-Matrix framework, again works for the case when d < n-1.

[11] shows the impossibility of constructing exact-repair codes meeting the cut-set lower bound for essentially all cases between MSR and MBR.

Apart from the above, there are many other codes in the literature that address different aspects of the repair problem. A list of code constructions addressing the repair problem in distributed storage can be found here.

Alex: Why is the of [4] (Cullina et al.) not covered in the results of [3] ?
Dimitris: There actually is a section where the authors present a code in terms of the eigenvector-based interference alignment scheme. Check page 23 of [3] . I am not sure though if this could be extended to any code.