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
| Year | Paper | Topic |
|---|---|---|
| 2000[2] | 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. | Lamport logical clock |
| 2001[3] | 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. | 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[4] | Herlihy, M. (1991). "Wait-free synchronization". ACM Transactions on Programming Languages and Systems. 13 (1): 124–149. doi:10.1145/114005.102808. Maurice Herlihy | Solvability and universality of consensus in shared-memory systems |
| 2004[5] | 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[6] | Pease, M.; Shostak, R.; Lamport, L. (April 1980). "Reaching Agreement in the Presence of Faults". Journal of the ACM. 27 (2): 228–234. 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. doi:10.1145/103727.103729. | "probably the most influential practical mutual exclusion algorithm of all time"[7] |
| 2007[8] | Dwork, C.; Lynch, N.; Stockmeyer, L. (1988). "Consensus in the presence of partial synchrony". Journal of the ACM. 35 (2): 288–323. doi:10.1145/42282.42283. | Solving consensus in partially synchronous systems |
| 2008[9] | 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 0-8186-2082-X. | 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. 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. Chandra, T. D.; Hadzilacos, V.; Toueg, S. (1996). "The Weakest Failure Detector for Solving Consensus". Journal of the ACM. 43 (4): 685–722. 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. doi:10.1007/s004460050028. |
Transactional memory |
| 2013 | Linial, N. (1992). "Locality in Distributed Graph Algorithms". SIAM Journal on Computing. 21: 193–201. doi:10.1137/0221015. | Locality in distributed graph algorithms |
| 2014[10] | Chandy, K. M.; Lamport, L. (1985). "Distributed snapshots: Determining global states of distributed systems". ACM Transactions on Computer Systems. 3: 63–75. doi:10.1145/214451.214456. | The Chandy-Lamport algorithm to get a consistent picture of the global state of a system |
| 2015[11] | 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: 27–30. doi:10.1145/800221.806707. ISBN 0897911105. Rabin, M. O. (1983). "Randomized byzantine generals". 24th Annual Symposium on Foundations of Computer Science (sfcs 1983): 403–409. doi:10.1109/SFCS.1983.48. ISBN 0-8186-0508-1. |
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. doi:10.1137/0215074. | Algorithms for finding a maximal independent set |
Funding
The award is financed by ACM PODC and EATCS DISC, each providing an equal share of $1,000 towards the $2,000 of the award.
- The PODC share is financed by an endowment at ACM that is based on gifts from the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), the ACM Special Interest Group on Operating Systems (SIGOPS), the AT&T Corporation, the Hewlett-Packard Company, the International Business Machines (IBM) Corporation, the Intel Corporation, and Sun Microsystems, Inc.
- The DISC share is financed by an endowment at EATCS that is based on contributions from several year's DISC budgets, and gifts from Microsoft Research, the Universidad Rey Juan Carlos and the Spanish Ministry of Science and Innovation.
See also
Notes
- ↑ Calls for nominations: 2005, 2006. DISC 2007 proceedings and web site.
- ↑ "PODC Influential Paper Award: 2000", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- ↑ "PODC Influential Paper Award: 2001", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- ↑ "Edsger W. Dijkstra Prize in Distributed Computing: 2003", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- ↑ "Edsger W. Dijkstra Prize in Distributed Computing: 2004", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- ↑ "Edsger W. Dijkstra Prize in Distributed Computing: 2005", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- ↑ "Edsger W. Dijkstra Prize in Distributed Computing: 2006", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- ↑ "Edsger W. Dijkstra Prize in Distributed Computing: 2007", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- ↑ "Edsger W. Dijkstra Prize in Distributed Computing: 2008", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- ↑ 2014 Edsger W. Dijkstra Prize in Distributed Computing, retrieved 2014-06-17
- ↑ The 2015 Edsger W. Dijkstra Prize in Distributed Computing, retrieved 2015-05-21
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.
This article is issued from Wikipedia - version of the 9/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.