Polynomial Length MDS Codes With Optimal Repair in Distributed Storage

Viveck R. Cadambe, Cheng Huang, Jin Li, and Sanjeev Mehrotra


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.


Publication typeProceedings
Published inAsilomar Conference on Signals, Systems, and Computers
> Publications > Polynomial Length MDS Codes With Optimal Repair in Distributed Storage