Coded Distributed Computing over Packet Erasure Channels

Dong Jun Han; Jy Yong Sohn; Jaekyun Moon

doi:10.1109/ISIT.2019.8849747

Coded Distributed Computing over Packet Erasure Channels

Dong Jun Han, Jy Yong Sohn, Jaekyun Moon

Department of Applied Statistics

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

8 Citations (Scopus)

Abstract

Coded computation is a framework which provides redundancy in distributed computing systems to speed up large-scale tasks. Although most existing works assume error-free scenarios, the link failures are common in current wired/wireless networks. In this paper, we consider the straggler problem in distributed computing systems with link failures, by modeling the links between the master node and worker nodes as packet erasure channels. We first analyze the latency in this setting using an (n, k) maximum distance separable (MDS) code. Then, we consider a setup where the number of retransmissions is limited due to the bandwidth constraint. By formulating practical optimization problems related to latency, bandwidth and probability of successful computation, we obtain achievable performance curves as a function of packet erasure probability.

Original language	English
Title of host publication	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	717-721
Number of pages	5
ISBN (Electronic)	9781538692912
DOIs	https://doi.org/10.1109/ISIT.2019.8849747
Publication status	Published - 2019 Jul
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: 2019 Jul 7 → 2019 Jul 12

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2019-July
ISSN (Print)	2157-8095

Conference

Conference	2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/Territory	France
City	Paris
Period	19/7/7 → 19/7/12

Bibliographical note

Publisher Copyright:
© 2019 IEEE.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modelling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2019.8849747

Cite this

Han, D. J., Sohn, J. Y., & Moon, J. (2019). Coded Distributed Computing over Packet Erasure Channels. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (pp. 717-721). Article 8849747 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849747

@inproceedings{cacf74bc03074c6f9f9bf915f74ae21b,

title = "Coded Distributed Computing over Packet Erasure Channels",

abstract = "Coded computation is a framework which provides redundancy in distributed computing systems to speed up large-scale tasks. Although most existing works assume error-free scenarios, the link failures are common in current wired/wireless networks. In this paper, we consider the straggler problem in distributed computing systems with link failures, by modeling the links between the master node and worker nodes as packet erasure channels. We first analyze the latency in this setting using an (n, k) maximum distance separable (MDS) code. Then, we consider a setup where the number of retransmissions is limited due to the bandwidth constraint. By formulating practical optimization problems related to latency, bandwidth and probability of successful computation, we obtain achievable performance curves as a function of packet erasure probability.",

author = "Han, {Dong Jun} and Sohn, {Jy Yong} and Jaekyun Moon",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

doi = "10.1109/ISIT.2019.8849747",

language = "English",

series = "IEEE International Symposium on Information Theory - Proceedings",

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

pages = "717--721",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

address = "United States",

}

Han, DJ, Sohn, JY & Moon, J 2019, Coded Distributed Computing over Packet Erasure Channels. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849747, IEEE International Symposium on Information Theory - Proceedings, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 717-721, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 19/7/7. https://doi.org/10.1109/ISIT.2019.8849747

Coded Distributed Computing over Packet Erasure Channels. / Han, Dong Jun; Sohn, Jy Yong; Moon, Jaekyun.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 717-721 8849747 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July).

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

TY - GEN

T1 - Coded Distributed Computing over Packet Erasure Channels

AU - Han, Dong Jun

AU - Sohn, Jy Yong

AU - Moon, Jaekyun

PY - 2019/7

Y1 - 2019/7

N2 - Coded computation is a framework which provides redundancy in distributed computing systems to speed up large-scale tasks. Although most existing works assume error-free scenarios, the link failures are common in current wired/wireless networks. In this paper, we consider the straggler problem in distributed computing systems with link failures, by modeling the links between the master node and worker nodes as packet erasure channels. We first analyze the latency in this setting using an (n, k) maximum distance separable (MDS) code. Then, we consider a setup where the number of retransmissions is limited due to the bandwidth constraint. By formulating practical optimization problems related to latency, bandwidth and probability of successful computation, we obtain achievable performance curves as a function of packet erasure probability.

AB - Coded computation is a framework which provides redundancy in distributed computing systems to speed up large-scale tasks. Although most existing works assume error-free scenarios, the link failures are common in current wired/wireless networks. In this paper, we consider the straggler problem in distributed computing systems with link failures, by modeling the links between the master node and worker nodes as packet erasure channels. We first analyze the latency in this setting using an (n, k) maximum distance separable (MDS) code. Then, we consider a setup where the number of retransmissions is limited due to the bandwidth constraint. By formulating practical optimization problems related to latency, bandwidth and probability of successful computation, we obtain achievable performance curves as a function of packet erasure probability.

UR - http://www.scopus.com/inward/record.url?scp=85073144691&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073144691&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849747

DO - 10.1109/ISIT.2019.8849747

M3 - Conference contribution

AN - SCOPUS:85073144691

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 717

EP - 721

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

Coded Distributed Computing over Packet Erasure Channels

Abstract

Publication series

Conference

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this