Abstract

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.

‚Äč