Polynomial Length MDS Codes With Optimal Repair in Distributed Storage

In this paper, we study maximum distance separable (MDS) codes for distributed storage with optimal repair properties. An (n; k) MDS code can be used to store data in n storage nodes, such that the system can tolerate the failure of any (n ? k) storage nodes because of the MDS property. Recently, MDS codes have been constructed which satisfy an additional optimal repair property as follows: the failure of a single storage node can be repaired by downloading a fraction of 1=(n?k) of the data stored in every surviving storage node. In previous constructions satisfying this optimal repair property, the size of the code is polynomial in k for the high-redundancy regime of k=n 1=2; but the codes have an exponential size (w.r.t. k) for the practically important low-redundancy regime of k=n > 1=2. In this paper, we construct polynomial size codes in this low redundancy regime. In particular, we construct MDS codes whose size is O(k2) with optimal repair bandwidth for the special case where k=n 2=3. Further, we show that for any fixed rate k=n; we can construct repair bandwidth optimal MDS codes whose size scales as a polynomial in k.