A Caltech Library Service

Erasure Correction of Scalar Codes in the Presence of Stragglers

Raviv, Netanel and Cassuto, Yuval and Cohen, Rami and Schwartz, Moshe (2018) Erasure Correction of Scalar Codes in the Presence of Stragglers. In: 2018 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 1983-1987. ISBN 978-1-5386-4780-6.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Raviv, Netanel0000-0002-1686-1994
Cassuto, Yuval0000-0001-6369-6699
Cohen, Rami0000-0002-9152-8446
Schwartz, Moshe0000-0002-1449-0026
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.
Funding AgencyGrant Number
Center for the Mathematics of Information, CaltechUNSPECIFIED
Lester-Deutsch postdoctoral fellowshipUNSPECIFIED
Israel Science Foundation130/14
Israel Science Foundation1676/14
Binational Science Foundation (USA-Israel)UNSPECIFIED
Record Number:CaltechAUTHORS:20181126-141418416
Persistent URL:
Official Citation:N. Raviv, Y. Cassuto, R. Cohen and M. Schwartz, "Erasure Correction of Scalar Codes in the Presence of Stragglers," 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, 2018, pp. 1983-1987. doi: 10.1109/ISIT.2018.8437322
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:91184
Deposited By: Tony Diaz
Deposited On:26 Nov 2018 22:39
Last Modified:04 Oct 2019 21:05

Repository Staff Only: item control page