On the optimal recovery threshold of coded matrix multiplication

Abstract

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 m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> 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.