Repairing reed-solomon codes with multiple erasures

• Main Authors: Dau, Hoang, Duursma, Iwan M., Kiah, Han Mao, Milenkovic, Olgica
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2020
• Subjects: Engineering::Computer science and engineering; Maintenance Engineering; Encoding
• Online Access: https://hdl.handle.net/10356/145450
• Institution: Nanyang Technological University

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.