Parallel Communication Obliviousness: One Round and Beyond

This paper studies communication-oblivious algorithms under the massively parallel computation (MPC) model. The communication patterns of these algorithms follow a distribution dependent only on the definition of the underlying problem, the problem size N, and the number p of machines, but not on the specific input elements. Our objective is to understand when obliviousness necessitates --- or does not necessitate --- heavier communication compared to the traditional MPC model that does not enforce such a requirement. The first part of our investigation focuses on single-round algorithms. We prove that skew-free hashing, a fundamental problem solvable with load Õ(N/p) (with high probability or w.h.p. for short) under the traditional model, demands a load of nearly Ω(N) under communication obliviousness. Intriguingly, we show that hashing can still be applied in an oblivious manner to process any natural join in one round with a load complexity matching that of the best traditional MPC algorithm. The second part of our investigation studies compilation methods that convert a traditional MPC algorithm A into a communication-oblivious counterpart. Given an A that operates within l = poly(p) rounds and entails a load at most L = Ω(p log p) w.h.p., we can produce w.h.p. a communication-oblivious version running in 2l rounds with a load at most (1 + δ) L, where δ < 0 can be an arbitrarily small constant. Additionally, we establish hardness results indicating that the theoretical guarantees of our compilation can no longer be significantly improved.