Halpern and Moses win 1997 Godel Prize

Ron Resnick (resnick@actcom.co.il)
Wed, 9 Apr 1997 09:01:56 +0300 (EET DST)

SCNEWS NEWSFILE appended at 08:19:57 on 97/04/08 GMT (by FAGIN at HAIFASC3)
. . 8 97/04/08 10:16 Halpern and Moses win 1997 Godel prize (FAGIN)

It gives me great pleasure to share the news that Joe Halpern and
Yoram Moses have won the 1997 Godel Prize, for an outstanding journal
article in the area of theoretical computer science, for their 1990
paper "Knowledge and Common Knowledge in a Distributed Environment".

Here is the citation:

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.

The award will be presented at the 24th Colloquium on Automata,
Languages, and Programming (ICALP), to be held July 7-11, 1997 in
Bologna, Italy. The winner was chosen by an awards committee
consisting of Ron Graham (AT&T Bell Laboratories), Juris Hartmanis
(National Science Foundation), David Johnson (AT&T Bell Laboratories),
Gordon Plotkin (University of Edinburgh), Grzegorz Rozenberg, chair
(Leiden University), and Emo Welzl (ETH Zurich).