“The Power of Two Random Choices: A Survey of Techniques and Results”, 2001 (; backlinks; similar):
…we begin with a simple problem that demonstrates a powerful fundamental idea. Suppose that n balls are thrown into n bins, with each ball choosing a bin independently and uniformly at random. Then the maximum load, or the largest number of balls in any bins, is ~log n / log log n with high probability. Now suppose instead that the balls are placed sequentially, and each ball is placed in the least loaded of d≥2 bins chosen independently and uniformly at random. et al 1999 showed that in this case, the maximum load is log log n / log d + Θ(1) with high probability.
The important implication of this result is that even a small amount of choice can lead to drastically different results in load balancing. Indeed, having just two random choices (ie. d = 2) yields a large reduction in the maximum load by just a constant factor. Over the past several years, there has been a great deal of research investigating this phenomenon. The picture that has emerged from this research is that the power of two choices is not simply an artifact of the simple balls-and-bins model, but a general and robust phenomenon applicable to a wide variety of situations. Indeed, this two-choice paradigm continues to be applied and refined, and new results appear frequently. Applications of the two-choice paradigm:…Hashing, Shared memory emulations, load balancing, low-congestion circuit routing.
[cf. “The Power of Two Choices in Randomized Load Balancing”, 1996; Nginx/HAProxy, Marc Brooker.]