Polynomial codes: an optimal design for high-dimensional coded matrix multiplication

TLDR

Large‑scale matrix multiplication is performed in a distributed system with a master node and workers that store parts of the input matrices. The authors propose a coding‑theory based strategy to design intermediate computations at workers to optimally handle stragglers. The strategy uses polynomial codes whose algebraic structure turns the reconstruction of the final output into an efficient polynomial interpolation problem. Polynomial codes achieve the optimal recovery threshold, outperforming prior schemes in recovery threshold, latency, and communication load, and extend to distributed convolution with order‑wise optimality.

Abstract

We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to optimally deal with straggling workers. The proposed strategy, named as polynomial codes, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. This is the first code that achieves the optimal utilization of redundancy for tolerating stragglers or failures in distributed matrix multiplication. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics including computation latency and communication load. Moreover, we extend this code to distributed convolution and show its order-wise optimality.