# Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors

arXiv: https://arxiv.org/abs/2202.03469 · HTML: https://mlsanity.com/paper/2202.03469/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 25 references that are in the map.
- First posted on arXiv 7 Feb 2022.

## Builds on (most cited first, 9 of 9)

- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [A Unified Coded Deep Neural Network Training Strategy Based on Generalized PolyDot Codes for Matrix Multiplication](https://mlsanity.com/paper/1811.10751/) (2018)
- [Coded Sparse Matrix Multiplication](https://mlsanity.com/paper/1802.03430/) (2018)
- [Distributed Matrix-Vector Multiplication: A Convolutional Coding Approach](https://mlsanity.com/paper/1901.08716/) (2019)
- [Erasure coding for distributed matrix multiplication for matrices with bounded entries](https://mlsanity.com/paper/1811.02144/) (2018)
- [Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent](https://mlsanity.com/paper/2201.12990/) (2022)

## Abstract (arXiv)

Tensors are a fundamental operation in distributed computing, 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.