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

By Qian Yu, Mohammad Ali Maddah-Ali, Amir Salman Avestimehr. 2018

314 citations recorded by the source corpus.

Consider massive matrix multiplication, a problem that underlies many data analytic applications, in a large-scale distributed system comprising a group of workers. 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 entangled polynomial code, designing intermediate computations at the workers 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 prove the optimality of entangled polynomial code in several cases, and show that it provides order-wise 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 bilinear complexity, by developing an improved version of the entangled polynomial code.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, background): “For instance, entangled polynomial codes [1] and PolyDot codes [2] have been proposed for the stragglers problem, within the context of distributed matrix multiplication.”
On the Capacity of Secure Distributed Matrix Multiplication (2018, methodology): “This methodology is similar to the one proposed in [9], [10] for distributed matrix multiplication problem.”
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy (2018, methodology): “This is the key building block for various algorithms, such as fast distributed matrix multiplication [30].”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, neutral): “[31] allows encoding of x as well.”
Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation (2018, methodology): “Similar schemes have been applied to the context of non-uniform computation delays at the servers [9].”
A Unified Coded Deep Neural Network Training Strategy based on Generalized PolyDot codes (2018, background): “Our proposed Generalized PolyDot achieves the same erasure recovery threshold (and hence error tolerance) for matrix-vector products as that obtained in a concurrent work on entangledpolynomial codes [10], proposed for matrix-matrix products.”
GASP Codes for Secure Distributed Matrix Multiplication (2018, background): “This follows the general mantra of evaluation codes and, in particular, polynomial codes as originally introduced in [8] and [9].”
Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes (2018, methodology): “In particular, [17], [18], [31]–[36] studied the problem of distributively multiplying two private matrices and [37]–[39] studied the problem of running private distributed machine learning algorithm in the presence of stragglers.”
Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding (2018, methodology): “The above described PCR scheme is motivated by techniques used in a coded computing scheme in [22], which is designed to mitigate stragglers in distributed computation of an element-wise vector product.”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, methodology): “An extension of this scheme, termed Generalized PolyDot (GPD) codes improves on the recovery threshold of PolyDot codes [21], which is independently obtained by the construction in [22].”
Communication-Computation Efficient Gradient Coding (2018, methodology): “introduced optimal coding schemes to compute high-dimensional matrix multiplication [16], [18] and Fourier Transform [17], and Yang et al.”
Cross-Iteration Coded Computing (2018, methodology): “The coded computing technique derived in this paper originates from “MatDot codes” [37], [38], which are storageoptimal codes for matrix multiplication, whose optimality was shown recently in [39].”