Fundamental Limits of Coded Linear Transform

Abstract

In large scale distributed linear transform problems, coded computation plays an important role to effectively deal with "stragglers" (distributed computations that may get delayed due to few slow or faulty processors). We propose a coded computation strategy, referred to as diagonal code, that achieves the optimum recovery threshold and the optimum computation load. This is the first code that simultaneously achieves two-fold optimality in coded distributed linear transforms. Furthermore, by leveraging the idea from random proposal graph theory, we design two random codes that can guarantee optimum recovery threshold with high probability but with much less computation load. These codes provide order-wise improvement over the state-of-the-art. Moreover, the experimental results show significant improvement compared to both uncoded and existing coding schemes.

References in corpus (3)

• Speeding Up Distributed Machine Learning Using Codes
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Coded Sparse Matrix Multiplication

Cited by in corpus (10)

• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• A Survey of Coded Distributed Computing
• A Game-theoretic Approach Towards Collaborative Coded Computation Offloading
• Coded Iterative Computing using Substitute Decoding
• A New Combinatorial Coded Design for Heterogeneous Distributed Computing
• CodeNet: Training Large Scale Neural Networks in Presence of Soft-Errors
• GCSA Codes with Noise Alignment for Secure Coded Multi-Party Batch Matrix Multiplication
• A Practical Algorithm Design and Evaluation for Heterogeneous Elastic Computing with Stragglers
• Price of Precision in Coded Distributed Matrix Multiplication: A Dimensional Analysis