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: |
| ||||||||||||
ORCID: |
| ||||||||||||
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: |
| ||||||||||||
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