A Locality-Based Lens for Coded Computation

Coded computation is an emerging paradigm of applying coding theory to large-scale distributed computing to provide resilience against slow or otherwise unavailable workers. We propose a new approach to view coded computation via the lens of the locality of codes. We do so by defining a new notion of locality, called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">computational locality</i>, using the locality properties of an appropriately defined code for the function being computed. This notion of locality incorporates the unique aspects of locality arising in the context of coded computation. Our first major contribution is to demonstrate how to design a coded computation scheme for a function using the local recovery scheme of an appropriately defined code. The so-obtained scheme rederives the best known coded computation scheme for multivariate polynomial functions via the viewpoint of the locality of the Reed-Muller code. Our second major contribution is to show that the proposed locality-based approach enables new tradeoffs (e.g., communication bandwidth vs number of workers) compared to existing coded computation schemes. Specifically for the case when there is known linear dependence among inputs—common in many real-world applications—the proposed approach significantly reduces resource overhead (i.e., number of workers) without incurring any tradeoffs.