TY - GEN
T1 - On the optimal recovery threshold of coded matrix multiplication
AU - Fahim, Mohammad
AU - Jeong, Haewon
AU - Haddadpour, Farzin
AU - Dutta, Sanghamitra
AU - Cadambe, Viveck
AU - Grover, Pulkit
N1 - Funding Information:
We thank Mayank Bakshi and Yaoqing Yang for helpful discussions. We acknowledge support from NSF CNS-1702694, CCF-1553248, CCF-1464336, and CCF-1350314. This work was also supported in part by Systems on Nanoscale Information fabriCs (SONIC), one of the six SRC STARnet Centers, sponsored by MARCO and DARPA.
Funding Information:
We acknowledge support from NSF CNS-1702694
Publisher Copyright:
© 2017 IEEE.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - 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 m2 successful workers, while our novel MatDot codes only require 2m-1 successful workers, albeit at a higher communication cost from each worker to the fusion node. Further, we propose 'PolyDot' coding that interpolates between Polynomial codes and MatDot codes. Finally, we demonstrate an application of PolyDot codes to multiplying multiple (> 2) matrices.
AB - 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 m2 successful workers, while our novel MatDot codes only require 2m-1 successful workers, albeit at a higher communication cost from each worker to the fusion node. Further, we propose 'PolyDot' coding that interpolates between Polynomial codes and MatDot codes. Finally, we demonstrate an application of PolyDot codes to multiplying multiple (> 2) matrices.
UR - http://www.scopus.com/inward/record.url?scp=85047977021&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85047977021&partnerID=8YFLogxK
U2 - 10.1109/ALLERTON.2017.8262882
DO - 10.1109/ALLERTON.2017.8262882
M3 - Conference contribution
AN - SCOPUS:85047977021
T3 - 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
SP - 1264
EP - 1270
BT - 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Y2 - 3 October 2017 through 6 October 2017
ER -