ACM Paris Kanellakis Theory and Practice Award
Israel - 2020
For the discovery and analysis of balanced allocations, known as the power of two choices, and their extensive applications to practice.
ACM has named Yossi Azar of Tel Aviv University, Andrei Broder of Google Research, Anna Karlin of the University of Washington, Michael Mitzenmacher of Harvard University, and Eli Upfal of Brown University recipients of the ACM Paris Kanellakis Theory and Practice award for their breakthrough work on the Balanced Allocations paradigm, also known as the power of two choices, an elegant theoretical work which has had profound and widespread practical impact.
When n balls are thrown into n bins chosen uniformly at random, it is known that with high probability, the maximum load on any bin is bounded by (lg n/lg lg n) (1+o(1)). Azar, Broder, Karlin, and Upfal (STOC 94) proved that adding a little bit of choice can work wonders. When throwing each ball, instead of choosing one bin at random, choose two bins at random, and then place the ball in the bin with the lesser load. This minor change brings on an exponential improvement; with high probability, the maximal load in any bin is bounded by (lg lg n/lg 2)+O(1). In the same work they extended the selection of bins from two to d, choosing the bin with the least load for the new ball, obtaining with high probability a bound of (ln ln n/ ln d)+O(1). These results were greatly extended by Mitzenmacher in his 1996 PhD dissertation: he removed the sequential setting in the 1994 work and developed a framework for using the power of two choices in queuing systems. These works led to a wide adoption of the power of two choices paradigm in the networking community, with applications in many areas in Computer Science.
Since bins and balls are the basic model for analyzing data structures such as hashing or processes like load balancing of jobs in servers, it is not surprising that the power of two choices has led to a wide range of practical applications. These include i-Google's web index which uses Balanced Allocations, Akamai's overlay routing network which applies an algorithm inspired by the power of two choices paradigm, and highly reliable distributed data storage systems used by Microsoft and Dropbox which are based on variants of the power of two paradigm. There are many other software systems that use the paradigm as an important ingredient.
The Balanced Allocations paper and the follow-up work on the power of two choices are elegant theoretical results, and their content had and will surely continue to have a demonstrable effect on the practice of computing.