Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors
This work addresses performance bottlenecks in distributed computing for machine learning by providing a more practical coding approach, though it is incremental as it builds on existing coded computing strategies.
The paper tackles the problem of stragglers in distributed tensor computations by shifting from a combinatorial recovery threshold to a probabilistic decoding probability measure, leading to the construction of locally random alloy codes for matrix multiplication that are optimal under this measure and revealing an impossibility theorem for coded distributed tensors.
Tensors are a fundamental operation in distributed computing, \emph{e.g.,} machine learning, that are commonly distributed into multiple parallel tasks for large datasets. Stragglers and other failures can severely impact the overall completion time. Recent works in coded computing provide a novel strategy to mitigate stragglers with coded tasks, with an objective of minimizing the number of tasks needed to recover the overall result, known as the recovery threshold. However, we demonstrate that this strict combinatorial definition does not directly optimize the probability of failure. In this paper, we focus on the most likely event and measure the optimality of a coding scheme more directly by its probability of decoding. Our probabilistic approach leads us to a practical construction of random codes for matrix multiplication, i.e., locally random alloy codes, which are optimal with respect to the measures. Furthermore, the probabilistic approach allows us to discover a surprising impossibility theorem about both random and deterministic coded distributed tensors.