This week, Professor Eli Upfal of Brown CS and his collaborators received one of theoretical computer science's highest honors, an award that also pays tribute to Eli's predecessor at Brown University. Together with Yossi Azar (Tel Aviv University), Andrei Broder (Google Research), Anna Karlin (University of Washington), and Michael Mitzenmacher (Harvard University), Upfal has won the Association for Computing Machinery (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.
The ACM is the world's largest educational and scientific computing society, and Eli is the first Brown CS recipient of this accolade, which is given annually to recognize specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing. It's accompanied by a prize of $10,000.
In a 1994 paper, Eli and his colleagues introduced the balanced allocations framework, also known as the power of two choices paradigm, a theoretical work that has had widespread practical impact. It can be explained as follows: when n balls are thrown into n bins chosen uniformly at random, it's known with high probability that the maximum load on any bin is bounded by (lg n/lg lg n) (1+o(1)). The researchers proved that adding a little bit of choice makes a big difference. When throwing each ball, instead of choosing one bin at random, the thrower should choose two bins at random, then place the ball in the bin with the lesser load. This minor change brings 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 show that if each ball has d choices, the maximum load drops with high probability to (ln ln n/ ln d)+O(1).
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's not surprising that the power of two choices, which requires only a local decision rather than global coordination, has led to a wide range of practical applications. Just a few examples include Google's web index, Akamai’s overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, all based on variants of the power of two choices paradigm.
"The Balanced Allocations paper and the follow-up work on the power of two choices," the ACM writes, "are elegant theoretical results, and their content had, and will surely continue to have, a demonstrable effect on the practice of computing."
Paris Kanellakis was a distinguished computer scientist who was an esteemed and beloved member of the Brown CS community. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing, and combinatorial optimization.
"Winning this award is special for me," says Eli. "I've always been proud to be Paris's successor at Brown, and being recognized as someone who has had a similar impact on computing practice is really an honor. Bringing an award named for Paris Kanellakis back to Brown feels like closing a circle."
The full ACM press release is available here.
For more information, click the link that follows to contact Brown CS Communication Outreach Specialist Jesse C. Polhemus.