Coded Distributed Computing: Straggling Servers and Multistage Dataflows

Songze Li; Mohammad Ali Maddah-Ali; A. Salman Avestimehr

doi:10.1109/ALLERTON.2016.7852225

Coded Distributed Computing: Straggling Servers and Multistage Dataflows

Songze Li
, Mohammad Ali Maddah-Ali
, A. Salman Avestimehr

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

35 Scopus citations

Abstract

In this paper, we first review the Coded Distributed Computing (CDC) framework, recently proposed to significantly slash the data shuffling load of distributed computing via coding, and then discuss the extension of the CDC techniques to cope with two major challenges in general distributed computing problems, namely the straggling servers and multistage computations. When faced with straggling servers in a distributed computing cluster, we describe a unified coding scheme that superimposes CDC with the Maximum-Distance-Separable (MDS) coding on computation tasks, which allows a flexible tradeoff between computation latency and communication load. On the other hand, for a general multistage computation task expressed as a directed acyclic graph (DAG), we propose a coded framework that given the load of computation on each vertex of the DAG, applies the generalized CDC scheme individually on each vertex to minimize the communication load.

Original language	English (US)
Title of host publication	54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	164-171
Number of pages	8
ISBN (Electronic)	9781509045495
DOIs	https://doi.org/10.1109/ALLERTON.2016.7852225
State	Published - Feb 10 2017
Externally published	Yes
Event	54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 - Monticello, United States Duration: Sep 27 2016 → Sep 30 2016

Publication series

Name	54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

Other

Other	54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
Country/Territory	United States
City	Monticello
Period	9/27/16 → 9/30/16

Bibliographical note

Publisher Copyright:
© 2016 IEEE.

Publisher link

10.1109/ALLERTON.2016.7852225

Find It

Find It at U of M Libraries

Cite this

Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2017). Coded Distributed Computing: Straggling Servers and Multistage Dataflows. In 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 (pp. 164-171). Article 7852225 (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2016.7852225

Coded Distributed Computing: Straggling Servers and Multistage Dataflows. / Li, Songze; Maddah-Ali, Mohammad Ali; Avestimehr, A. Salman.
54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016. Institute of Electrical and Electronics Engineers Inc., 2017. p. 164-171 7852225 (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Li, S, Maddah-Ali, MA & Avestimehr, AS 2017, Coded Distributed Computing: Straggling Servers and Multistage Dataflows. in 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016., 7852225, 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016, Institute of Electrical and Electronics Engineers Inc., pp. 164-171, 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016, Monticello, United States, 9/27/16. https://doi.org/10.1109/ALLERTON.2016.7852225

Li S, Maddah-Ali MA, Avestimehr AS. Coded Distributed Computing: Straggling Servers and Multistage Dataflows. In 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016. Institute of Electrical and Electronics Engineers Inc. 2017. p. 164-171. 7852225. (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016). doi: 10.1109/ALLERTON.2016.7852225

Li, Songze ; Maddah-Ali, Mohammad Ali ; Avestimehr, A. Salman. / Coded Distributed Computing : Straggling Servers and Multistage Dataflows. 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 164-171 (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016).

@inproceedings{c708502b5b0f4952a99ee288288e4cb7,

title = "Coded Distributed Computing: Straggling Servers and Multistage Dataflows",

abstract = "In this paper, we first review the Coded Distributed Computing (CDC) framework, recently proposed to significantly slash the data shuffling load of distributed computing via coding, and then discuss the extension of the CDC techniques to cope with two major challenges in general distributed computing problems, namely the straggling servers and multistage computations. When faced with straggling servers in a distributed computing cluster, we describe a unified coding scheme that superimposes CDC with the Maximum-Distance-Separable (MDS) coding on computation tasks, which allows a flexible tradeoff between computation latency and communication load. On the other hand, for a general multistage computation task expressed as a directed acyclic graph (DAG), we propose a coded framework that given the load of computation on each vertex of the DAG, applies the generalized CDC scheme individually on each vertex to minimize the communication load.",

author = "Songze Li and Maddah-Ali, \{Mohammad Ali\} and Avestimehr, \{A. Salman\}",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 ; Conference date: 27-09-2016 Through 30-09-2016",

year = "2017",

month = feb,

day = "10",

doi = "10.1109/ALLERTON.2016.7852225",

language = "English (US)",

series = "54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "164--171",

booktitle = "54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016",

}

TY - GEN

T1 - Coded Distributed Computing

T2 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

AU - Li, Songze

AU - Maddah-Ali, Mohammad Ali

AU - Avestimehr, A. Salman

PY - 2017/2/10

Y1 - 2017/2/10

N2 - In this paper, we first review the Coded Distributed Computing (CDC) framework, recently proposed to significantly slash the data shuffling load of distributed computing via coding, and then discuss the extension of the CDC techniques to cope with two major challenges in general distributed computing problems, namely the straggling servers and multistage computations. When faced with straggling servers in a distributed computing cluster, we describe a unified coding scheme that superimposes CDC with the Maximum-Distance-Separable (MDS) coding on computation tasks, which allows a flexible tradeoff between computation latency and communication load. On the other hand, for a general multistage computation task expressed as a directed acyclic graph (DAG), we propose a coded framework that given the load of computation on each vertex of the DAG, applies the generalized CDC scheme individually on each vertex to minimize the communication load.

AB - In this paper, we first review the Coded Distributed Computing (CDC) framework, recently proposed to significantly slash the data shuffling load of distributed computing via coding, and then discuss the extension of the CDC techniques to cope with two major challenges in general distributed computing problems, namely the straggling servers and multistage computations. When faced with straggling servers in a distributed computing cluster, we describe a unified coding scheme that superimposes CDC with the Maximum-Distance-Separable (MDS) coding on computation tasks, which allows a flexible tradeoff between computation latency and communication load. On the other hand, for a general multistage computation task expressed as a directed acyclic graph (DAG), we propose a coded framework that given the load of computation on each vertex of the DAG, applies the generalized CDC scheme individually on each vertex to minimize the communication load.

UR - https://www.scopus.com/pages/publications/85015248675

UR - https://www.scopus.com/pages/publications/85015248675#tab=citedBy

U2 - 10.1109/ALLERTON.2016.7852225

DO - 10.1109/ALLERTON.2016.7852225

M3 - Conference contribution

AN - SCOPUS:85015248675

T3 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

SP - 164

EP - 171

BT - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 27 September 2016 through 30 September 2016

ER -

Coded Distributed Computing: Straggling Servers and Multistage Dataflows

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this