Brief Announcement:
Simulations between Massively Parallel Computing and Distributed Computing

Summary

We study how the Massively Parallel Computation ($\MPC$) model in the strongly sublinear regime relates to graph-centric distributed models, focusing on the Node-Capacitated Clique ($\NCC$), a bandwidth-parametrized generalization of the Congested Clique. In $\MPC$, $M$ machines with per-machine memory $S$ hold a partition of the input graph. In $\NCC$, we are given $n$ nodes that are themselves machines that know their full neighborhood but can send and receive at most $C$ words per round. We are interested in the strongly sublinear regime where $S=n^\delta$, for some constant $0 < \delta <1$ and $C = MS/n$, for which no prior simulation results are known. We explore when deterministic round-preserving simulations between these models are possible and when they are provably not, for different model parameters, problem families and graph classes. On the positive side, we provide techniques that allow, under certain restrictions, simulations with only constant overhead. On the negative side, we prove simulation impossibility results, which show that the limitations of our simulation results are inherent.