The classical balls-and-bins model and its two-choice variant have been extensively studied
in probability theory, random graph theory, and computer science. Many applications have been found
in various areas, such as hashing, load balancing and resource allocation in parallel and distributed
systems (see e.g., [1]}, [2]}, [3]}, [4]}, [5]}).
In the balls-and-bins model, it is known that for \(m=\Theta (n)\) , the maximum load is \((1+o(1))\frac{\log n}{\log \log n}\)  with high probability, and for \(m\gg n\) , the maximum load is \(\Theta \Big (\sqrt{\frac{m\log n}{n}}\Big )\)  with high probability (see e.g. [6]}). In the seminal paper [1]}, Azar, Broder, Karlin and Upfal showed that in the two-choice model, for \(m=\Theta (n)\) , the maximum load is \(\frac{\log \log n}{\log 2}+O(1)\)  with high probability – an exponential improvement over the balls-and-bins model. In fact, this phenomenon was first noticed by Karp, Luby and Meyer auf der Heide [3]} in the context of PRAM simulations when switching from one hash function to two. In [1]}, the \(d\) -choice setting, where the overseer is given \(d>2\)  choices, was also considered.
In this setting, an optimal maximum load of \(\frac{\log \log n}{\log d}+O(1)\)  can be achieved with high probability; that is, compared with the case \(d=2\) , the performance improves by merely a multiplicative factor for larger values of \(d\) . We refer the reader to the survey [10]} for more details about the two-choice model.
