Gödel Prize - 2004Maurice Herlihy, Nir Shavit, Michael Saks, and Fotios ZaharoglouThe 2004 Gödel Prize for outstanding journal articles in the area of theoretical computer science was awarded jointly to Maurice Herlihy, Nir Shavit, Michael Saks, and Fotios Zaharoglou for their papers: Maurice Herlihy and Nir Shavit: Michael Saks and Fotios Zaharoglou: 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.
|
