Maximally recoverable codes: The bounded case

Venkata Gandikota, Elena Grigorescu, Clayton Thomas, Minshen Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Modern distributed storage systems employ Maximally Recoverable codes that aim to balance failure recovery capabilities with encoding/decoding efficiency tradeoffs. Recent works of Gopalan et al [SODA 2017] and Kane et al [FOCS 2017] show that the alphabet size of grid-like topologies of practical interest must be large, a feature that hampers decoding efficiency. To bypass such shortcomings, in this work we initiate the study of a weaker version of recoverability, where instead of being able to correct all correctable erasure patterns (as is the case for maximal recoverability), we only require to correct all erasure patterns of bounded size. The study of this notion reduces to a variant of a combinatorial problem studied in the literature, which is interesting in its own right. We study the alphabet size of codes withstanding all erasure patterns of small (constant) size. We believe the questions we propose are relevant to both real storage systems and combinatorial analysis, and merit further study.

Original languageEnglish (US)
Title of host publication55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1115-1122
Number of pages8
ISBN (Electronic)9781538632666
DOIs
StatePublished - Jan 17 2018
Externally publishedYes
Event55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 - Monticello, United States
Duration: Oct 3 2017Oct 6 2017

Publication series

Name55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Volume2018-January

Conference

Conference55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
CountryUnited States
CityMonticello
Period10/3/1710/6/17

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Signal Processing
  • Energy Engineering and Power Technology
  • Control and Optimization

Fingerprint Dive into the research topics of 'Maximally recoverable codes: The bounded case'. Together they form a unique fingerprint.

Cite this