The 2013 Principles of Distributed Computing Doctoral Dissertation Award

The abundance of excellent candidates made the choice very difficult. Even after narrowing the list down, the committee still decided to split the award between two winners, listed next alphabetically by last name.  Dr. Shiri Chechik completed her thesis ``Fault-tolerant structures in graphs'' in 2012 under the supervision of Prof. David Peleg at the Weizmann Institute of Science. Dr. Danupon Nanongkai completed his thesis ``Graphs and geometric algorithms on distributed networks and databases'' in 2011 under the supervision of Prof. Richard J. Lipton at the Georgia Institute of Technology.

The thesis of Dr. Chechik includes a comprehensive and deep body of work on fault-tolerant graph spanners and related structures. It contains many strong results, one of which received a best student paper award, and one solved a long-standing open problems. In one of these results, Dr. Chechik shows that it is possible to compute, ahead of time, a compact routing table that provides good routes even if several edges fail. The thesis targets an area of research that has been well studied, but Dr. Chechik's contributions advances the area significantly and promises to have a deep and long-lasting impact.

The thesis of Dr. Nanongkai shows a useful approach to make communication complexity a powerful tool for establishing lower bounds bounds for distributed computing. It also contains several sophisticated almost matching upper bounds. The thesis shows that this tool is applicable in diverse contexts, such as random walks, graph problems, and more. Besides being technically deep, the thesis combines distributed computing, communication complexity, and theory of random walks, in natural and novel ways. These results suggest and open the path for much exciting follow-up work on distributed communication complexity and distributed random walks.

The award is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). This award is presented annually, with the presentation taking place alternately at PODC and DISC. This year it was presented at DISC.


Principles of Distributed Computing Doctoral Dissertation Award Committee, 2013:

Marcos K. Aguilera,       Microsoft Research
Rachid Guerraoui,          EPFL
Shay Kutten (Chair),      Technion
Michael Mitzenmacher,  Harvard
Alessandro Panconesi.  Sapienza