Netanel Raviv – Access-optimal MSR codes with optimal sub-packetization over small fields


Event Details

  • Date:

This paper presents a new construction of access-optimal minimum storage regenerating codes which attain the sub-packetization bound. These distributed storage codes provide the minimum storage in a node, and in addition have the following two important properties: first, a helper node accesses the minimum number of its symbols for repair of a failed node; second, given storage \ell in each node, the entire stored data can be recovered from any 2\log
\ell (any 3\log\ell) for 2 parity nodes (for 3 parity nodes, respectively). The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. Our construction is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices which constitute a generator matrix of the constructed codes. The field size required for our construction is significantly smaller when compared to previously known codes. Using similar techniques, an additional construction of a larger code which attains the sub-packetization bound is given. Although it is not an access-optimal code, this additional code is comparable to known codes in terms of size, and can be defined over exponentially smaller fields.