Explicit Maximally Recoverable Codes With Locality
Authors:
Top Cited Papers
- 30 June 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 60 (9) , 5245-5256
Abstract
Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, whereas 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, whereas 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 dependence 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 tradeoff between maximal recoverability and alphabet size.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- On the locality of codeword symbols in non-linear codesDiscrete Mathematics, 2014
- XORing elephantsProceedings of the VLDB Endowment, 2013
- Locally Decodable CodesFoundations and Trends® in Theoretical Computer Science, 2012
- Locally repairable codes2012
- Optimal linear codes with a local-error-correction property2012
- On sets of vectors of a finite vector space in which every subset of basis size is a basis IIDesigns, Codes and Cryptography, 2012
- On sets of vectors of a finite vector space in which every subset of basis size is a basisJournal of the European Mathematical Society, 2012
- Pyramid Codes: Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems2007
- Long Nonbinary Codes Exceeding the Gilbert–Varshamov Bound for any FixedDistanceIEEE Transactions on Information Theory, 2004
- Nonbinary double-error-correcting codes designed by means of algebraic varietiesIEEE Transactions on Information Theory, 1995