Prix Dijkstra

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 24 janvier 2022 à 05:45 et modifiée en dernier par OrlodrimBot (discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.

Prix Dijkstra
Organisateur ACM et EATCS
Date de création 2000
Site officiel Site de l'EATCS et Site de PODC (ACM)
modifier Consultez la documentation du modèle

Le prix Edsger W. Dijkstra en algorithmique répartie, anciennement prix PoDC de l'article influent, est décerné chaque année, depuis 2000, aux auteurs d'un article dont l'impact est particulièrement important pour la théorie ou la pratique des systèmes distribués depuis au moins dix ans. Remis à l'origine lors de la conférence ACM Principles of Distributed Computing (PoDC), il est, depuis 2007, remis alternativement lors de PoDC les années paires et lors de la conférence EATCS Distributed Computing (DISC) les années impaires, chacune des deux conférences fournissant la moitié de la somme de 2 000 $. Il change de nom en 2003 pour prendre celui de Dijkstra, qui vient de mourir peu après avoir reçu le prix.

Lauréats

Liste des lauréats[1]
Année Nom(s) Article
2000 Leslie Lamport Time, Clocks, and the Ordering of Events in a Distributed System[2]
2001 Michael J. Fischer
Nancy Lynch
Michael Paterson 		Impossibility of Distributed Consensus with One Faulty Process[3]
2002 Edsger Dijkstra Self-stabilizing systems in spite of distributed control[4]
2003 Maurice Herlihy Wait-Free Synchronization[5]
2004 Robert G. Gallager
Pierre A. Humblet
Philip M. Spira 		A Distributed Algorithm for Minimum-Weight Spanning Trees[6]
2005 Marshall Pease
Robert Shostak
Leslie Lamport 		Reaching agreement in the presence of faults[7]
2006 John M. Mellor-Crummey
Michael L. Scott (en)
Algorithms for scalable synchronization on shared-memory multiprocessors[8]
2007 Cynthia Dwork
Nancy Lynch
Larry Stockmeyer 		Consensus in the presence of partial synchrony[9]
2008 Baruch Awerbuch
David Peleg
Sparse Partitions[10]
2009 Joseph Halpern
Yoram Moses
Knowledge and Common Knowledge in a Distributed Environment[11]
2010 Tushar Deepak Chandra
Sam Toueg
Vassos Hadzilacos 		Unreliable Failure Detectors for Reliable Distributed Systems
The Weakest Failure Detector for Solving Consensus
2011 Hagit Attiya
Amotz Bar-Noy
Danny Dolev 		Sharing Memory Robustly in Message-Passing Systems
2012 Maurice Herlihy
J. Eliot B. Moss
Nir Shavit
Dan Touitou 		Transactional memory
Software transactional memory
2013 Nati Linial Locality in distributed graph algorithms[12]
2014 K. Mani Chandy (en) et Leslie Lamport The Snapshot algorithm to get a consistent picture of the global state of a system[13]
2015 Michael Ben-Or Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols[14]
Michael O. Rabin Randomized Byzantine Generals[15]
2016 Noga Alon, László Babai et Alon Itai A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem[16]
Michael Luby Simple Parallel Algorithm for the Maximal Independent Set Problem[17]
2017 Elizabeth Borowsky et Eli Gafni Generalized FLP impossibility result for t-resilient asynchronous computations[18]
2018 Bowen Alpern et Fred B. Schneider Defining liveness[19]
2019 Alessandro Panconesi et Aravind Srinivasan Randomized Distributed Edge Coloring via an Extension of the Chernoff–Hoeffding Bounds[20]
2020 Dana Angluin, James Aspnes (en), Zoe Diamadi, Michael J. Fischer, et Rene Peralta Computation in networks of passively mobile finite-state sensors[21]
2021 Paris C. Kanellakis et Scott A. Smolka (en) CCS Expressions, Finite State Processes, and Three Problems of Equivalence[22]

Liens externes

Références

  1. ↑ « Dijkstra Prize », EATCS (consulté le )
  2. ↑ (en) Leslie Lamport, « Time, Clocks, and the Ordering of Events in a Distributed System », Communications of the ACM, vol. 21, no 7,‎ , p. 558-565 (lire en ligne [PDF])
  3. ↑ (en) Michael J. Fischer, Nancy A. Lynch et Michael S. Paterson, « Impossibility of Distributed Consensus with One Faulty Process », Journal of the ACM, vol. 32, no 2,‎ , p. 374-382 (lire en ligne [PDF])
  4. ↑ (en) Edsger Wybe Dijkstra, « Self-stabilizing systems in spite of distributed control », Communications of the ACM, vol. 17, no 11,‎ , p. 643-644 (lire en ligne [PDF])
  5. ↑ (en) Maurice Herlihy, « Wait-Free Synchronization », ACM Transactions on Programming Languages and Systems, vol. 13, no 1,‎ , p. 124-149 (lire en ligne [PDF])
  6. ↑ (en) Robert G. Gallagher, Pierre A. Humblet et Philip M. Spira, « A Distributed Algorithm for Minimum-Weight Spanning Trees », ACM Transactions on Programming Languages and Systems, vol. 5, no 1,‎ , p. 66-77 (lire en ligne [PDF])
  7. ↑ (en) Marshall Pease, Robert Shostak et Leslie Lamport, « Reaching agreement in the presence of faults », Journal of the ACM, vol. 27, no 1,‎ , p. 228-234 (lire en ligne [PDF])
  8. ↑ (en) John M. Mellor-Crummey et Michael L. Scott, « Algorithms for scalable synchronization on shared-memory multiprocessors », ACM Transactions on Computer Systems, vol. 9, no 1,‎ (lire en ligne [PDF])
  9. ↑ (en) Cynthia Dwork, Nancy Lynch et Larry Stockmeyer, « Consensus in the presence of partial synchrony », Journal of the ACM, vol. 35, no 2,‎ , p. 288-323 (lire en ligne [PDF])
  10. ↑ (en) Baruch Awerbuch et David Peleg, « Sparse Partitions », Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS),‎ , p. 503-513 (lire en ligne [PDF])
  11. ↑ (en) Joseph Halpern et Yoram Moses, « Knowledge and Common Knowledge in a Distributed Environment », Journal of the ACM, vol. 37, no 3,‎ , p. 549-587 (lire en ligne [PDF])
  12. ↑ (en) Nathan Linial, « Locality in Distributed Graph Algorithms », SIAM Journal on Computing, vol. 21, no 1,‎ , p. 193-201.
  13. ↑ (en) K. Mani Chandy et Leslie Lamport, « Distributed Snapshots: Determining Global States of Distributed Systems », ACM Trans. Comput. Syst., vol. 3, no 1,‎ , p. 63-75
  14. ↑ (en) Michael Ben-Or, « Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols », dans Proceedings of the Second ACM Symposium on Principles of Distributed Computing, , p. 27-30
  15. ↑ (en) Michael O. Rabin, « Randomized Byzantine Generals », dans Proceedings of Twenty-Fourth IEEE Annual Symposium on Foundations of Computer Science, , p. 403-409
  16. ↑ Noga Alon, László Babai et Alon Itai, « A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem », J. Algorithms, vol. 7, no 4,‎ , p. 567-583 (DOI 10.1016/0196-6774(86)90019-2).
  17. ↑ Michael Luby, « A Simple Parallel Algorithm for the Maximal Independent Set Problem », SIAM J. Comput., vol. 15, no 4,‎ , p. 1036-1053 (DOI 10.1137/0215074).
  18. ↑ Elizabeth Borowsky et Eli Gafni, « Generalized FLP impossibility result for t-resilient asynchronous computations, », dans Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, , p. 91--100
  19. ↑ Bowen Alpern et Fred B. Schneider, « Defining Liveness », Inf. Process. Lett., vol. 21, no 4,‎ , p. 181-185 (DOI 10.1016/0020-0190(85)90056-0)
  20. ↑ Alessandro Panconesi et Aravind Srinivasan, « Randomized Distributed Edge Coloring via an Extension of the Chernoff–Hoeffding Bounds », SIAM Journal on Computing, vol. 26, no 2,‎ , p. 350–368
  21. ↑ Dana Angluin, James Aspnes, Zoe Diamadi, Michael J. Fischer et Rene Peralta, « Computation in networks of passively mobile finite-state sensors », Distributed Computing, vol. 18, no 4,‎ , p. 235-253
  22. ↑ Paris C. Kanellakis et Scott A. Smolka, « CCS Expressions, Finite State Processes, and Three Problems of Equivalence ` », Inf. Comput., vol. 86, no 1,‎ , p. 43-68
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Prix_Dijkstra&oldid=190179684 ».