Dijkstra Prize

The Edsger W. Dijkstra Prize in Distributed Computing is named for Edsger Wybe Dijkstra (1930-2002), a pioneer in the area of distributed computing. His foundational work on concurrency, semaphores, mutual exclusion, deadlock, finding shortest paths in graphs, fault-tolerance, self-stabilization, among many other contributions comprises one of the most important supports upon which the field of distributed computing is built. No other individual has had a larger influence on research in principles of distributed computing.

The prize 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 includes an award of $2000.

The Prize 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 ACM PODC and EATCS DISC.

The winners of the award will share the cash award, and each winning author will be presented with a plaque. An announcement of each year's prize recipient(s) will be included in the ACM PODC or EATCS DISC proceedings of that year, describing the paper's lasting contributions.

Award Committee:

The winner of the Prize is selected by a committee of six members.

Award Committee 2017:


Marcos K. Aguilera                 VMware Research, USA
Alessandro Panconesi           University of Rome Sapienza, Italy
Andrzej Pelc                           Université du Québec en Outaouais, Canada
Andrea Richa                          Arizona State University, USA
Alex Schwarzmann, Chair      University of Connecticut, USA
Roger Wattenhofer                 ETH Zurich, Switzerland

Nominations and Eligibility

Nominations may be made by any member of the scientific community. Each nomination must identify the paper being nominated and include a few paragraphs (approximately 400 words) justifying the nomination. Papers appearing in any conference proceedings or journal are eligible, as long as they have had a significant impact on research areas of interest within the theory of distributed computing community, and as long as the year of the original publication is at least ten years prior to the year in which the award is given.

Papers authored or co-authored by members of the Award Committee will not be eligible for consideration. Members of the Award Committee will be especially sensitive to conflict-of-interests issues if papers by former students or close colleagues are nominated.

Selection Process

Although the Award Committee is encouraged to consult with the distributed computing community at large, the Award Committee is solely responsible for the selection of the winner of the award. The prize may be shared by more than one paper. All matters relating to the selection process that are not specified here are left to the discretion of the Award Committee.

Past Prizes

Prizes in the years 2000-2002 were given under the name "PODC Influential-Paper Award".

2017 / Elizabeth Borowsky, Eli Gafni

Paper: "Generalized FLP impossibility result for t-resilient asynchronous computations", by Elizabeth Borowsky and Eli Gafni,  STOC 1993: 91-100.

Committee:  Marcos K. Aguilera, Alessandro Panconesi, Andrzej Pelc , Andrea Richa, Alex Schwarzmann (Chair) , Roger Wattenhofer

2016 / Noga Alon, László Babai, Alon Itai, Michael Luby

Paper: "A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem", by Noga Alon, László Babai, and Alon Itai by in Journal of Algorithms, 7(4):567-583, 1986.
Paper: "Simple Parallel Algorithm for the Maximal Independent Set Problem", by Michael Luby in the Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 1-10, May 1985, and in SIAM Journal on Computing, 15(4):1036-1053, 1986.

Committee: Shlomi Dolev, Pierre Fraigniaud, Cyril Gavoille, Dahlia Malkhi, Andrzej Pelc, David Peleg

2015 / Michael Ben-Or, Michael O. Rabin

Paper: "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols", by Michael Ben-Or, published in Proceedings of the Second ACM Symposium on Principles of Distributed Computing, pages 27-30, August 1983
Paper: "Randomized Byzantine Generals", by Michael O. Rabin, published in Proceedings of Twenty-Fourth IEEE Annual Symposium on Foundations of Computer Science, pages 403-409, November 1983

Committee: James Aspnes, Pierre Fraigniaud, Rachid Guerraoui, Nancy Lynch, Yoram Moses, Paul Spirakis (Chair)

2014 / Kanianthra Mani Chandy, Leslie Lamport

Paper: 'Distributed Snapshots: Determining Global States of Distributed SystemsACM Transactions on Computer Systems, 3(1):63–75, 1985.

Committee: Lorenzo Alvisi, Shlomi Dolev, Rachid Guerraoui, Idit Keidar, Fabian Kuhn (Chair), Shay Kutten

2013 / Nati Linial

Paper: ''Locality in Distributed Graph Algorithms". SIAM Journal on Computing, 21(1):193-201, 1992

Committee: Yehuda Afek, Faith Ellen, Boaz Patt-Shamir, Sergio Rajsbaum, Alexander Shvartsman, Gadi Taubenfeld (Chair)

2012 / Maurice Herlihy, J. Eliot B. Moss, Nir Shavit, Dan Touitou

Paper: ''Transactional Memory: Architectural Support for Lock-Free Data Structures". 20th Annual International Symposium on Computer Architecture, pages 289-300, May 1993. and Software Transactional Memory Distributed Computing 10(2):99-116, February 1997. (An earlier version appearing in the 14th ACM Symposium on Principles of Distributed Computing, pages 204-213, August 1995.)

Committee: Marcos K. Aguilera (Chair), Dahlia Malkhi, Keith Marzullo, Alessandro Panconesi, Andrzej Pelc, and Roger Wattenhofer

2011 / Hagit Attiya, Amotz Bar-Noy, Danny Dolev

Paper: ''Sharing Memory Robustly in Message-Passing Systems'', Journal of the ACM,(JACM) 42(1):124-142 (1995)

Committee: Shlomi Dolev, Pierre Fraigniaud (Chair), Dahlia Malkhi, David Peleg, Nir Shavit, Jennifer Welch

2010 / Tushar D. Chandra, Vassos Hadzilacos, Sam Toueg

Papers: ''Unreliable Failure Detectors for Reliable Distributed Systems'', Journal of the ACM, 43(2):225-267, 1996 and ''The Weakest Failure Detector for Solving Consensus'', Journal of the ACM, 43(4):685-722, 1996

Committee: Nancy Lynch(Co-Chair), Alexander Shvartsman(Co-Chair), James Anderson, James Aspens, Pierre Fraigniaud, Rachid Guerraoui, Maurice Herlihy

2009 / Joseph Halpern, Yoram Moses

Paper: "Knowledge and Common Knowledge in a Distributed Environment", published in Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (PODC'84) pp. 50-61, 1984 (pdf), and in Journal of the ACM (JACM), 37(3):549-587, 1990 (pdf)

Committee: Lorenzo Alvisi (Chair), Rachid Guerraoui, Prasad Jayanti, Idit Keidar, Shay Kutten, Jennifer Welch

2008 / Baruch Awerbuch, David Peleg

Paper: "Sparse Partitions" published in FOCS 1990.

Committee: Yehuda Afek, Faith Ellen, Shay Kutten, Boaz Patt-Shamir, Sergio Rajsbaum, Gadi Taubenfeld (Chair)

2007/ Cynthia Dwork, Nancy Lynch, Larry Stockmeyer

Paper: "Consensus in the presence of partial synchrony", Journal of the ACM, Vol. 35, No. 2, April, 1988. pages 288--323 (a preliminary version appeared in PODC 1984).

Committee: Hagit Attiya, Dahlia Malkhi, Keith Marzullo, Marios Mavronicolas, Andrzej Pelc, Roger Wattenhofer (Chair)

2006 / John M. Mellor-Crummey, Michael L. Scott

Paper: "Algorithms for scalable synchronization on shared-memory multiprocessors", ACM Transactions on Computer Systems, 9(1), 1991

Committee: Dahlia Malkhi (Chair), Yoram Moses, Michel Raynal, Nir Shavit

2005 / Marshal Pease, Robert Shostak, Leslie Lamport

Paper: "Reaching agreement in the presence of faults", Journal of the Association of Computing Machinery, April, 1980, 27(1):228-234

2004 / R. G. Gallager, P. A. Humblet, P. M. Spira

Paper: "A Distributed Algorithm for Minimum-Weight Spanning Trees", ACM Transactions on Programming Languages and Systems, January 1983, 5(1):66-77

Committee: Shay Kutten (Chair), David Peleg, George Varghese, and Jennifer Welch

2003 / Maurice Herlihy

Paper: "Wait-Free Synchronization", ACM Transactions on Programming Languages and Systems, January 1991, 13(1):124-149

Committee: Yehuda Afek, Michael Merritt, Sergio Rajsbaum (chair), and Sam Toueg

2002 / Edsger W. Dijkstra

Paper: "Self-stabilizing systems in spite of distributed control", Communications of the ACM, 1974, 17(11):643-644

2001 / Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson

Paper: "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM, April 1985, 32(2):374-382

2000 / Leslie Lamport

Paper: "Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM, July 1978, 21(7):558-565

e-max.it: your social media marketing partner
 
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.