Navigation

Optimal storage efficiency codes are called minimum-storage regenerating (MSR) and attain one of the two extremal points of the optimal Storage-Bandwidth Tradeoff curve [1] .

MSR codes require minimum storage space per node, i.e., have . Thus, these codes are Maximum-Distance-Separable (MDS). For this amount of storage, they then minimise the amount of repair-bandwidth as . (See here for the system model and notation.)

When a replacement node is constrained to store the same data as the corresponding failed node, the code is known as an exact-MSR code.

Results on MSR Codes (in chronological order in each subsection)

Exact-MSR codes:

1. Reducing repair traffic for erasure coding-based storage via interference alignment (Wu, Dimakis) presents codes that are optimal when [n = d+1, k = 2, d].
   
2. Searching for Minimum Storage Regenerating Codes (Cullina, Dimakis, Ho) presents explicit codes for [n=4, k=2, d=3] and [n=5, k=3, d=4].
   
3. Explicit Codes Minimizing Repair Bandwidth for Distributed Storage (Shah, Rashmi, Kumar, Ramchandran) present explicit codes that perform exact repair for systematic nodes optimally for all [n = d+1, k, d ≥ 2k-1].
   
4. Exact Regeneration Codes for Distributed Storage Repair Using Interference Alignment (Suh, Ramchandran) shows that the codes in the above paper can also perform exact repair of parity nodes optimally for all [n = d+1, k, d ≥ 2k-1], by providing explicit algorithms to perform the same. The paper also contains a code construction for [n=5, k=3, d=4].
   
5. Distributed Data Storage with Minimum Storage Regenerating Codes - Exact and Functional Repair are Asymptotically Equally Efficient (Cadambe, Jafar, Maleki) and On the Existence of Optimal Exact-Repair MDS Codes for Distributed Storage (Suh, Ramchandran) show that the minimum storage (MSR) extremum is achievable asymptotically (i.e., as the number of message symbols → ∞) for all [n, k, d].
   
6. Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction (Rashmi, Shah, Kumar) presents explicit codes for all [n, k, d ≥ 2k-2].

Converse results:

1. Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions (Shah, Rashmi, Kumar, Ramchandran) show the non-existence of linear, scalar (β=1) exact-MSR codes for d < 2k-3.

Other codes:

1. Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage (Rashmi, Shah, Kumar, Ramchandran) presents explicit codes for [n, k, d=k+1] that performs exact repair of half the data stored in a node and functional repair of the remaining half.
2. A Construction of Systematic MDS Codes with Minimum Repair Bandwidth (Wu) presents codes for [n ≥ 2k, k, d = k+1] that distributes the systematic symbols amongst 2k nodes and performs exact repair of this part.

Back to Definitions