2004 Gödel Prize (original) (raw)

2004 Gödel Prize

The 2004 Gödel Prize for outstanding journal articles in theoretical computer science is shared between the papers:

"The Topological Structure of Asynchronous Computation" by Maurice Herlihy and Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858-923,

and

"Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge" by Michael Saks and Fotios Zaharoglou, SIAM J. on Computing, Vol. 29 (2000), 1449-1483.

CITATION

The two papers recognized by the 2004 Gödel Prize offer one of the most important breakthroughs in the theory of distributed computing.

The problem attacked is the complete understanding of asynchronous wait-free deterministic computation in the basic shared memory model. These papers demonstrate that one can avoid the inherent difficulty of analyzing a dynamic model, transforming it into a static one by associating computational tasks with simplicial complexes and translating the question of existence of a wait-free protocol into (distinct but related) topological questions about the complexes. This reformulation allows the introduction of powerful topological invariants, such as homologies, to show the impossibility of numerous tasks, including set-agreement and renaming.

The discovery of the topological nature of distributed computing provides a new perspective on the area and represents one of the most striking examples, possibly in all of applied mathematics, of the use of topological structures to quantify natural computational phenomena.

Created byWolfgang Bein, July 25,2004