Chebyshev Polynomial Codes: Task Entanglement-based Coding for Distributed Matrix Multiplication

a given task much slower than other workers, deteriorate Distributed computing has been a prominent solu tion to efficiently process massive datasets in par allel. However, the existence of stragglers is one of the major concerns that slows down the overall speed of distributed computing. To deal with this problem, we consider a distributed matrix multi plication scenario where a master assigns multiple tasks to each worker to exploit stragglers' comput ing ability (which is typically wasted in conven tional distributed computing). We propose Cheby shev polynomial codes, which can achieve orderwise improvement in encoding complexity at the master and communication load in distributed ma trix multiplication using task entanglement. The key idea of task entanglement is to reduce the number of encoded matrices for multiple tasks assigned to each worker by intertwining encoded matrices. We experimentally demonstrate that, in cloud environments, Chebyshev polynomial codes can provide significant reduction in overall processing time in distributed computing for ma trix multiplication, which is a key computational component in modern deep learning.