Coded Matrix Multiplication on a Group-Based Model

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

  • Muah Kim - , Korea Advanced Institute of Science & Technology (KAIST) (Autor:in)
  • Jy-yong Sohn - , Korea Advanced Institute of Science & Technology (KAIST) (Autor:in)
  • Jaekyun Moon - , Korea Advanced Institute of Science & Technology (KAIST) (Autor:in)

Abstract

Coded distributed computing has been considered as a promising technique which makes large-scale systems robust to the "straggler" workers. Yet, practical system models for distributed computing have not been available that reflect the clustered or grouped structure of real-world computing servers. Also, the large variations in the computing power and bandwidth capabilities across different servers have not been properly modeled. We suggest a group-based model to reflect practical conditions and develop an appropriate coding scheme for this model. The suggested code, called group code, employs parallel encoding for each group. We show that the suggested coding scheme can asymptotically achieve optimal computing time in the regime of infinite n, the number of workers. While theoretical analysis is conducted in the asymptotic regime, numerical results also show that the suggested scheme achieves near-optimal computing time for any finite but reasonably large n. Moreover, we demonstrate that decoding complexity of the suggested scheme is significantly reduced by the virtue of parallel decoding.

Details

OriginalspracheEnglisch
Titel2019 IEEE International Symposium on Information Theory (ISIT)
Herausgeber (Verlag)IEEE
Seiten722-726
Seitenumfang5
ISBN (Print)978-1-5386-9292-9
PublikationsstatusVeröffentlicht - 12 Juli 2019
Peer-Review-StatusJa
Extern publiziertJa

Konferenz

Titel2019 IEEE International Symposium on Information Theory (ISIT)
Dauer7 - 12 Juli 2019
OrtParis, France

Externe IDs

Scopus 85073151316

Schlagworte

Schlagwörter

  • Computational modeling, Decoding, Task analysis, Encoding, Complexity theory, Distributed computing, Resource management