Repairing Reed-Solomon Codes With Multiple Erasures

Hoang Dau, Iwan M. Duursma, Han Mao Kiah, Olgica Milenkovic

Research output: Contribution to journalArticlepeer-review

Abstract

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.

Original languageEnglish (US)
Article number8340062
Pages (from-to)6567-6582
Number of pages16
JournalIEEE Transactions on Information Theory
Volume64
Issue number10
DOIs
StatePublished - Oct 2018

Keywords

  • Reed-Solomon codes
  • distributed storage systems
  • erasure
  • repair bandwidth
  • trace

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint

Dive into the research topics of 'Repairing Reed-Solomon Codes With Multiple Erasures'. Together they form a unique fingerprint.

Cite this