Maurice Herlihy has won the Gödel Prize for the year 2004 for his paper "The Topological Structure of Asynchronous Computability" (coauthored with Nur Shavit) (JACM 46, 6 (1999)). Other winners were Michael Saks and Fotios Zaharoglou, "Wait-Free k-Set Agreement Is Impossible: the Topology of Public Knowledge" (SIAM J. Computing 29, 5 (2000)).
The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computing Theory of the Association of Computing Machinery (ACM-SIGACT). This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and ACM Symposium on the Theory of Computing (STOC). The Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his recently discovered interest in what has become the famous "P versus NP" question. The Prize includes an award of $5000.