Technion Alumnus Wins Prestigious Prize from the Association for Computing Machinery

Pictured above: Technion alumnus Dr. Andrei Broder

Technion alumnus Andrei Broder was recently awarded the Paris Kanellakis Theory and Practice Award by the Association for Computing Machinery (ACM). The peer-selected award honors specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing.

Dr. Broder, along with his colleagues Yossi Azar, Anna Karlin, Michael Mitzenmacher, and Eli Upfal, were recognized for their Balanced Allocations framework, also known as the power of two choices, and their extensive applications to practice.

By way of illustrating the Balanced Allocations framework, imagine you and a few friends are tossing hundreds of tennis balls into hundreds of bins. You want to make sure that no bin gets too full – but while you try to assess which bins are less empty, they’re constantly getting new tennis balls added to them.

Frustrated, you might be tempted just to toss the tennis ball into a bin at random. But the Balanced Allocations framework proves there’s a better way. Instead of choosing a bin at random, you should just choose two of the bins at random and toss your tennis ball into the bin that is less full. It turns out that choosing the emptier of two bins is nearly as good as choosing the most empty bin, and it takes much less time.

The power of two choices is an incredibly useful framework for large data centers. Rather than spending precious time searching for the least busy computer processor for each incoming task, computer scientists can apply this framework and keep data centers running efficiently without any centralized load-balancing decision making.