## Description

Encoding that provides an extra redundancy for distributed matrix computation algorithms such as matrix multiplication. Parallelized algorithms distribute a desired computation over many nodes, and a key performance bottleneck is due to some nodes completing their individual tasks much later than other nodes. Matrix computation codes provide a layer of redundancy such that the computation can be performed without having all nodes finish their piece of the computation.

## Protection

Allows computation to complete without waiting for stragglers, or nodes that either do not finish or finish their portion of the computation much later than all other nodes.

## Parent

## Cousin

- Maximum distance separable (MDS) code — The first matrix multiplication code encoded each entry of the matrices to be multiplied into an MDS code [1].

## References

- [1]
- K. Lee et al., “Speeding Up Distributed Machine Learning Using Codes”, IEEE Transactions on Information Theory 64, 1514 (2018) arXiv:1512.02673 DOI

## Page edit log

- Victor V. Albert (2022-06-06) — most recent

## Cite as:

“Distributed computation code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/matrix_computation