PODC Archives

ACM PODC Participants List


Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Reply To:
Thu, 25 Oct 2012 01:43:54 -0400
text/plain (41 lines)
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.


To unsubscribe from the PODC list:
write to: mailto:[log in to unmask]
or click the following link: