Brown CS News

The Paris C. Kanellakis Memorial Lecture, a tradition of more than two decades, honors a distinguished computer scientist who was an esteemed and beloved member of the Brown CS community. Paris came to Brown in 1981 and became a full professor in 1990. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing, and combinatorial optimization. He died in an airplane crash on December 20, 1995, along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis.

Each year, Brown CS invites one of the field's most prominent scientists to address wide-ranging topics in honor of Paris. Recently, Donald Knuth of Stanford University returned to Brown to give a "history of clever ideas that arose around the world” as he traced the evolution of a combinatorial problem dating back to antiquity. Last week, Eli Upfal, Rush Hawkins Professor of Computer Science at Brown University, delivered the twenty-first annual Paris C. Kanellakis Memorial Lecture: "Balls, Bins and Server Farms". 

In his opening remarks, Department Chair Ugur Çetintemel described Paris as a "great scholar and wonderful human being" whose work was broad as well as deep, with attention to practical concerns and impact. When looking for a computer science thought leader to deliver the Kanellakis Lecture, Ugur explained, Brown CS typically turns outward, but made an exception this year for the first time in two decades by choosing one of our own faculty members.

"Eli is in many ways a successor to Paris," he said, "and his work is diverse and deep." As evidence of this, Ugur cited Upfal's recent receipt of the ACM Paris Kanellakis Theory and Practice Award, one of the very highest honors in theoretical computer science.  

Eli began his talk by saying that although he never met Kanellakis, upon arriving at Brown CS in 1996, he "saw and felt how much Paris was appreciated. His death was a great loss to the department." His lecture, Upfal explained, would continue the idea of theory that makes a different type of impact, not necessarily financial: theory that "eventually percolates out into the world" to leave its mark on practice.

His example was his invention of the balanced allocations framework, also known as the power of two choices paradigm, which can be explained as follows: when n balls are thrown into n bins chosen uniformly at random, it's known with high probability that the maximum load on any bin is bounded by (lg n/lg lg n) (1+o(1)). Eli and his collaborators proved that adding a little bit of choice makes a big difference. When throwing each ball, instead of choosing one bin at random, the thrower should choose two bins at random, then place the ball in the bin with the lesser load. This minor change brings an exponential improvement: now, with high probability, the maximal load in any bin is bounded by (lg lg n/lg 2)+O(1). In the same work, they show that if each ball has d choices, the maximum load drops with high probability to (ln ln n/ ln d)+O(1). 

Eli's lecture traced the progress of his ideas chronologically across three stages: 

• theory (balanced allocations)
• bridge (the power of two choices), and
• applications (the p2c protocol)

Since bins and balls are the basic model for analyzing data structures such as hashing or processes like load balancing of jobs in servers, Eli explained that the power of two choices, which requires only a local decision rather than global coordination, has led to a wide range of practical applications. It took more than a decade, Upfal said, for systems and networking researchers to notice his theories and even longer for companies to implement them, but at present, Google's web index, Akamai’s overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox are all based on variants of the power of two choices paradigm due to their superior load balancing, low overhead, and ease of parallelization.

Brown CS Professor Stephen Bach was one of the event's many attendees. "Eli's lecture was inspiring," Steve said. "He talked about his work studying fundamental, theoretical properties of decision making, which has over decades led to algorithms that play a huge role in modern, distributed computing. When he started, it wasn't clear that it would have such a big impact, but he pursued what he thought was interesting. It's a reminder that great work can have a big effect, even if it's hard to anticipate exactly how."

A recording of the lecture is available here.

For more information, click the link that follows to contact Brown CS Communication and Outreach Specialist Jesse C. Polhemus.