Download and Access Trade-offs in Lagrange Coded Computing
Download and Access Trade-offs in Lagrange Coded Computing
复制标题
DOI：
10.1109/isit.2019.8849547
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Netanel Raviv;Qian Yu;Jehoshua Bruck;A. Avestimehr
中科院分区：
文献类型：
--
作者：
Netanel Raviv;Qian Yu;Jehoshua Bruck;A. Avestimehr
拉格朗日编码计算（LCC）是最近提出的一种用于分布式环境中任意多项式的弹性、安全和私有计算的技术。通过将这些计算映射到多项式的合成，LCC允许主节点通过访问最小数量的工作者并下载其所有内容来完成计算，从而为剩余的落伍者提供弹性。然而，在最常见的情况下，其中掉队者的数量小于在最坏的情况下，系统的大部分计算能力仍然未被利用。为了修正这个问题，在本文中，我们扩大LCC通过研究下载和访问之间的基本权衡，并提出两个贡献。在第一个贡献中，示出了在不对编码过程进行任何修改的情况下，主节点可以通过访问更大数量的节点来解码计算，然而与LCC相比，从每个节点下载更少的信息（即，交易访问下载）。该方案依赖于解码由感兴趣的多项式生成的理想中的特定多项式，我们称之为理想解码的技术。这种新方案还改进了LCC，因为对于具有对手的系统，总体下载带宽小于LCC。在第二个贡献中，我们研究了这种权衡的实时模型，其中工人的数据被顺序下载。通过聚类具有相似延迟的节点并使用通用可解码矩阵对函数进行编码，一旦从每个集群下载了足够的数据，主机就可以解码，而不管该集群内的内部延迟如何。这允许大师利用掉队者完成的部分工作，而不是忽略它，这是编码计算中大多数过去的工作所缺乏的功能。
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.