# Prêmio Dijkstra

O Prêmio Dijkstra (em inglês: Edsger W. Dijkstra Prize in Distributed Computing) é concedido por artigo científico excepcional sobre os princípios da computação distribuída, cuja significância e impacto sobre a teoria e/ou prática da computação distribuída foram evidentes por no mínimo uma década. É concedido anualmente desde 2000.
O prêmio foi apresentado no Symposium on Principles of Distributed Computing (PODC) da Association for Computing Machinery (ACM) Distributed Computing]], chamado inicialmente de PODC Influential-Paper Award. Foi renomeado em memória de Edsger Dijkstra em 2003, após ele receber o prêmio por seu trabalho sobre autoestabilização em 2002 e morreu pouco depois.
Desde 2007, o prêmio é patrocinado juntamente pelo PODC e o International Symposium on Distributed Computing (DISC) da European Association for Theoretical Computer Science EATCS), e sua apresentação ocorre alternadamente no PODC (anos pares) e DISC (anos ímpares). O prêmio inclui um valor em dinheiro de US$ 2.000.

## Recipientes

| Ano | Artigo | Tópico |
| 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 | Relógios de Lamport |
| 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. Consultado em 17 de agosto de 2016. Arquivado do original (PDF) em 5 de julho de 2007 | Prova da impossibilidade de consenso usando comunicação assíncrona |
| 2002 | Dijkstra, E. W. (novembro de 1974). «Self-stabilizing systems in spite of distributed control». Communications of the ACM. 17 (11): 643–644. doi:10.1145/361179.361202 | Autoestabilização |
| 2003 | Herlihy, M. (1991). «Wait-free synchronization». ACM Transactions on Programming Languages and Systems. 13 (1): 124–149. doi:10.1145/114005.102808 | Solvabilidade e universalidade de consenso em sistemas de memória compartilhada |
| 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 | Algoritmo distribuído para encontrar uma árvore de extensão mínima |
| 2005 | Pease, M.; Shostak, R.; Lamport, L. (abril de 1980). «Reaching Agreement in the Presence of Faults». Journal of the ACM. 27 (2): 228–234. doi:10.1145/322186.322188 | Problema dos generais bizantinos |
| 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 | "provavelmente o mais influente algoritmo prático de exclusão mútua de todos os tempos" |
| 2007 | 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 | resolvendo consenso em sistemas parcialmente síncronos |
| 2008 | Awerbuch, B.; Peleg, D. (1990). «Sparse partitions». Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science. [S.l.: s.n.] pp. 503–513. ISBN 0-8186-2082-X. doi:10.1109/FSCS.1990.89571 | partições esparsas |
| 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 | Um modelo formal para o raciocínio sobre o conhecimento em sistemas distribuídos |
| 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 | Detectores de falha |
| 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 | Simulando memória compartilhada em sistemas de transmissão de mensagens propensos a falhas |
| 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 | Memória transacional |
| 2013 | Linial, N. (1992). «Locality in Distributed Graph Algorithms». SIAM Journal on Computing. 21: 193–201. doi:10.1137/0221015 | Localidade em algoritmos de grafos distribuídos |
| 2014 | Chandy, K. M.; Lamport, L. (1985). «2014 Edsger W. Dijkstra Prize in Distributed Computing». ACM Transactions on Computer Systems. 3: 63–75. doi:http://www.podc.org/dijkstra/2014-dijkstra-prize/ Verifique |doi= (ajuda) | o algoritmo de Chandy-Lamport para obter uma imagem consistente do estado global de um sistema |
| 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: 27–30. ISBN 0897911105. doi:10.1145/800221.806707 Rabin, M. O. (1983). «2015 Edsger W. Dijkstra Prize in Distributed Computing». 24th Annual Symposium on Foundations of Computer Science (sfcs 1983): 403–409. ISBN 0-8186-0508-1. doi:http://www.podc.org/dijkstra/2015-dijkstra-prize/ Verifique |doi= (ajuda) | Algoritmos probabilísticos distribuídos tolerantes a falhas |
| 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 páginas. doi:10.1016/0196-6774(86)90019-2 e Luby, Michael (1986). «A Simple Parallel Algorithm for the Maximal Independent Set Problem». SIAM Journal on Computing. 15 (4). 1036 páginas. doi:10.1137/0215074 | Algoritmo para encontrar um conjuno máximo independente |