Repairing Reed-Solomon Codes With Multiple Erasures

Abstract

Despite their exceptional error-correcting properties, Reed-Solomon 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 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 Reed-Solomon 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.

15 pages

References in corpus (1)

• Repairing Reed-Solomon codes: Universally achieving the cut-set bound for any number of erasures

Cited by in corpus (17)

• Repairing Reed-Solomon codes: Universally achieving the cut-set bound for any number of erasures
• Optimal repairing schemes for Reed-Solomon codes with alphabet sizes linear in lengths under the rack-aware model
• Multilinear Algebra for Minimum Storage Regenerating Codes
• Enabling optimal access and error correction for the repair of Reed-Solomon codes
• The repair problem for Reed-Solomon codes: Optimal repair of single and multiple erasures, asymptotically optimal node size
• Constructing $(h,d)$ cooperative MSR codes with sub-packetization $(d-k+h)(d-k+1{)}^{\lceil n/2\rceil }$
• On the I/O Costs of Some Repair Schemes for Full-Length Reed-Solomon Codes
• Centralized Multi-Node Repair Regenerating Codes
• On the Sub-Packetization Size and the Repair Bandwidth of Reed-Solomon Codes
• Bandwidth Cost of Code Conversions in Distributed Storage: Fundamental Limits and Optimal Constructions
• Repairing Generalized Reed-Muller Codes
• Storage Codes with Flexible Number of Nodes
• Repairing Reed-Solomon Codes via Subspace Polynomials
• New constructions of cooperative MSR codes: Reducing node size to $\exp (O(n))$
• Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization
• Erasures repair for decreasing monomial-Cartesian and augmented Reed-Muller codes of high rate
• Convertible Codes: Efficient Conversion of Coded Data in Distributed Storage