A Computation vs Communication Tradeoff in Distributed Matrix Multiplication Over Finite Fields
Tushara Swapna Malladi, Balaji Sundar Rajan · 2019
One of the key problems affecting the performance of algorithms running on a distributed storage system is straggler nodes. There have been works on reducing the recovery threshold (i.e., the minimum number of workers the master needs to wait for, in order to compute the final output) in the case of massive matrix multiplication problems. These works generally consider matrices over arbitrary field i.e., matrices over fields of characteristic both zero and prime. In this paper, we focus on multiplication of matrices over finite fields in a distributed storage system and exploit some properties of finite fields to achieve a fractional improvement in the recovery threshold, with a tradeoff in computational complexity. The proposed coding idea is applicable without restriction on the number of workers and the field size.