Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!decvax!decwrl!pyramid!pesnta!hplabs!ucbvax!su-sushi.arpa!PATASHNIK
From: PATASHNIK@SU-SUSHI.ARPA (Oren Patashnik)
Newsgroups: mod.ai
Subject: Seminar - Knowledge and Action in the Presence of Faults (SU)
Message-ID: <12188539941.7.PATASHNIK@SU-SUSHI.ARPA>
Date: Thu, 6-Mar-86 09:09:35 EST
Article-I.D.: SU-SUSHI.12188539941.7.PATASHNIK
Posted: Thu Mar  6 09:09:35 1986
Date-Received: Tue, 11-Mar-86 08:45:51 EST
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 28
Approved: ailist@sri-ai.arpa

AFLB, 13-Mar-86  :  Yoram Moses (MIT)
12:30 pm in MJ352 (Bldg. 460)

	Knowledge, Common Knowledge, and Simultaneous Actions 
		     in the Presence of Faults

We show that any protocol that guarantees to perform a particular
action simultaneously at all sites of a distributed system must
guarantee that the sites attain common knowledge of particular facts
when such an action is performed. We analyze what facts become common
knowledge at various points in the execution of protocols in a simple
model of a system in which processors are liable to crash.  We obtain
a new protocol for Simultaneous Byzantine Agreement that is optimal in
all of its runs. That is, rather than achieving the worst case
behavior, every run of the protocol halts at the earliest possible
time, given the pattern in which failures occur. This may happen as
early as after two rounds. We characterize precisely what failure
patterns require the protocol to run for k rounds, 1<k<t+2,
generalizing and simplifying the lower bound proof for Byzantine
agreement.  We also show a non-trivial simultaneous action for which
popular belief would suggest that t+1 rounds would be required in the
worst case, and use our analysis to design a protocol for it that
always halts in two rounds. This work sheds considerable light on many
heretofore mysterious aspects of the Byzantine Agreement problem. It
is one of the first examples of how reasoning about knowledge can be
used to obtain improved solutions to problems in distributed computing.

This is joint work with Cynthia Dwork of IBM Almaden.