The Two-Choice Process

An improvement over the \(\OneChoice \) process is the \(\TwoChoice \) process, where for each ball two bins are chosen uniformly at random and the ball is allocated to the least loaded bin.

The \(\TwoChoice \) process:
Iteration: At each step \(t = 1, 2, \ldots \),

  • • Sample two bins \(i_1 = i_1^t\) and \(i_2 = i_2^t\) uniformly at random.

  • • Allocate one ball to bin \(i^t \in \{ i_1, i_2 \}\) such that \(y_{i^t}^{t+1} = \min \{ x_{i_1}^t, x_{i_2}^t \}\).

Azar, Broder, Karlin and Upfal (1999) (and implicitly Karp, Luby and Meyer auf der Heide (1996)) showed that the \(\TwoChoice \) process achieves w.h.p. an \(\log _2 \log n + \Theta (1)\) gap, which is an exponential improvement over the \(\Theta (\frac {\log n}{\log \log n})\) gap of \(\OneChoice \). Berenbrink, Czumaj, Steger and Vöcking (2006) extended the analysis to the heavily-loaded case (for any \(m \geq n\)) proving a gap of \(\log _2 \log n + \Theta (1)\).

Your browser does not support the HTML5 canvas tag.


Power of two-choices

The difference in the gap of the \(\OneChoice \) and \(\TwoChoice \) process is known as the “power of two choices" phenomenon.


Your browser does not support the HTML5 canvas tag.


Your browser does not support the HTML5 canvas tag.


  • [1]  Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM J. Comput., 29(1):180–200, 1999.

  • [2]  Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. Balanced allocations: the heavily loaded case. SIAM J. Comput., 35(6):1350–1385, 2006.

  • [3]  Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. Algorithmica, 16(4-5):517–542, 1996.