Eli Upfal

Digital Library

ACM Paris Kanellakis Theory and Practice Award

USA - 2020

citation

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.

Press Release

ACM Fellows

USA - 2005

citation

For contributions to parallel and stochastic networks.

2020 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.