Distributed Computing Trade-offs with Random Connectivity

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with host publication)peer-review

18 Scopus Citations
View graph of relations

Author(s)

  • Sundara Rajan Srinivasavaradhan
  • Linqi Song
  • Christina Fragouli

Detail(s)

Original languageEnglish
Title of host publication2018 IEEE International Symposium on Information Theory (ISIT)
PublisherIEEE
Pages1281-1285
ISBN (Print)978-1-5386-4780-6
Publication statusPublished - Jun 2018
Externally publishedYes

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2018-June
ISSN (Print)2157-8095

Conference

Title2018 IEEE International Symposium on Information Theory, ISIT 2018
PlaceUnited States
CityVail
Period17 - 22 June 2018

Abstract

Trade-offs between distributed computation and communication are recently attracting significant interest; however, these works assume that all nodes that share the distributed computation task are within the same broadcast domain, and each can losslessly broadcast to every other node that takes part in the computation task. In this work, we dispose of this assumption, and consider the case where each node can broadcast to a subset of the nodes that take part in the computation task. We model the network via an Erdos-Renyi random graph model where a pair of nodes can communicate with each other with a probability p. We propose both uncoded and coded transmission schemes and give an achievable communication-computation tradeoff for large computational loads.

Research Area(s)

  • Broadcasting, Communication-Computation Trade-Off, Distributed Computation, Map-Reduce, Random Connectivity

Citation Format(s)

Distributed Computing Trade-offs with Random Connectivity. / Srinivasavaradhan, Sundara Rajan; Song, Linqi; Fragouli, Christina.
2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 2018. p. 1281-1285 8437653 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-June).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with host publication)peer-review