Repairing Reed-solomon codes
Authors:
Open Access
- 19 June 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 216-226
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 (which are elements of a large field F), we are allowed to query partial evaluations; that is, each evaluation delivers a few elements from a small subfield of F, rather than a single element from F. 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. The traditional use of RS codes in this setting is analogous to the traditional interpolation problem. Each node in a system stores an evaluation of f, and if one node fails we can recover it by reading k other nodes. However, each node is free to send less information, leading to the modified problem above. The quickly-developing field of regenerating codes has yielded several codes which take advantage of this freedom. However, these codes are not RS codes, and RS codes are still often used in practice; in 2011, Dimakis et al. asked how well RS codes could perform in this setting. Our results imply that RS codes can also take advantage of this freedom to download partial symbols. 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.Keywords
All Related Versions
Funding Information
- National Science Foundation (DMS- 1400558,CCF-1422045)
This publication has 19 references indexed in Scilit:
- Repairing Reed-solomon codes2016
- Bounds on locally recoverable codes with multiple recovering sets2014
- A Family of Optimal Locally Recoverable CodesIEEE Transactions on Information Theory, 2014
- A Repair Framework for Scalar MDS CodesIEEE Journal on Selected Areas in Communications, 2014
- An Improved Sub-Packetization Bound for Minimum Storage Regenerating CodesIEEE Transactions on Information Theory, 2014
- Optimal locally repairable codes and connections to matroid theory2013
- XORing elephantsProceedings of the VLDB Endowment, 2013
- Exact regenerating codes for Byzantine fault tolerance in distributed storage2012
- A Survey on Network Codes for Distributed StorageProceedings of the IEEE, 2011
- Network Coding for Distributed Storage SystemsIEEE Transactions on Information Theory, 2010