Dijkstra Prize
Year Paper Topic
2000 Lamport , L. ( 1978 ) . Time , clocks , and the ordering of events in a distributed system ( PDF ) . Communications of the ACM . 21 ( 7 ) : 558-565. doi : 10.1145/359545.359563 . .mw-parser-output cite.citation { font-style : inherit } .mw-parser-output .citation q { quotes : \\ '' } .mw-parser-output .id-lock-free a , .mw-parser-output .citation .cs1-lock-free a { background-image : url ( //upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png ) ; background-image : linear-gradient ( transparent , transparent ) , url ( //upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg ) ; background-repeat : no-repeat ; background-size:9px ; background-position : right .1em center } .mw-parser-output .id-lock-limited a , .mw-parser-output .id-lock-registration a , .mw-parser-output .citation .cs1-lock-limited a , .mw-parser-output .citation .cs1-lock-registration a { background-image : url ( //upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png ) ; background-image : linear-gradient ( transparent , transparent ) , url ( //upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg ) ; background-repeat : no-repeat ; background-size:9px ; background-position : right .1em center } .mw-parser-output .id-lock-subscription a , .mw-parser-output .citation .cs1-lock-subscription a { background-image : url ( //upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png ) ; background-image : linear-gradient ( transparent , transparent ) , url ( //upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg ) ; background-repeat : no-repeat ; background-size:9px ; background-position : right .1em center } .mw-parser-output .cs1-subscription , .mw-parser-output .cs1-registration { color : # 555 } .mw-parser-output .cs1-subscription span , .mw-parser-output .cs1-registration span { border-bottom:1px dotted ; cursor : help } .mw-parser-output .cs1-ws-icon a { background-image : url ( //upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png ) ; background-image : linear-gradient ( transparent , transparent ) , url ( //upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg ) ; background-repeat : no-repeat ; background-size:12px ; background-position : right .1em center } .mw-parser-output code.cs1-code { color : inherit ; background : inherit ; border : inherit ; padding : inherit } .mw-parser-output .cs1-hidden-error { display : none ; font-size:100% } .mw-parser-output .cs1-visible-error { font-size:100% } .mw-parser-output .cs1-maint { display : none ; color : # 33aa33 ; margin-left:0.3em } .mw-parser-output .cs1-subscription , .mw-parser-output .cs1-registration , .mw-parser-output .cs1-format { font-size:95% } .mw-parser-output .cs1-kern-left , .mw-parser-output .cs1-kern-wl-left { padding-left:0.2em } .mw-parser-output .cs1-kern-right , .mw-parser-output .cs1-kern-wl-right { padding-right:0.2em } .mw-parser-output .citation .mw-selflink { font-weight : inherit } ll
2001 Fischer , M. J. ; Lynch , N. A. ; Paterson , M. S. ( 1985 ) . Impossibility of distributed consensus with one faulty process ( PDF ) . Journal of the ACM . 32 ( 2 ) : 374-382. doi : 10.1145/3149.214121 . Archived from the original ( PDF ) on 2007-07-05 Proving the impossibility of consensus using asynchronous communication
2002 Dijkstra , E. W. ( November 1974 ) . Self-stabilizing systems in spite of distributed control . Communications of the ACM . 17 ( 11 ) : 643-644. doi : 10.1145/361179.361202 Self-stabilization
2003 Herlihy , M. ( 1991 ) . Wait-free synchronization . ACM Transactions on Programming Languages and Systems . 13 ( 1 ) : 124-149 . CiteSeerX 10.1.1.56.5659 . doi : 10.1145/114005.102808 . Maurice Herlihy Solvability and universality of consensus in shared-memory systems
2004 Gallager , R. G. ; Humblet , P. A. ; Spira , P. 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 Distributed algorithm to find a minimum spanning tree
2005 Pease , M. ; Shostak , R. ; Lamport , L. ( April 1980 ) . Reaching Agreement in the Presence of Faults . Journal of the ACM . 27 ( 2 ) : 228-234 . CiteSeerX 10.1.1.68.4044 . doi : 10.1145/322186.322188 Byzantine agreement
2006 Mellor-Crummey , J. M. ; Scott , M. L. ( 1991 ) . Algorithms for scalable synchronization on shared-memory multiprocessors . ACM Transactions on Computer Systems . 9 ( 1 ) : 21-65 . CiteSeerX 10.1.1.228.3461 . doi : 10.1145/103727.103729 probably the most influential practical mutual exclusion algorithm of all time
2007 Dwork , C. ; Lynch , N. ; Stockmeyer , L. ( 1988 ) . Consensus in the presence of partial synchrony . Journal of the ACM . 35 ( 2 ) : 288-323 . CiteSeerX 10.1.1.13.3423 . doi : 10.1145/42282.42283 Solving consensus in partially synchronous systems
2008 Awerbuch , B. ; Peleg , D. ( 1990 ) . Sparse partitions . Proceedings [ 1990 ] 31st Annual Symposium on Foundations of Computer Science . pp . 503-513. doi : 10.1109/FSCS.1990.89571 . ISBN 978-0-8186-2082-9 Sparse partitions
2009 Halpern , J. Y. ; Moses , Y . ( 1990 ) . Knowledge and Common Knowledge in a Distributed Environment . Journal of the ACM . 37 ( 3 ) : 549-587. arXiv : cs/0006009 . doi : 10.1145/79147.79161 A formal framework for reasoning about knowledge in distributed systems
2010 Chandra , T. D. ; Toueg , S. ( 1996 ) . Unreliable Failure Detectors for Reliable Distributed Systems . Journal of the ACM . 43 ( 2 ) : 225-267. doi : 10.1145/226643.226647 . hdl : 1813/7192 . Chandra , T. D. ; Hadzilacos , V. ; Toueg , S. ( 1996 ) . The Weakest Failure Detector for Solving Consensus . Journal of the ACM . 43 ( 4 ) : 685-722 . CiteSeerX 10.1.1.55.8585 . doi : 10.1145/234533.234549 Failure detectors
2011 Attiya , H. ; Bar-Noy , A. ; Dolev , D. ( 1995 ) . Sharing Memory Robustly in Message-Passing Systems . Journal of the ACM . 42 ( 1 ) : 124-142. doi : 10.1145/200836.200869 Simulating shared memory in fault-prone message-passing systems
2012 Herlihy , M. ; Moss , J. E. B . ( 1993 ) . Transactional memory . ACM SIGARCH Computer Architecture News . 21 ( 2 ) : 289-300. doi : 10.1145/173682.165164 . Shavit , N. ; Touitou , D. ( 1997 ) . Software transactional memory . Distributed Computing . 10 ( 2 ) : 99-116 . CiteSeerX 10.1.1.468.7173 . doi : 10.1007/s004460050028 Transactional memory
2013 Linial , N. ( 1992 ) . Locality in Distributed Graph Algorithms . SIAM Journal on Computing . 21 : 193-201 . CiteSeerX 10.1.1.711.689 . doi : 10.1137/0221015 Locality in distributed graph algorithms
2014 Chandy , K. M. ; Lamport , L. ( 1985 ) . Distributed snapshots : Determining global states of distributed systems . ACM Transactions on Computer Systems . 3 : 63-75 . CiteSeerX 10.1.1.69.2561 . doi : 10.1145/214451.214456 The Chandy-Lamport algorithm to get a consistent picture of the global state of a system
2015 Ben-Or , M. ( 1983 ) . Another Advantage of Free Choice : Completely Asynchronous Agreement Protocols . Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing - PODC '83 . pp . 27-30. doi : 10.1145/800221.806707 . ISBN 978-0897911108 . Rabin , M. O . ( 1983 ) . Randomized byzantine generals . 24th Annual Symposium on Foundations of Computer Science ( FOCS 1983 ) . pp . 403-409. doi : 10.1109/SFCS.1983.48 . ISBN 978-0-8186-0508-6 Fault-tolerant randomized distributed algorithms
2016 Alon , Noga ; Babai , László ; Itai , Alon ( 1986 ) . A fast and simple randomized parallel algorithm for the maximal independent set problem . Journal of Algorithms . 7 ( 4 ) : 567. doi : 10.1016/0196-6774 ( 86 ) 90019-2 . and Luby , Michael ( 1986 ) . A Simple Parallel Algorithm for the Maximal Independent Set Problem . SIAM Journal on Computing . 15 ( 4 ) : 1036-1053 . CiteSeerX 10.1.1.225.5475 . doi : 10.1137/0215074 Algorithms for finding a maximal independent set
2017 Borowsky , Elizabeth ; Gafni , Eli ( 1993 ) . Generalized FLP impossibility result for t-resilient asynchronous computations . P 25th Annual ACM Symposium on Theory of Computing . ACM . pp . 91-100 The BG Simulation Algorithm , which allows a set of processes to simulate a larger set of processes in a coordinated way
2018 Alpern , Bowen ; Schneider , Fred B . ( 1985 ) . Defining liveness . Information Processing Letters Volume 21 , Issue 4 . pp . 181-185 Formal definition of liveness property
2019 Panconesi , A. ; Srinivasan , A . ( 1997 ) . Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds . SIAM Journal on Computing . 26 ( 2 ) : 350-368. doi : 10.1137/S0097539793250767 . hdl : 1813/6127 Distributed edge coloring
Winners
The Edsger W. Dijkstra Paper 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 paper prize has been presented annually since 2000. Originally the paper 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, the paper 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 paper prize includes an award of $2000.