Minimum Cost Encoding for Coded Distributed Computing Systems

In large-scale distributed matrix-vector multiplications, e.g., for generative AI, straggling nodes can slow down or even jeopardize the whole operation. Coded distributed computing (CDC) uses erasure codes to create redundant computations and combat stragglers. This requires encoding very large matrices. Moreover, encoding must be repeated whenever system parameters (e.g., weight matrices in AI models) evolve. This paper introduces a general framework for reducing encoding complexity in CDC. We