TY - GEN
T1 - Distributed Computing Trade-offs with Random Connectivity
AU - Srinivasavaradhan, Sundara Rajan
AU - Song, Linqi
AU - Fragouli, Christina
PY - 2018/6
Y1 - 2018/6
N2 - 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.
AB - 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.
KW - Broadcasting
KW - Communication-Computation Trade-Off
KW - Distributed Computation
KW - Map-Reduce
KW - Random Connectivity
UR - http://www.scopus.com/inward/record.url?scp=85052473756&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85052473756&origin=recordpage
U2 - 10.1109/ISIT.2018.8437653
DO - 10.1109/ISIT.2018.8437653
M3 - 32_Refereed conference paper (with host publication)
SN - 978-1-5386-4780-6
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1281
EP - 1285
BT - 2018 IEEE International Symposium on Information Theory (ISIT)
PB - IEEE
T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018
Y2 - 17 June 2018 through 22 June 2018
ER -