Dijkstra Prize

The Edsger W. Dijkstra Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade. The prize has been presented annually since 2000.

Originally the prize was presented at the ACM Symposium on Principles of Distributed Computing (PODC), and it was known as the PODC Influential-Paper Award. It was renamed in honor of Edsger W. Dijkstra in 2003, after he received the award for his work in self-stabilization in 2002 and died shortly thereafter.

Since 2007,^[1] the prize is sponsored jointly by PODC and the EATCS International Symposium on Distributed Computing (DISC), and the presentation takes place alternately at PODC (even years) and DISC (odd years). The prize includes an award of $2000.

Winners

• 2000 - Leslie Lamport for his paper on logical clocks.
• 2001 - Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson for proving the impossibility of consensus using asynchronous communication.
• 2002 - Edsger W. Dijkstra for his paper that introduced self-stabilization.
• 2003 - Maurice Herlihy for his paper on the solvability and universality of consensus in shared-memory systems.
• 2004 - Robert G. Gallager, Pierre A. Humblet, Philip M. Spira for their distributed algorithm to find a minimum spanning tree.^[2]
• 2005 - Marshall Pease, Robert Shostak, Leslie Lamport for their paper on Byzantine agreement.
• 2006 - John M. Mellor-Crummey, Michael L. Scott for their mutual exclusion algorithm.
• 2007 - Cynthia Dwork, Nancy A. Lynch, Larry Stockmeyer for their paper on solving consensus in partially synchronous systems.^[3]
• 2008 - Baruch Awerbuch, David Peleg for their paper on sparse partitions.^[4]
• 2009 - Joseph Halpern and Yoram Moses for their paper that provides a formal framework for reasoning about knowledge in distributed systems.^[5]

See also

• List of important publications in concurrent, parallel, and distributed computing

Notes

1. ^ Calls for nominations: 2005, 2006. DISC 2007 proceedings and web site.
2. ^ Gallager, Robert G.; Humblet, Pierre A.; Spira, Philip M. (1983), "A distributed algorithm for minimum-weight spanning trees", ACM Transactions on Programming Languages and Systems 5 (1): 66–77, doi:10.1145/357195.357200 .
3. ^ Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (1988), "Consensus in the presence of partial synchrony", Journal of the ACM 35 (2): 288–323, doi:10.1145/42282.42283 .
4. ^ Awerbuch, Baruch; Peleg, David (1990), "Sparse partitions", Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS 1990), pp. 503–513, doi:10.1109/FSCS.1990.89571 .
5. ^ Halpern, Joseph; Moses, Yoram (1990), "Knowledge and Common Knowledge in a Distributed Environment", Journal of the ACM 37 (3): 549–587, doi:10.1145/79147.79161 .

References

• EATCS web site: Awards: Dijkstra Prize.
• PODC web site: Edsger W. Dijkstra Prize in Distributed Computing.
• DISC web site: Edsger W. Dijkstra Prize in Distributed Computing.