Knowledge in a distributed environment
Yoram Moses · CERN Document Server (European Organization for Nuclear Research) · 1986
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 such a system must handle. Individual sites customarily have only partial knowledge about the general state of the system. Moreover, different information is available at the 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. This thesis is an initial attempt to study the role of knowledge in distributed systems. We present a general framework for defining knowledge in a distributed system, and identify a variety of states of knowledge that groups of processors may have. These states of knowledge seem to capture basic aspects of coordinated actions in a distributed environment. This machinery is applied to the analysis of a number of problems: we generalize and extend the well-known coordinated attack problem, which deals with the effects of unreliable communcation on coordination in a distributed system; we analyze a generalized version of the cheating wives puzzle, obtaining insight into the subtle interaction between knowledge, communication and action, as well as an understanding of the subtle differences between broadcasting messages via different communication channels. 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.