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 language | English (US) |
---|---|
Article number | 8340062 |
Pages (from-to) | 6567-6582 |
Number of pages | 16 |
Journal | IEEE Transactions on Information Theory |
Volume | 64 |
Issue number | 10 |
DOIs | |
State | Published - 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