Optimal Repair Schemes for Some Families of Full-Length Reed-Solomon Codes

Abstract

Reed-Solomon codes have found many applications in practical storage systems, but were until recently considered unsuitable for distributed storage applications due to the widely-held belief that they have poor repair bandwidth. The work of Guruswami and Wootters (STOC'16) has shown that one can actually perform bandwidth-efficient linear repair with Reed-Solomon codes: When the codes are over the field ${\mathbb{F}}_{q^t}$ and the number of parities $r\ge q^s$, where $(t-s)$ divides $t$, there exists a linear scheme that achieves a repair bandwidth of $(n-1)(t-s){\log }_{2}q$ bits. We extend this result by showing the existence of such a linear repair scheme for every $1\le s<t$. Moreover, our new schemes are optimal among all linear repair schemes for Reed-Solomon codes when $n=q^t$ and $r=q^s$. Additionally, we improve the lower bound on the repair bandwidth for Reed-Solomon codes, also established in the work of Guruswami and Wootters.

ISIT'17 (accepted), 5 pages

Cited by in corpus (1)

• Erasure Coding for Distributed Storage: An Overview