Accession Number:

ADA222131

Title:

Knowledge in a Distributed Environment

Descriptive Note:

Technical rept.

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1986-03-01

Pagination or Media Count:

116.0

Abstract:

The distributed nature of information in a distributed system is one of the major issues that protocols for cooperation and coordination between individual components in a such systems must handle. Individual sites customarily have only partial knowledge about the general state of the system. Moreover, different information is available at different sites of the system. Consequently, a central role of communication in such protocols is to inform particular sites about events that take place at other sites, and to transform the systems state of knowledge in a way that will guarantee the successful achievement of the goals of the protocol. We present a general framework for defining knowledge in a distributed system, and identify a variety of states of knowledge of sets of processors, which seem to capture some basic aspects of coordinated actions in a distributed environment. This machinery is applied to the analysis of a number problems we generalize and extend the well-known coordinated attack problem, which deals with the effects of unreliable communication on coordination in a distributed system we analyze a generalized version of the cheating wives puzzle, obtaining insight into the subtle differences between broadcasting messages via different communication channels, and into the subtle interaction between knowledge, communication and action. Finally, we apply this machinery to the study of fault-tolerance in systems of unreliable processors, providing considerable insight into the Byzantine agreement problem, and obtaining improved protocols for Byzantine agreement and many related problems.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE