On the optimal recovery threshold of coded matrix multiplication

By Mohammad Fahim, Haewon Jeong, Farzin Haddadpour, Sanghamitra Dutta, Viveck R. Cadambe, Pulkit Grover. 2017

318 citations recorded by the source corpus.

We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent “Polynomial code” constructions in recovery threshold, i.e., the required number of successful workers. When m-th fraction of each matrix can be stored in each worker node, polynomial codes require m2 successful workers, while our novel MatDot codes only require 2m − 1 successful workers, albeit at a higher communication cost from each worker to the fusion node. Further, we propose “PolyDot” coding that interpolates between Polynomial codes and MatDot codes. Finally, we demonstrate an application of PolyDot codes to multiplying multiple (> 2) matrices.

Subfields: 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 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, background): “There has been significant recent work [9]–[11] in speeding up computation and reducing communication overhead using codes when it comes to distributed matrix multiplication in information theory community.”
Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding (2018, methodology): “We note that recently, another computation design named PolyDot was also proposed for this problem, achieving a recovery threshold of m(2)(2p − 1) for m = n [13], [14].”
Coded Federated Computing in Wireless Networks with Straggling Devices and Imperfect CSI (2019, unknown): “Under the assumption that communication is ideal, recent work has demonstrated the role of coding of the input data in mitigating the impact of stragglers [6], [7], as well as of coding of the output data in reducing the communication load for Map-Shufﬂe-Reduce systems [3].”
A Unified Coded Deep Neural Network Training Strategy based on Generalized PolyDot codes (2018, methodology): “In [8], we first demonstrated that the recovery threshold of Polynomial codes [9] can be reduced further using a novel code construction called MatDot.”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, methodology): “In [12] so called MatDot codes are introduced, resulting in a lower recovery threshold at the expense of a larger communication load.”
Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication (2018, background): “A natural generalization of matrix-vector multiplication is matrix-matrix multiplication, considered in [16, 61, 63].”
A Full Dive Into Realizing the Edge-Enabled Metaverse: Visions, Enabling Technologies, and Challenges (2022, background): “In response, various types of coding schemes, such as MatDot codes and PolyDot codes, are proposed in [198], which can be”