Simulations between Strongly Sublinear MPC and Node-Capacitated Clique

Abstract

We study how the Massively Parallel Computation (MPC) model in the strongly sublinear regime relates to the classic, 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/receive only a bounded number of $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$, where no 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.