About ACM Paris Kanellakis Theory and Practice Award

Yossi Azar, Tel Aviv University; Andrei Broder, Google Research; Anna Karlin, University of Washington; Michael Mitzenmacher, Harvard University; and Eli Upfal, Brown University, receive the ACM Paris Kanellakis Theory and Practice Award for the discovery and analysis of balanced allocations, known as the power of two choices, and their extensive applications to practice.

Azar, Broder, Karlin, Mitzenmacher and Upfal introduced the Balanced Allocations framework, also known as the power of two choices paradigm, an elegant theoretical work that had a 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 1994) proved that adding a little bit of choice makes a big difference. 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; now with high probability, the maximal load in any bin is bounded by (lg lg n/lg 2)+O(1).

In the same work, they have shown that, if each ball has d choices, then the maximum load drops with high probability to (ln ln n/ ln d)+O(1). These results were greatly extended by Mitzenmacher in his 1996 PhD dissertation, where he removed the sequential setting, and developed a framework for using the power of two choices in queueing systems.

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 that requires only a local decision rather than global coordination has led to a wide range of practical applications. These include i-Google's web index, Akamai’s overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, which are all based on variants of the power of two choices paradigm. There are many other software systems that use balanced allocations 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.