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.