Parallel Balanced Allocations: The Heavily Loaded Case
Parallel Balanced Allocations: The Heavily Loaded Case
We study parallel algorithms for the classical balls-into-bins problem, in which $m$ balls acting in parallel as separate agents are placed into $n$ bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins …