Feeds: iCal | RSS | JSON (as of )
Login | Need an account?

Regenerating codes for distributed storage

Setup Time:
15 minutes
Wednesday, May 24, 2017 at 6:00pm
Wednesday, May 24, 2017 at 9:00pm
Teardown Time:
15 minutes
Estimated size:
Large Event Room

Mary Wooters, professor at Stanford, will speak on the following abstract:

We study the performance of Reed-Solomon (RS) codes for the \em exact repair problem \em in distributed storage. Our main result is that, in some parameter regimes, Reed-Solomon codes are optimal regenerating codes, among MDS codes with linear repair schemes. Moreover, we give a characterization of MDS codes with linear repair schemes which holds in any parameter regime, and which can be used to give non-trivial repair schemes for RS codes in other settings.
More precisely, we show that for k-dimensional RS codes whose evaluation points are a finite field of size n, there are exact repair schemes with bandwidth (n−1)log((n−1)/(n−k)) bits, and that this is optimal for any MDS code with a linear repair scheme. In contrast, the naive (commonly implemented) repair algorithm for this RS code has bandwidth klog(n) bits. When the entire field is used as evaluation points, the number of nodes n is much larger than the number of bits per node (which is O(log(n))), and so this result holds only when the degree of sub-packetization is small. However, our method applies in any parameter regime, and to illustrate this for high levels of sub-packetization we give an improved repair scheme for a specific (14,10)-RS code used in the Facebook Hadoop Analytics cluster.


Member RSVP

Hacker Dojo members may login to reserve space in the event room up to 48 hours before the event.

Member RSVP does not imply event registration if applicable.