CaltechAUTHORS
  A Caltech Library Service

Download and Access Trade-offs in Lagrange Coded Computing

Raviv, Netanel and Yu, Qian and Bruck, Jehoshua and Avestimehr, Salman (2019) Download and Access Trade-offs in Lagrange Coded Computing. In: 2019 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 1787-1791. ISBN 9781538692912. https://resolver.caltech.edu/CaltechAUTHORS:20191004-100332096

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

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191004-100332096

Abstract

Lagrange Coded Computing (LCC) is a recently proposed technique for resilient, secure, and private computation of arbitrary polynomials in distributed environments. By mapping such computations to composition of polynomials, LCC allows the master node to complete the computation by accessing a minimal number of workers and downloading all of their content, thus providing resiliency to the remaining stragglers. However, in the most common case in which the number of stragglers is less than in the worst case scenario, much of the computational power of the system remains unexploited. To amend this issue, in this paper we expand LCC by studying a fundamental trade-off between download and access, and present two contributions. In the first contribution, it is shown that without any modification to the encoding process, the master can decode the computations by accessing a larger number of nodes, however downloading less information from each node in comparison with LCC (i.e., trading access for download). This scheme relies on decoding a particular polynomial in the ideal that is generated by the polynomials of interest, a technique we call Ideal Decoding. This new scheme also improves LCC in the sense that for systems with adversaries, the overall downloaded bandwidth is smaller than in LCC. In the second contribution we study a real-time model of this trade-off, in which the data from the workers is downloaded sequentially. By clustering nodes of similar delays and encoding the function with Universally Decodable Matrices, the master can decode once sufficient data is downloaded from every cluster, regardless of the internal delays within that cluster. This allows the master to utilize the partial work that is done by stragglers, rather than to ignore it, a feature that most past works in coded computing are lacking.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/isit.2019.8849547DOIArticle
https://resolver.caltech.edu/CaltechAUTHORS:20190220-123432908Related ItemTechnical Report
ORCID:
AuthorORCID
Raviv, Netanel0000-0002-1686-1994
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2019 IEEE. This material is based upon work supported by Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0053, ARO award W911NF1810400, NSF grants CCF-1703575, ONR Award No. N00014-16-1-2189, and CCF-1763673. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.
Funders:
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)HR001117C0053
Army Research Office (ARO)W911NF1810400
NSFCCF-1703575
Office of Naval Research (ONR)N00014-16-1-2189
NSFCCF-1763673
DOI:10.1109/isit.2019.8849547
Record Number:CaltechAUTHORS:20191004-100332096
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191004-100332096
Official Citation:N. Raviv, Q. Yu, J. Bruck and S. Avestimehr, "Download and Access Trade-offs in Lagrange Coded Computing," 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France, 2019, pp. 1787-1791. doi: 10.1109/ISIT.2019.8849547
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99073
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:04 Oct 2019 18:03
Last Modified:16 Nov 2021 17:43

Repository Staff Only: item control page