Nonlinear Repair of Reed-Solomon Codes

DOI10.1109/TIT.2022.3167615MaRDI QIDQ5096980zbMATH OpenOpenAlexFDO

Authors Roni Con, Itzhak Tamo

Publication date 19 August 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.01652

zbMATH Keywords

nonlinear repair schemeReed Solomon (RS) codesrepair of linear codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Abstract: The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised in [GW17] on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Lastly, we show that the cut-set bound for RS codes is not tight over prime fields by proving a tighter bound, using additive combinatorics ideas.

Recommendations

• Repairing Reed-Solomon Codes
• Repairing Reed-solomon codes
• Repairing Reed-Solomon Codes With Multiple Erasures
• Repairing Reed-Solomon Codes via Subspace Polynomials
• Enabling Optimal Access and Error Correction for the Repair of Reed–Solomon Codes
• Reed-solomon codes for correcting phased error bursts
• Decoding of Reed Solomon codes beyond the error-correction bound
• Constructions and Properties of Linear Locally Repairable Codes
• scientific article; zbMATH DE number 3225714
• Non-Binary Error Correction Codes*

Cited in

(8)

• Repairing Reed-Solomon Codes
• Repairing Reed-Solomon Codes via Subspace Polynomials
• Repairing Reed-solomon codes
• Constructing leakage-resilient Shamir's secret sharing: over composite order fields
• Towards breaking the half-barrier of local leakage-resilient Shamir's secret sharing
• Physical-bit leakage resilience of linear code-based secret sharing
• Distributed repairing multiple erasures in Reed-Solomon codes
• Leakage-resilience of Shamir's secret sharing: identifying secure evaluation places

This page was built for publication: Nonlinear Repair of Reed-Solomon Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096980)