@inproceedings{c83006ff8aa14dd5b97e17605cd2a09c, title = "Distributed Computing Trade-offs with Random Connectivity", 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.", keywords = "Broadcasting, Communication-Computation Trade-Off, Distributed Computation, Map-Reduce, Random Connectivity", author = "Srinivasavaradhan, {Sundara Rajan} and Linqi Song and Christina Fragouli", year = "2018", month = jun, doi = "10.1109/ISIT.2018.8437653", language = "English", isbn = "978-1-5386-4780-6", series = "IEEE International Symposium on Information Theory - Proceedings", publisher = "IEEE", pages = "1281--1285", booktitle = "2018 IEEE International Symposium on Information Theory (ISIT)", note = "2018 IEEE International Symposium on Information Theory, ISIT 2018 ; Conference date: 17-06-2018 Through 22-06-2018", }