Bivariate Hermitian Polynomial Coding for Efficient Distributed Matrix Multiplication

Coded distributed computing is an effective framework to improve the speed of distributed computing systems by mitigating stragglers (temporarily slow workers). In essence, coded computing allows replacing the computation assigned to a straggling worker by that at a faster worker by assigning redundant computations. Coded computing techniques proposed so far are mostly based on univariate polynomial coding. These codes are not very effective if storage and computation capacity across workers are heterogeneous and lose completely the work done by the straggling workers. For the particular problem of distributed matrix-matrix multiplication, we show how bivariate polynomial coding addresses these two issues.Grant numbers : SGR-RC - Suport als Grups de Recerca, "Grup de Tecnologies de les Comunicacions Ràdio" ( Project code: 2009SGR1046)(03 August 2009 - 31 December 2013) and ARISTIDES - Aprendizaje Estadístico e Inferencia para Sistemas de Comunicación de Alta Dimensionalidad (RTI2018-099722-B-I00) projects.© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works