CodedSketch: Coded Distributed Computation of Approximated Matrix Multiplication

Tayyebeh Jahani-Nezhad, Mohammad Ali Maddah-Ali

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that the master node needs to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count-sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count-sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count-sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes.

Original languageEnglish (US)
Title of host publication2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2489-2493
Number of pages5
ISBN (Electronic)9781538692912
DOIs
StatePublished - Jul 2019
Externally publishedYes
Event2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France
Duration: Jul 7 2019Jul 12 2019

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2019-July
ISSN (Print)2157-8095

Conference

Conference2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/TerritoryFrance
CityParis
Period7/7/197/12/19

Bibliographical note

Publisher Copyright:
© 2019 IEEE.

Fingerprint

Dive into the research topics of 'CodedSketch: Coded Distributed Computation of Approximated Matrix Multiplication'. Together they form a unique fingerprint.

Cite this