One idealistic assumption made by the sequential balanced allocations framework is that the reported load of a sampled bin is an exact estimate of its load. Mitzenmacher (2000) introduced the $\Batched$, where balls are allocated in batches of size $b$ in parallel. Berenbrink, Czumaj, Englert, Friedetzky and Nagel (2012) analysed the $b = n$ case for $\TwoChoice$ showing an $\Oh(\log n)$ bound on the gap. In this work, we improve this to $\Oh(\log n/\log \log n)$ and show that for $b \leq n \log n$, the $\TwoChoice$ gap follows the gap of $\OneChoice$ for $b$ balls and so it is asymptotically optimal.
On the contrary, for large batches $b \geq n \log n$ we show that $\TwoChoice$ has $\Gap(m) = \Theta(b/n)$ and there exist instances of $\OnePlusBeta$ that achieve the optimal $\Theta(\sqrt{b/n \cdot \log n})$ gap. Most of these results hold for a large family of processes and in the presense of weights. The experiments below demonstrate this almost quadratic improvement. Note that $\TwoChoice$ allocates aggressively to light bins, while $\OnePlusBeta$ is more gentle (see also this figure).
$\TwoChoice$
$\OnePlusBeta$-process (for $\beta = 0.6$)
.
.
