This paper explores the concepts of knowledge and common knowledge in distributed systems. It introduces a framework for formalizing and reasoning about knowledge in such systems, emphasizing the importance of group knowledge in the design and analysis of distributed protocols. The paper distinguishes between distributed knowledge, which is knowledge shared among group members, and common knowledge, which is knowledge that is publicly known. It shows that common knowledge is essential for coordinated actions in distributed systems, but formally, it cannot be attained in practical systems. The paper introduces weaker variants of common knowledge that are attainable in many cases of interest.
The paper discusses the "muddy children" puzzle, illustrating the subtleties of reasoning about knowledge in a group context. It defines a hierarchy of states of knowledge, including distributed knowledge, everyone's knowledge, and common knowledge. The paper also presents the coordinated attack problem, demonstrating that common knowledge is necessary for coordinated actions, but it is not achievable in systems where communication is not guaranteed. The paper further discusses the implications of these findings for distributed systems, emphasizing the importance of fact publication and common knowledge in ensuring reliable communication and coordination.
The paper introduces a general model of a distributed system, defining a set of runs and the properties of a system's behavior. It then defines how knowledge can be ascribed to processors in such systems, using view-based knowledge interpretations. These interpretations allow for precise reasoning about knowledge in distributed systems, aligning with modal logic S5. The paper also discusses the properties of common knowledge under view-based interpretations, including the fixed-point axiom and the induction rule, which are crucial for proving the correctness of distributed protocols. The paper concludes that while common knowledge is ideal for coordination, practical systems often rely on weaker variants of common knowledge to achieve reliable communication and coordination.This paper explores the concepts of knowledge and common knowledge in distributed systems. It introduces a framework for formalizing and reasoning about knowledge in such systems, emphasizing the importance of group knowledge in the design and analysis of distributed protocols. The paper distinguishes between distributed knowledge, which is knowledge shared among group members, and common knowledge, which is knowledge that is publicly known. It shows that common knowledge is essential for coordinated actions in distributed systems, but formally, it cannot be attained in practical systems. The paper introduces weaker variants of common knowledge that are attainable in many cases of interest.
The paper discusses the "muddy children" puzzle, illustrating the subtleties of reasoning about knowledge in a group context. It defines a hierarchy of states of knowledge, including distributed knowledge, everyone's knowledge, and common knowledge. The paper also presents the coordinated attack problem, demonstrating that common knowledge is necessary for coordinated actions, but it is not achievable in systems where communication is not guaranteed. The paper further discusses the implications of these findings for distributed systems, emphasizing the importance of fact publication and common knowledge in ensuring reliable communication and coordination.
The paper introduces a general model of a distributed system, defining a set of runs and the properties of a system's behavior. It then defines how knowledge can be ascribed to processors in such systems, using view-based knowledge interpretations. These interpretations allow for precise reasoning about knowledge in distributed systems, aligning with modal logic S5. The paper also discusses the properties of common knowledge under view-based interpretations, including the fixed-point axiom and the induction rule, which are crucial for proving the correctness of distributed protocols. The paper concludes that while common knowledge is ideal for coordination, practical systems often rely on weaker variants of common knowledge to achieve reliable communication and coordination.