Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy

• DOI: 10.48550/arxiv.1806.00939
• Publication Date: 2018-01-01
• Authors: Qian Yu; Songze Li; Netanel Raviv; Seyed Mohammadrez...; Mahdi Soltanolkotabi; Salman Avestimehr
• Keywords: Speedup

We consider a scenario involving computations over massive dataset stored distributedly across multiple workers, which is at the core of distributed learning algorithms. propose Lagrange Coded Computing (LCC), new framework to simultaneously provide (1) resiliency against stragglers that may prolong computations; (2) security Byzantine (or malicious) workers deliberately modify computation for their benefit; and (3) (information-theoretic) privacy amidst possible collusion workers. LCC, leverages well-known polynomial create redundancy in novel coded form can be applied any function interest an arbitrary multivariate input dataset, hence covering many machine learning. LCC significantly generalizes prior works go beyond linear computations. It also enables secure private computing settings, improving communication efficiency state-of-the-art. Furthermore, we prove optimality by showing it achieves optimal tradeoff between resiliency, security, privacy, i.e., terms tolerating maximum number adversaries, providing data colluding Finally, show via experiments on Amazon EC2 speeds up conventional uncoded implementation least-squares regression $13.43\times$, $2.36\times$-$12.65\times$ speedup state-of-the-art straggler mitigation strategies.