Distributed Computing Trade-offs with Random Connectivity

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.