Coded distributed computing: Fundamental limits and practical challenges

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

doi:10.1109/ACSSC.2016.7869092

Coded distributed computing: Fundamental limits and practical challenges

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

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

23 Scopus citations

Abstract

In this paper, we demonstrate a coded computing framework, named Coded Distributed Computing (CDC), which optimally trades extra computation resources for communication bandwidth in a MapReduce-type distributed computing environment. We also empirically illustrate the practical impact of CDC by analyzing the performance of a distributed sorting algorithm, named CodedTeraSort, which was developed by integrating the coding principle of CDC into the Hadoop benchmark TeraSort. Experiment results illustrate 1.97×-3.39 × speedup using CodedTeraSort, compared with TeraSort, for typical settings of interest. In the end, we review some of the open problems and future directions.

Original language	English (US)
Title of host publication	Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Editors	Michael B. Matthews
Publisher	IEEE Computer Society
Pages	509-513
Number of pages	5
ISBN (Electronic)	9781538639542
DOIs	https://doi.org/10.1109/ACSSC.2016.7869092
State	Published - Mar 1 2017
Externally published	Yes
Event	50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 - Pacific Grove, United States Duration: Nov 6 2016 → Nov 9 2016

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)	1058-6393

Other

Other	50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Country/Territory	United States
City	Pacific Grove
Period	11/6/16 → 11/9/16

Bibliographical note

Publisher Copyright:
© 2016 IEEE.

Publisher link

10.1109/ACSSC.2016.7869092

Find It

Find It at U of M Libraries

Cite this

Li, S., Yu, Q., Maddah-Ali, M. A., & Avestimehr, A. S. (2017). Coded distributed computing: Fundamental limits and practical challenges. In M. B. Matthews (Ed.), Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 (pp. 509-513). Article 7869092 (Conference Record - Asilomar Conference on Signals, Systems and Computers). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2016.7869092

Coded distributed computing: Fundamental limits and practical challenges. / Li, Songze; Yu, Qian; Maddah-Ali, Mohammad Ali et al.
Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. ed. / Michael B. Matthews. IEEE Computer Society, 2017. p. 509-513 7869092 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

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

Li, S, Yu, Q, Maddah-Ali, MA & Avestimehr, AS 2017, Coded distributed computing: Fundamental limits and practical challenges. in MB Matthews (ed.), Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016., 7869092, Conference Record - Asilomar Conference on Signals, Systems and Computers, IEEE Computer Society, pp. 509-513, 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016, Pacific Grove, United States, 11/6/16. https://doi.org/10.1109/ACSSC.2016.7869092

Li S, Yu Q, Maddah-Ali MA, Avestimehr AS. Coded distributed computing: Fundamental limits and practical challenges. In Matthews MB, editor, Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. IEEE Computer Society. 2017. p. 509-513. 7869092. (Conference Record - Asilomar Conference on Signals, Systems and Computers). doi: 10.1109/ACSSC.2016.7869092

Li, Songze ; Yu, Qian ; Maddah-Ali, Mohammad Ali et al. / Coded distributed computing : Fundamental limits and practical challenges. Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. editor / Michael B. Matthews. IEEE Computer Society, 2017. pp. 509-513 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

@inproceedings{ab68e9b0c1b449429b7436e24317ebed,

title = "Coded distributed computing: Fundamental limits and practical challenges",

abstract = "In this paper, we demonstrate a coded computing framework, named Coded Distributed Computing (CDC), which optimally trades extra computation resources for communication bandwidth in a MapReduce-type distributed computing environment. We also empirically illustrate the practical impact of CDC by analyzing the performance of a distributed sorting algorithm, named CodedTeraSort, which was developed by integrating the coding principle of CDC into the Hadoop benchmark TeraSort. Experiment results illustrate 1.97×-3.39 × speedup using CodedTeraSort, compared with TeraSort, for typical settings of interest. In the end, we review some of the open problems and future directions.",

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

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 ; Conference date: 06-11-2016 Through 09-11-2016",

year = "2017",

month = mar,

day = "1",

doi = "10.1109/ACSSC.2016.7869092",

language = "English (US)",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

publisher = "IEEE Computer Society",

pages = "509--513",

editor = "Matthews, \{Michael B.\}",

booktitle = "Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016",

}

TY - GEN

T1 - Coded distributed computing

T2 - 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

AU - Li, Songze

AU - Yu, Qian

AU - Maddah-Ali, Mohammad Ali

AU - Avestimehr, A. Salman

PY - 2017/3/1

Y1 - 2017/3/1

N2 - In this paper, we demonstrate a coded computing framework, named Coded Distributed Computing (CDC), which optimally trades extra computation resources for communication bandwidth in a MapReduce-type distributed computing environment. We also empirically illustrate the practical impact of CDC by analyzing the performance of a distributed sorting algorithm, named CodedTeraSort, which was developed by integrating the coding principle of CDC into the Hadoop benchmark TeraSort. Experiment results illustrate 1.97×-3.39 × speedup using CodedTeraSort, compared with TeraSort, for typical settings of interest. In the end, we review some of the open problems and future directions.

AB - In this paper, we demonstrate a coded computing framework, named Coded Distributed Computing (CDC), which optimally trades extra computation resources for communication bandwidth in a MapReduce-type distributed computing environment. We also empirically illustrate the practical impact of CDC by analyzing the performance of a distributed sorting algorithm, named CodedTeraSort, which was developed by integrating the coding principle of CDC into the Hadoop benchmark TeraSort. Experiment results illustrate 1.97×-3.39 × speedup using CodedTeraSort, compared with TeraSort, for typical settings of interest. In the end, we review some of the open problems and future directions.

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

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

U2 - 10.1109/ACSSC.2016.7869092

DO - 10.1109/ACSSC.2016.7869092

M3 - Conference contribution

AN - SCOPUS:85016328209

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 509

EP - 513

BT - Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

A2 - Matthews, Michael B.

PB - IEEE Computer Society

Y2 - 6 November 2016 through 9 November 2016

ER -

Coded distributed computing: Fundamental limits and practical challenges

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this