Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2018 | public
Book Section - Chapter

Erasure Correction of Scalar Codes in the Presence of Stragglers

Abstract

Recent advances in coding for distributed storage systems have reignited the interest in scalar codes over extension fields. In parallel, the rise of large-scale distributed systems has motivated the study of computing in the presence of stragglers, i.e., servers that are slow to respond or unavailable. This paper addresses storage systems that employ linear codes over extension fields. A common task in such systems is the reconstruction of the entire dataset using sequential symbol transmissions from multiple servers, which are received concurrently at a central data collector. However, a key bottleneck in the reconstruction process is the possible presence of stragglers, which may result in excessive latency. To mitigate the straggler effect, the reconstruction should be possible given any sufficiently large set of sequentially received symbols, regardless of their source. In what follows, an algebraic framework for this scenario is given, and a number of explicit constructions are provided. Our main result is a construction that uses a recursive composition of generalized Reed-Solomon codes over smaller fields. In addition, we show links of this problem to Gabidulin codes and to universally decodable matrices.

Additional Information

© 2018 IEEE. The work of Netanel Raviv was supported in part by the postdoctoral fellowship of the Center for the Mathematics of Information (CMI), Caltech, and in part by the Lester-Deutsch postdoctoral fellowship. This research was supported in part by the Israel Science Foundation under grant no. 130/14, 1676/14 and the US-Israel Binational Science Foundation.

Additional details

Created:
August 19, 2023
Modified:
October 19, 2023