A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes

Qifa Yan; Michele Wigger; Sheng Yang; Xiaohu Tang

doi:10.1109/ISIT.2019.8849615

A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes

Qifa Yan, Michele Wigger, Sheng Yang, Xiaohu Tang

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

Abstract

The optimal storage-computation tradeoff is characterized for a MapReduce-like distributed computing system with straggling nodes, where only a part of the nodes can be utilized to compute the desired output functions. The result holds for arbitrary output functions and thus generalizes previous results that restricted to linear functions. Specifically, in this work, we propose a new information-theoretical converse and a new matching coded computing scheme, that we call coded computing for straggling systems (CCS).

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	2803-2807
Number of pages	5
ISBN (Electronic)	9781538692912
DOIs	https://doi.org/10.1109/ISIT.2019.8849615
Publication status	Published - 1 Jul 2019
Externally published	Yes
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: 7 Jul 2019 → 12 Jul 2019

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	7/07/19 → 12/07/19

Access to Document

10.1109/ISIT.2019.8849615

Cite this

Yan, Q., Wigger, M., Yang, S., & Tang, X. (2019). A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (pp. 2803-2807). Article 8849615 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849615

Yan, Qifa ; Wigger, Michele ; Yang, Sheng et al. / A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes. 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 2803-2807 (IEEE International Symposium on Information Theory - Proceedings).

@inproceedings{9e7236b5744949d8926a48e9e44d5861,

title = "A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes",

abstract = "The optimal storage-computation tradeoff is characterized for a MapReduce-like distributed computing system with straggling nodes, where only a part of the nodes can be utilized to compute the desired output functions. The result holds for arbitrary output functions and thus generalizes previous results that restricted to linear functions. Specifically, in this work, we propose a new information-theoretical converse and a new matching coded computing scheme, that we call coded computing for straggling systems (CCS).",

author = "Qifa Yan and Michele Wigger and Sheng Yang and Xiaohu Tang",

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,

day = "1",

doi = "10.1109/ISIT.2019.8849615",

language = "English",

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

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

pages = "2803--2807",

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

}

Yan, Q, Wigger, M, Yang, S & Tang, X 2019, A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849615, IEEE International Symposium on Information Theory - Proceedings, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 2803-2807, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7/07/19. https://doi.org/10.1109/ISIT.2019.8849615

A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes. / Yan, Qifa; Wigger, Michele; Yang, Sheng et al.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 2803-2807 8849615 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July).

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

TY - GEN

T1 - A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes

AU - Yan, Qifa

AU - Wigger, Michele

AU - Yang, Sheng

AU - Tang, Xiaohu

PY - 2019/7/1

Y1 - 2019/7/1

N2 - The optimal storage-computation tradeoff is characterized for a MapReduce-like distributed computing system with straggling nodes, where only a part of the nodes can be utilized to compute the desired output functions. The result holds for arbitrary output functions and thus generalizes previous results that restricted to linear functions. Specifically, in this work, we propose a new information-theoretical converse and a new matching coded computing scheme, that we call coded computing for straggling systems (CCS).

AB - The optimal storage-computation tradeoff is characterized for a MapReduce-like distributed computing system with straggling nodes, where only a part of the nodes can be utilized to compute the desired output functions. The result holds for arbitrary output functions and thus generalizes previous results that restricted to linear functions. Specifically, in this work, we propose a new information-theoretical converse and a new matching coded computing scheme, that we call coded computing for straggling systems (CCS).

U2 - 10.1109/ISIT.2019.8849615

DO - 10.1109/ISIT.2019.8849615

M3 - Conference contribution

AN - SCOPUS:85073153102

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2803

EP - 2807

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 -

Yan Q, Wigger M, Yang S, Tang X. A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 2803-2807. 8849615. (IEEE International Symposium on Information Theory - Proceedings). doi: 10.1109/ISIT.2019.8849615

A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this