On Wednesday, October 17, 2012, the first Principles of Distributed Computing Doctoral Dissertation Award was given to Dr. Keren Censor-Hillel for her 2010 thesis “Probabilistic Methods in Distributed Computing”, supervised by Professor Hagit Attiya at the Technion, Israel. The main contribution of her thesis is proving that the total step complexity of asynchronous randomized consensus for n processes is a quadratic function of n, solving a longstanding open problem. This result involved developing and analyzing a new shared coin algorithm that improved the previously best randomized consensus algorithm and creating a randomized valency technique that improved the lower bound. Another very interesting result in her thesis is the implementation of a counter with polylogarithmic individual step complexity, which she uses to derive a randomized consensus algorithm with linear individual step complexity. The thesis also contains a number of other related results, including the first randomized k-set agreement algorithm. As the nomination letter said, “The thesis has changed the way randomization is applied and analyzed in distributed computing, especially in the context of the consensus problem”. The work in Keren’s thesis has been presented in six conference papers: three at PODC and one at each of SODA, SPAA, and STOC. It has also led to five journal papers, including two in JACM and one in SICOMP. Her thesis is coherent and well organized. It is exceptionally well written, with clear explanations of technically sophisticated proofs.
Seventeen very strong theses were nominated for the award. The award committee consisted of Professor Faith Ellen (chair), Professor Pierre Fraigniaud, Professor Maurice Herlihy, Professor Friedhelm Meyer auf der Heide, Professor David Peleg, and Professor Sergio Rajsbaum. Dr. Tushar Chandra was a consultant to the committee.
