On the Optimal Recovery Threshold of Coded Matrix Multiplication

DOI10.1109/TIT.2019.2929328MaRDI QIDQ5211601zbMATH OpenOpenAlexWikidataFDO

Authors Sanghamitra Dutta, Mohammad Fahim, Farzin Haddadpour, Haewon Jeong, Viveck R. Cadambe, Pulkit Grover

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.10292

zbMATH Keywords

novel coded computation strategies for distributed matrix-matrix products

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent "Polynomial code" constructions in recovery threshold, i.e., the required number of successful workers. When $m$-th fraction of each matrix can be stored in each worker node, Polynomial codes require $m^2$ successful workers, while our MatDot codes only require $2m-1$ successful workers, albeit at a higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Further, we propose "PolyDot" coding that interpolates between Polynomial codes and MatDot codes to trade off communication cost and recovery threshold. Finally, we demonstrate a coding technique for multiplying $n$ matrices ($ngeq3$) by applying MatDot and PolyDot coding ideas.

Cited in

(1)

• Distributed matrix multiplication with straggler tolerance over very small fields

This page was built for publication: On the Optimal Recovery Threshold of Coded Matrix Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211601)