Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
复制标题
DOI：
--
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Qian Yu;Netanel Raviv;Jinhyun So;A. Avestimehr
中科院分区：
文献类型：
--
作者：
Qian Yu;Netanel Raviv;Jinhyun So;A. Avestimehr
我们考虑了一个场景，涉及对分布在多个工作人员上的大量数据集的计算，这是分布式学习算法的核心。我们提出了拉格朗日编码计算（LCC），这是一种新的框架，可以同时提供(1)对可能延长计算时间的掉队者的弹性；(2)针对拜占庭（或恶意）工作人员故意修改计算以获取利益的安全性；(3)（信息论的）数据集在可能的工人串通中的隐私性。LCC利用著名的拉格朗日多项式以一种新颖的编码形式在工作人员之间创建计算冗余，可以应用于任何计算场景，其中感兴趣的函数是输入数据集的任意多元多项式，因此涵盖了机器学习中感兴趣的许多计算。LCC极大地推广了以前的工作，超越了线性计算。它还可以在分布式环境中实现安全和私有计算，提高最先进的计算和通信效率。此外，我们通过显示它实现了弹性，安全性和隐私之间的最佳权衡来证明LCC的最优性，即在容忍最大数量的掉队者和对手方面，并针对最大数量的串通工作人员提供数据隐私。最后，我们通过在Amazon EC2上的实验表明，LCC将分布式最小二乘线性回归的传统非编码实现速度提高了13.43倍，并且与最先进的离散子缓解策略相比，还实现了2.36倍至12.65倍的加速。
We consider a scenario involving computations over a massive dataset stored distributedly across multiple workers, which is at the core of distributed learning algorithms. We propose Lagrange Coded Computing (LCC), a new framework to simultaneously provide (1) resiliency against stragglers that may prolong computations; (2) security against Byzantine (or malicious) workers that deliberately modify the computation for their benefit; and (3) (information-theoretic) privacy of the dataset amidst possible collusion of workers. LCC, which leverages the well-known Lagrange polynomial to create computation redundancy in a novel coded form across workers, can be applied to any computation scenario in which the function of interest is an arbitrary multivariate polynomial of the input dataset, hence covering many computations of interest in machine learning. LCC significantly generalizes prior works to go beyond linear computations. It also enables secure and private computing in distributed settings, improving the computation and communication efficiency of the state-of-the-art. Furthermore, we prove the optimality of LCC by showing that it achieves the optimal tradeoff between resiliency, security, and privacy, i.e., in terms of tolerating the maximum number of stragglers and adversaries, and providing data privacy against the maximum number of colluding workers. Finally, we show via experiments on Amazon EC2 that LCC speeds up the conventional uncoded implementation of distributed least-squares linear regression by up to $13.43\times$, and also achieves a $2.36\times$-$12.65\times$ speedup over the state-of-the-art straggler mitigation strategies.