1997 Gödel Prize

1997 Gödel Prize

Joseph Halpern and Yoram Moses

The 1997 Gödel Prize for outstanding journal articles in the area of theoretical computer science will be awarded to Joseph Halpern and Yoram Moses for their paper "Knowledge and Common Knowledge in a Distributed Environment," J. ACM 37} (1990), 549-587.

The Halpern-Moses paper provided a new and effective way of reasoning about distributed systems, providing rigorous and powerful new techniques based on epistemic logic. When reasoning informally about distributed protocols, researchers naturally think (and speak) in terms of agents "knowing" certain facts about the global system state. The key insight of Halpern and Moses was that this informal notion of knowledge could be given a rigorous mathematical formulation. Using this, they delineated various forms of group knowledge, including common knowledge, which can be viewed as a limiting form of group knowledge. They illustrated these using clever examples, and showed for instance that the distributed task of coordinated attack cannot be performed without common knowledge, and that common knowledge is impossible when communication is not guaranteed. The paper is exceptionally clear and accessible to a wide audience. It not only has had a profound impact on the study of distributed computing, but also on areas as diverse as security, where knowledge is a key concern of cryptographic protocols, and artificial intelligence, where the paper's concrete computational interpretation of knowledge has reinvigorated whole lines of research into knowledge and goals. In impact and originality, it represents an ideal to which all papers in theoretical computer science should aspire.


Created by Ian Parberry, March 25, 1999.
Last updated Thu Mar 25 10:06:23 CST 1999.