Repairing reed-solomon codes with multiple erasures

• المؤلفون الرئيسيون: Dau, Hoang, Duursma, Iwan M., Kiah, Han Mao, Milenkovic, Olgica
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2020
• الموضوعات: Engineering::Computer science and engineering; Maintenance Engineering; Encoding
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/145450
• المؤسسة: 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.