PROVIDENCE, R.I. [Brown University] — The Paris Kanellakis Theory and Practice Award given by the Association for Computing Machinery (ACM) is one of the most prestigious awards in theoretical computing — and it’s named for a renowned Brown University professor who was killed in a tragic airplane crash in 1995.
This year, the award comes home to Brown.
In May, the ACM named Brown Professor of Computer Science Eli Upfal a recipient of this year’s award. Upfal and four colleagues were honored for their foundational work in developing what’s known as the balanced allocations framework, a concept that among other applications helps data centers rapidly process billions of web requests distributed across millions of servers.
Upfal, who joined the Brown faculty shortly after Kanellakis’ death, said winning an award bearing his predecessor’s name is especially gratifying.
“When I came to the department, people were still shaken by his loss,” Upfal said. “He was a much beloved and admired teacher and colleague, and so it’s a great honor to bring an award back to Brown that’s very prestigious and that’s named for Paris.”
The work for which Upfal and his colleagues were honored is often referred to as the “power of two choices” paradigm. One way to think about the idea is to imagine shopping at the world’s largest grocery store — one so big that there are hundreds of checkout lines. You want to pick the shortest line, but checking all of them to see which is the shortest would take a while, and the number of people in each line would change while you’re checking. One option might be to simply pick one line at random and live with that choice. But the power-of-two-choices idea shows there’s a vastly better way.
Instead of choosing one line at random, customers should choose two lines at random, compare them and then select the shorter of the two. Upfal and his colleagues proved mathematically that if all customers chose the shorter of two randomly selected lines, the average wait time would be exponentially shorter than if customers chose just one line at random. In fact, choosing the shortest of two lines is nearly as good as choosing the shortest of all the lines — and it saves the time of having to check each line.