Brown professor wins prestigious computing award named for his late predecessor

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.

The concept turns out to be incredibly important for routing computing tasks to servers in large data centers. To search for the least busy processor for each incoming task — hundreds of thousands each second — would be far too time consuming for large data centers. So the power of two choices paradigm is widely used to route incoming tasks and keep data centers running as efficiently as possible.

“It’s a really nice compromise,” Upfal said. “You add one small processing step to incoming data — choosing the best of two randomly selected options — and the outcome is nearly the same as searching all of the processors for the best option.”

Upfal, along with colleagues Yossi Azar of Tel Aviv University, Andrei Broder of Google Research and Anna Karlin of the University of Washington, published the first research paper outlining the concept in 1994. Many more studies followed, and the concept is now widely used in data processing, data storage and other areas.

Upfal says he’s thrilled to see a theoretical exercise turn into something so widely applicable.

“This is something that started as pure theory — pure mathematics,” Upfal said. “We ended up with these elegant results, but we assumed this would just stay in the realm of obscure theory. But right around the time we were doing this work, computing was really scaling up dramatically. Suddenly there was a need for processing, storing and routing vast amounts of data, and our theory turned out to be important in solving that problem.”

And in winning a prestigious ACM award, Upfal also helped the Brown community to remember a much beloved and greatly missed former professor.