Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding
share
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 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, using bilinear complexity, we characterize the optimal recovery threshold among all linear coding strategies within a factor of 2. 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. Finally, we show that the techniques developed in this paper can also be extended to several other problems such as coded convolution and fault tolerance computing, leading to tight characterizations.
READ FULL TEXT