Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding

Abstract

We consider the problem of massive matrix multiplication, which underlies many data analytic applications, in a large-scale distributed system comprising a group of worker nodes. We target the stragglers' delay performance bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy, named \emph{entangled polynomial code}, for designing the intermediate computations at the worker nodes in order to minimize the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We demonstrate the optimality of entangled polynomial code in several cases, and show that it provides orderwise improvement over the conventional schemes for straggler mitigation. Furthermore, we characterize the optimal recovery threshold among all linear coding strategies within a factor of $2$ using \emph{bilinear complexity}, by developing an improved version of the entangled polynomial code. In particular, while evaluating bilinear complexity is a well-known challenging problem, we show that optimal recovery threshold for linear coding strategies can be approximated within a factor of $2$ of this fundamental quantity. On the other hand, the improved version of the entangled polynomial code enables further and orderwise reduction in the recovery threshold, compared to its basic version. Finally, we show that the techniques developed in this paper can also be extended to several other problems such as coded convolution and fault-tolerant computing, leading to tight characterizations.

References in corpus (2)

• A Unified Coded Deep Neural Network Training Strategy Based on Generalized PolyDot Codes for Matrix Multiplication
• On the Capacity of Secure Distributed Matrix Multiplication

Cited by in corpus (11)

• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• Private and Secure Distributed Matrix Multiplication Schemes for Replicated or MDS-Coded Servers
• Bivariate Polynomial Coding for Efficient Distributed Matrix Multiplication
• Bivariate Polynomial Codes for Secure Distributed Matrix Multiplication
• A Systematic Approach towards Efficient Private Matrix Multiplication
• Information-Theoretically Private Matrix Multiplication From MDS-Coded Storage
• Efficient Recovery of a Shared Secret via Cooperation: Applications to SDMM and PIR
• On the Generic Capacity of $K$-User Symmetric Linear Computation Broadcast
• Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation
• Blind Interference Alignment for MapReduce: Exploiting Side-information with Reconfigurable Antennas
• Folded Polynomial Codes for Coded Distributed $A{A}^{\top }$-Type Matrix Multiplication