Repairing Reed-Solomon Codes
Authors:
- Venkatesan GuruswamiVGVenkatesan Guruswami
- Mary WoottersMWMary Wootters
Preprint
Abstract
A fundamental fact about polynomial interpolation is that $k$ evaluations of a degree-$(k-1)$ polynomial $f$ are sufficient to determine $f$. This is also necessary in a strong sense: given $k-1$ evaluations, we learn nothing about the value of $f$ on any $k$'th point. In this paper, we study a variant of the polynomial interpolation problem. Instead of querying entire evaluations of $f$, we may query "partial" evaluations; that is, we may ask for a few bits instead of an entire field element. We show that in this model, one can do significantly better than in the traditional setting, in terms of the amount of information required to determine the missing evaluation. More precisely, we show that only $O(k)$ bits are necessary to recover a missing evaluation. In contrast, the traditional method of looking at $k$ evaluations requires $\Omega(k\log(k))$ bits. We also show that our result is optimal for linear methods, even up to the leading constants. Our motivation comes from the use of Reed-Solomon (RS) codes for distributed storage systems, in particular for the exact repair problem. Codes which solve this problem well are known, but they are not RS codes, and RS codes are still often used in practice; it was a question of (Dimakis et al., 2011) how well RS codes could perform in this setting. Our results imply non-trivial exact repair schemes for RS codes. In some parameter regimes---those with small levels of sub-packetization---our scheme for RS codes outperforms all known regenerating codes. Even with a high degree of sub-packetization, our methods give non-trivial schemes, and we give an improved repair scheme for a specific (14,10)-RS code used in the Facebook Hadoop Analytics cluster.