Collaborative Decoding of Polynomial Codes for Distributed Computation
Adarsh M. Subramaniam, Anoosheh Heidarzadeh, Krishna R. Narayanan · 2019
We show that Polynomial codes (and some related codes) used for distributed matrix multiplication are interleaved Generalized Reed-Solomon codes and hence, can be collaboratively decoded. We consider a fault-tolerant setup where t out of N workers return erroneous values. For an additive random Gaussian error model, we show that for any t ≤ N - K - 1, where K is the effective dimension of the code, all errors can be corrected with probability 1 while the decoding complexity is O(( L/L+1)4(N - K)4+ LN) for any L ≥ N - K - 1.