Knowledge in a Distributed Environment
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 system's 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1986
- Accession Number
- ADA222131
Entities
People
- Yoram O. Moses
Organizations
- Stanford University