Nir Shavit, Maurice Herlihy Awarded 2004 Gödel Prize
 |
| Nir Shavit |
May 10, 2004 - Congratulations to Nir Shavit, Sun Labs, member of the Scalable Synchronization Research Group, Sun Labs at Massachusetts, and Maurice Herlihy, Professor, Brown University and consultant to the Scalable Synchronization Research Group! Their paper, "The Topological Structure of Asynchronous Computability" (see sidebar) by Maurice Herlihy and Nir Shavit, Journal of the ACM, Volume 46, Issue 6 (1999) has been awarded the Gödel Prize for the year 2004.
Presented annually, 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).
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.
This year the award will be presented at The 31st International Colloquium on Automata, Languages and Programming, (ICALP04), to be held July 12-16, 2004, in Turku, Finland.
For additional information:
|
The Topological Structure of Asynchronous Computability
Standard "Turing" computability, named after Alan Turing --- considered by many to be the father of Computer Science -- captures the computational behavior of a single processor. Today, state-of-the-art computer chips (such as Sun Microsystems' new line of CMTs) are multiprocessors; that is, they have several processors on a single chip, and are inherently asynchronous: threads on processor can be halted or delayed without warning. It
is therefore becoming increasingly important to extend computability theory beyond the single processor. The asynchronous computability theorem of Herlihy and Shavit provides the first complete characterization of the circumstances under which computational tasks have such fault-tolerant asynchronous solutions.
The key difficulty in reasoning about asynchronous systems is the "exponential blowup" in the number of possible executions resulting from different interleavings of processors' actions. The important breakthrough in the research of Gödel prize winners Herlihy and Shavit and Saks and Zaharouglou, was the use of tools from algebraic topology, a young branch of modern mathematics, as a tool for reasoning about the multitudes of possible executions in a comprehensible way. The authors were able to show a surprising result: that being "asynchronously computable" is equivalent to having a collection of executions that, when viewed as a high dimensional geometric object, do not have holes.
If holes exist, it follows from the Herlihy-Shavit theorem that the given task is not computable asynchronously. The characterization has had a profound impact on the field of distributed computing and has yielded the first impossibility results for several of its longest-standing open problems, including the famous Renaming and Set Agreement problems.
|
