Concept of Knowledge in Distributed Systems

Swarup Mohalik, LaBRI

Design and verification of distributed algorithms routinely use an informal notion of knowledge of individual processes in the system. It is common to find arguments like "the algorithm in a process terminates when it knows that all other processes have got a certain message", "when process A gets a message m1 then it knows that process B has got a message m2", etc.

Formalization of this concept of knowledge started with the works of Halpern, Moses and others. In this framework, processes have states of knowledge and communication is seen as transforming the states of knowledge. Then one can define the states of knowledge for groups of processes. In particular, "common knowledge" is defined as the facts that are "publicly known". Starting with the works of Halpern et al. there has been a good amount of investigation on relating common knowledge and actions of processes in distributed systems. In this talk, I explain the framework and some results about common knowledge.

J.Y.Halpern and Y.Moses. Knowledge and common knowledge in a distributed environment, Journal of the ACM 37:3, 1990, pp. 549-587.
 
J.Y.Halpern and L. Zuck. A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols, Journal of the ACM 39:3, 1992, pp. 449-478.