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. Parallel and Distributed Systems Group Technical Reports, etr144. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190220-123432908

[img] PDF - Submitted Version
See Usage Policy.

297kB

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

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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://paradise.caltech.edu/papers/etr144.pdfAuthorArticle
https://resolver.caltech.edu/CaltechAUTHORS:20191004-100332096Related ItemConference Paper
ORCID:
AuthorORCID
Raviv, Netanel0000-0002-1686-1994
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Series Name:Parallel and Distributed Systems Group Technical Reports
Issue or Number:etr144
Record Number:CaltechAUTHORS:20190220-123432908
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190220-123432908
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93009
Collection:CaltechPARADISE
Deposited By: Tony Diaz
Deposited On:20 Feb 2019 20:52
Last Modified:09 Apr 2020 18:06

Repository Staff Only: item control page