Robust Repair of Reed-Solomon Codes
For coding theorists, this work provides theoretical bounds and practical schemes for robust repair of Reed-Solomon codes, though the results are incremental and specific to the Guruswami-Wootters trace repair framework.
This paper studies robust repair of Reed-Solomon codes under low communication bandwidth, focusing on correcting erroneous responses from helper nodes. It derives upper bounds on code dimension for error correction and proposes two efficient repair schemes, with the first achieving BCH-bound error correction and the second tolerating more errors at higher computational cost.
We study the problem of robust repair of a single erasure in Reed--Solomon codes under low communication bandwidth. Focusing on the Guruswami--Wootters trace repair framework, we investigate whether a failed node can be correctly repaired in the presence of erroneous responses from helper nodes. Equivalently, we view the collection of downloaded traces as a code, which we call the repair-trace code. By characterizing the zero coefficients of the associated polynomial in terms of cyclotomic cosets, we derive upper bounds on the dimension $k$ that allow correction of a given number of erroneous traces $e$, as well as lower bounds on the minimum distance as a function of $k$. For the case $q=2$, we exploit explicit formulas for cyclotomic coset representatives to obtain the exact optimal dimension bound for single-error correction. We also propose two efficient robust repair schemes. Our first scheme achieves the error-correction capability guaranteed by the BCH bound. To approach a stronger bound based on character sums, we develop a second scheme that tolerates more errors at the cost of an additional factor $n$ in computational complexity.