Optimal systematic distributed storage codes with fast encoding
Preetum Nakkiran, K. V. Rashmi, Kannan Ramchandran · 2016
We consider the problem of constructing explicit erasure codes for distributed storage with the following desirable properties motivated by system constraints: (i) Maximum-Distance-Separable (MDS), (ii)Optimal repair-bandwidth, (iii)Flexibility in repair (as will be described), (iv) Systematic Form, and (v) Fast encoding (enabled by a sparse generator matrix). Existing constructions in the literature satisfy only strict subsets of these desired properties. This paper presents the first explicit code construction which theoretically guarantees all the five desired properties simultaneously. We first present a construction that builds on Product-Matrix (PM) codes by enabling sparsity in its generator matrix. We then present a transformation for general classes of storage and repair optimal codes to enable fast encoding through sparsity. In practice, such sparse codes are roughly 7 times sparser than their standard counterparts, and result in encoding speedup by a factor of about 4 for typical parameters.