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.
Dr. Broder received his B.Sc. Summa cum Laude from the Technion in 1977, then completed his Ph.D. at Stanford University under Professor Donald Knuth. In 2014 the Technion awarded him a Ph.D. Honoris Causa “In recognition of pioneering contributions to the development of the World Wide Web.” After working at Compaq, AltaVista, Yahoo!, and IBM, he is now a Distinguished Scientist at Google.
Dr. Broder is the first scientist to receive the ACM Paris Kanellakis Theory and Practice Award twice: he was also honored in 2012 for his work on min-hashing and min-hashing and document similarity.