Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-104 | 20th July 2013 02:24

Explicit Maximally Recoverable Codes with Locality

RSS-Feed




TR13-104
Authors: Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin
Publication: 26th July 2013 15:17
Downloads: 4270
Keywords: 


Abstract:

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. Local parities allow to quickly recover any single symbol when it is erased, while 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 recoverable given the code topology. In this paper we present explicit families of maximally-recoverable codes with locality. We also initiate the study of the trade-off between maximal recoverability and alphabet size.



ISSN 1433-8092 | Imprint