Prix Dijkstra

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Liste des lauréats[1]
Année Nom(s) Article
2000 Leslie Lamport (Drapeau des États-Unis États-Unis) Time, Clocks, and the Ordering of Events in a Distributed System[2]
2001 Michael Fischer (Drapeau des États-Unis États-Unis)
Nancy Lynch (Drapeau des États-Unis États-Unis)
Michael Paterson (Drapeau des États-Unis États-Unis)
Impossibility of Distributed Consensus with One Faulty Process[3]
2002 Edsger Dijkstra (Drapeau des Pays-Bas Pays-Bas) Self-stabilizing systems in spite of distributed control[4]
2003 Maurice Herlihy (Drapeau des États-Unis États-Unis) Wait-Free Synchronization[5]
2004 Robert G. Gallager (Drapeau des États-Unis États-Unis)
Pierre A. Humblet
Philip M. Spira (Drapeau des États-Unis États-Unis)
A Distributed Algorithm for Minimum-Weight Spanning Trees[6]
2005 Marshall Pease
Robert Shostak
Leslie Lamport (Drapeau des États-Unis États-Unis)
Reaching agreement in the presence of faults[7]
2006 John M. Mellor-Crummey
Michael L. Scott (Drapeau des États-Unis États-Unis)
Algorithms for scalable synchronization on shared-memory multiprocessors[8]
2007 Cynthia Dwork
Nancy Lynch (Drapeau des États-Unis États-Unis)
Larry Stockmeyer (Drapeau des États-Unis États-Unis)
Consensus in the presence of partial synchrony[9]
2008 Baruch Awerbuch
David Peleg (Drapeau d’Israël Israël)
Sparse Partitions[10]
2009 Joseph Halpern
Yoram Moses (Drapeau d’Israël Israël)
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 (Drapeau des États-Unis États-Unis)
J. Eliot B. Moss
Nir Shavit
Dan Touitou
Transactional memory
Software transactional memory
2013 Nati Linial Locality in distributed graph algorithms

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  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,‎ 1978, 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,‎ avril 1985, 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,‎ 1974, 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,‎ janvier 1991, 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,‎ janvier 1983, 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,‎ avril 1980, 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,‎ 1991 (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,‎ avril 1988, 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),‎ 1990, 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,‎ 1990, p. 549-587 (lire en ligne [PDF])