Explicit Maximally Recoverable Codes with Locality

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Such codes have been studied recently in the context of erasure coding for data storage, where the local parities facilitate fast recovery of any single symbol when it is erased, while the heavy parities provide tolerance to a large number of simultaneous erasures.

A code as above is maximally recoverable, if it corrects all erasure patterns which are information theoretically correctable given the prescribed dependency relations between data symbols and parity symbols. In this paper we present explicit families of maximally recoverable codes with locality. We also initiate the general study of the trade-off between maximal recoverability and alphabet size.