Alladi Ramakrishnan Hall

Maximally Recoverable Codes with Locality

Venkat Guruswami

Carnegie Mellon Univ

MDS codes like Reed-Solomon codes enable erasure correction with optimal redundancy: with h redundant symbols they allow recovery of any subset of h erased positions. In matrix terms, they are defined by an h x n parity check matrix all of whose h x h submatrices are nonsingular. Such matrices, e.g. Vandermonde, exist over a field of size O(n).

The prevalent use of erasure coding in today's large distributed storage systems, where individual storage nodes often fail, brings to the fore a new requirement: the ability to quickly recover any single symbol of the codeword based on few other codeword symbols. Such locality can be built into the code via local parity checks --- for example, the n codeword symbols can be partitioned into n/r groups each with r symbols obeying a local parity check. Here r is the ``locality'' of the code. In matrix terms, we have an (n/r + h) x n matrix with the first n/r rows, each with r 1's, corresponding to the local parity checks, and the last h rows unrestricted. The local checks compromise the MDS property, but we would still like the code to correct all erasure patterns that can possibly be recovered given the specified topology of parity checks. This property is called Maximal Recoverability, and for the above topology amounts to the nonsingularity of every (n/r+h) x (n/r+h) submatrix that includes at least one column from each local group.

The known constructions (and even existence proofs) of such matrices require a very large field size of about n^h, and it has been an important question whether MR codes can exist over smaller, even O(n)-sized, fields. The talk will mention the prior construction with n^h field size, and then present a recent super-linear lower on the field size which relies on known vertex expansion properties of the hyperplane-point incidence graph in projective space. Time permitting, we will sketch a construction with near-linear field size for the special case of r=h=3, via a new approach based on elliptic curves and AP-free sets.

Based on joint work with Sivakanth Gopi and Sergey Yekhanin.