Edsger W. Dijkstra Prize in Distributed Computing – ACM Symposium on Principles of Distributed Computing (original) (raw)
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 primitives (such as the semaphore), concurrency problems (such as mutual exclusion and deadlock), reasoning about concurrent systems, and self-stabilization 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 have 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 PODC and 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 PODC and DISC proceedings of that year, describing the paper’s lasting contributions.
Prize-winning papers
- 2024 citation
- Nicola Santoro and Peter Widmayer for “Time is Not a Healer” in Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science, pages 304–313, 1989.
- 2023 citation
- Michael Ben-Or, Shafi Goldwasser and Avi Wigderson for “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation” in Proceedings of the 20th ACM Symposium on Theory of Computing (STOC), Chicago, Illinois, USA, May 1988, pages 1-10.
- David Chaum, Claude Crépeau and Ivan Damgård for “Multiparty Unconditionally Secure Protocols” in Proceedings of the 20th ACM Symposium on Theory of Computing (STOC), Chicago, Illinois, USA, May 1988, pages 11-19.
- Tal Rabin and Michael Ben-Or for “Verifiable Secret Sharing and Multiparty Protocols with Honest Majority” in Proceedings of the 21st ACM Symposium on Theory of Computing (STOC), Seattle, Washington, USA, May 1989, pages 73-85.
- 2022 citation
- Maged M. Michael for “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes” in Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), Monterey, CA, USA, July 2002, pages 21–30.
- Maurice Herlihy, Victor Luchangco, and Mark Moir for “The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures” in Proceedings of the 16th International Symposium on Distributed Computing (DISC), Toulouse, France, October
2002, pages 339–353.
- 2021 citation
- Paris C. Kanellakis and Scott A. Smolka for “CCS Expressions, Finite State Processes, and Three Problems of Equivalence” in Information and Computation, Volume 86, Issue 1, pages 43–68, 1990.
- 2020 citation
- Dana Angluin, James Aspnes, Zoe Diamadi, Michael J. Fischer, and Rene Peralta for “Computation in networks of passively mobile finite-state sensors” in Distributed Computing 18(4): 235-253 (2006).
- 2019 citation
- Alessandro Panconesi and Aravind Srinivasan for “Randomized Distributed Edge Coloring via an Extension of the Chernoff–Hoeffding Bounds” in SIAM Journal on Computing, volume 26, number 2, 1997, pages 350–368.
- 2018 citation
- Bowen Alpern and Fred B. Schneider for “Defining liveness” in Information Processing Letters 21(4), October 1985, pages 181-185.
- 2017 citation
- Elizabeth Borowsky and Eli Gafni for “Generalized FLP impossibility result for t-resilient asynchronous computations” in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC 93), pages 91-100, May 1993.
- 2016 citation
- Noga Alon, László Babai, and Alon Itai for “A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem” in Journal of Algorithms, 7(4):567-583, 1986.
- Michael Luby for “Simple Parallel Algorithm for the Maximal Independent Set Problem” 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.
- 2015 citation
- Michael Ben-Or for “Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols” in Proceedings of the Second ACM Symposium on Principles of Distributed Computing, pages 27-30, August 1983.
- Michael O. Rabin for “Randomized Byzantine Generals” in Proceedings of Twenty-Fourth IEEE Annual Symposium on Foundations of Computer Science, pages 403-409, November 1983.
- 2014 citation
- Kanianthra Mani Chandy and Leslie Lamport for “Distributed Snapshots: Determining Global States of Distributed Systems” in ACM Transactions on Computer Systems, 3(1):63–75, 1985.
- 2013 citation
- Nati Linial for “Locality in Distributed Graph Algorithms” in SIAM Journal on Computing, 21(1):193-201, 1992.
- 2012 citation
- Maurice Herlihy and J. Eliot B. Moss for “Transactional Memory: Architectural Support for Lock-Free Data Structures” in Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 289-300, May 1993.
- Nir Shavit and Dan Touitou for “Software Transactional Memory” in Distributed Computing, 10(2):99-116, February 1997. (An earlier version appeared in the Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, pages 204-213, August 1995.)
- 2011 citation
- Hagit Attiya, Amotz Bar-Noy, and Danny Dolev for “Sharing Memory Robustly in Message-Passing Systems” in Journal of the ACM, 42(1):124-142, 1995.
- 2010 citation
- Tushar D. Chandra and Sam Toueg for “Unreliable Failure Detectors for Reliable Distributed Systems” in Journal of the ACM, 43(2):225-267, 1996.
- Tushar D. Chandra, Vassos Hadzilacos, and Sam Toueg for “The Weakest Failure Detector for Solving Consensus” in Journal of the ACM, 43(4):685-722, 1996.
- 2009 citation
- Joseph Halpern and Yoram Moses for “Knowledge and Common Knowledge in a Distributed Environment” in the Journal of the ACM, 37(3):549-587, July 1990.
- 2008 citation
- Baruch Awerbuch and David Peleg for “Sparse Partitions” in Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS), 503-513, October 1990.
- 2007 citation
- Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer for “Consensus in the presence of partial synchrony” in Journal of the ACM, 35(2):288-323, April 1988.
- 2006 citation
- John M. Mellor-Crummey and Michael L. Scott for “Algorithms for scalable synchronization on shared-memory multiprocessors” in ACM Transactions on Computer Systems, 9(1):21-65, February 1991.
- 2005 citation
- Marshall Pease, Robert Shostak, and Leslie Lamport for “Reaching agreement in the presence of faults” in Journal of the ACM, 27(1):228-234, April 1980.
- 2004 citation
- R. G. Gallager, P. A. Humblet, and P. M. Spira for “A Distributed Algorithm for Minimum-Weight Spanning Trees” in ACM Transactions on Programming Languages and Systems, 5(1):66-77, January 1983.
- 2003 citation
- Maurice Herlihy for “Wait-Free Synchronization” in ACM Transactions on Programming Languages and Systems, 13(1):124-149, January 1991.
- 2002 citation*
- Edsger W. Dijkstra for “Self-stabilizing systems in spite of distributed control” in Communications of the ACM, 17(11):643-644, November 1974.
- 2001 citation*
- Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson for “Impossibility of Distributed Consensus with One Faulty Process” in Journal of the ACM, 32(2):374-382, April 1985.
- 2000 citation*
- Leslie Lamport for “Time, Clocks, and the Ordering of Events in a Distributed System” in Communications of the ACM, 21(7):558-565, July 1978.
*The “Dijkstra Prize” was awarded under the name “PODC Influential-Paper Award” in the years 2000, 2001, and 2002.
Award committee
The winner of the Prize is selected by a committee of six members. The Award Committee will consist of the current PODC and DISC program chairs, the PODC program chairs from five and ten years ago, and the DISC program chairs from five and ten years ago. The Award Committee will be chaired alternately by the current PODC and DISC program chairs.
If the resulting committee consists of less than six distinct members (because one of the specified program chairs is unable to serve on the committee or because a single person has served in the role of more than one of the specified program chairs), then the committee chair will nominate a replacement of similar stature for the approval of the PODC and DISC steering committees. The PODC and DISC steering committees shall be the final authority on the membership of the awards committee.
Nominations and eligibility
At least four months prior to each year’s PODC or DISC (whichever comes earlier), a Call for Nominations will be posted on the PODC and DISC mailing lists. Nominations may be made by any member of the scientific community. Each nomination must identify the paper being nominated and include a short paragraph (approximately 200 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 can nominate papers as well. However, they must carefully consider nominations from within the community. Members of the Award Committee should be especially sensitive to conflict-of-interests issues if papers by former students or close colleagues are nominated (members of the Award Committee cannot nominate such papers themselves).
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.