Distributed computation code 

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

References

[1]
K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding Up Distributed Machine Learning Using Codes”, IEEE Transactions on Information Theory 64, 1514 (2018) arXiv:1512.02673 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: matrix_computation

Cite as:
“Distributed computation code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/matrix_computation
BibTeX:
@incollection{eczoo_matrix_computation, title={Distributed computation code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/matrix_computation} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/matrix_computation

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/matrices/matrix_computation.yml.