The researchers who introduced the Balanced Allocations framework, also known as the power of two choices paradigm, an elegant theoretical work that has had a widespread practical impact, are the latest winners of the ACM Paris Kanellakis Theory and Practice Award.

The ACM Paris Kanellakis Theory and Practice Award is one of four technical awards administered by the ACM technical awards in which recipients are selected by their peers. Endowed by contributions from the Kanellakis family, with additional financial support provided by several of the ACM's Special Interest Groups this award, accompanied by a prize of $10,000, honors specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing. 

The award itself honors the Greek American computer scientist,  Paris Christos Kanellakis who died in the in the crash of American Airlines Flight 965 in 1995 at the age of 42.

The most recent award (2020) went to five recipients,  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, Brown University, with the citation:

For the discovery and analysis of balanced allocations, known as the power of two choices, and their extensive applications to practice.

The background to the breakthrough made by these recipients is that:

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

In a paper with the title Balanced Allocations presented at the 1994 Symposium of Theory of Computing (sponsored by SIGACT) Azar, Broder, Karlin, and Upfal  made a significant advance:

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

Mitzenmacher, who had worked with Andrei Broder during a summer internship at Digital Systems Research Center to which both Broder and Karlin were affiliated, contributed to this work with his PhD thesis The Power of Two Choices in Randomized Load Balancing presented at UC Berkley in 1996. According to ACM:

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.

Explaining the everyday relevance of this body of work, the ACM  continues:

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.

Mitzenmacher and Upfal subsequently co-authored Probability and Computing: Randomized Algorithms (2005).

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:0521835402>