Discussion for: Joseph Y. Halpern and Yoram Moses, "Knowledge and Common Knowledge in a Distributed Environment" (JACM, 1990)

Paper overview

The paper emphasises the importance of Knowledge in distributed systems and introduces a hierarchical model of knowledge states. By means of the Muddy Children puzzle, the concept of Common Knowledge is presented. Then, various knowledge states like distributed, "someone in group knows", "everyone in group knows", Ek-knowledge and common knowledge are discussed. It is shown that these states of knowledge form a hierarchy where common knowledge can be thought of as the strongest form of knowledge and distributed as the weakest. Finally, the famous Coordinated Attack problem is put forward to demonstrate how in a lossy communication channel, it is impossible to agree on things (ie., achieve consensus) by exchanging messages.

Discussion questions

Q1

In the "muddy children" problem in this paper, when the father arrives and says, "At least one of you has mud on your head", this provides new useful information to the children, even though they all already knew that at least one of them has mud on their head! How can this be?

Can you think of another situation (in distributed systems or in real life) where a participant in the system can gain new knowledge by being told a fact they already know?

Discussion summary for Q1

In the class discussion, it was agreed that the father's announcement "At least one of you has mud on your head" serves to elevate the state of knowledge to "common knowledge" for the system. That means, because of the announcement, every child now knows that every other child also knows that there is at least one child with a muddy head. As it turns out, the announcement serves as a crucial piece of information that is "new and useful" to the children. Using this, the children who actually have mud on their heads are correctly able to answer "yes" on the k'th time the father asks "Can any of you prove you have mud on your head?".

A similar real-life situation was discussed in class where the host of a party first sends a private message inviting every guest to the party and then sends a group broadcast with the same invitation. The group broadcast is analogous to the father's announcement, which serves to elevate the state of knowledge of the group to "common knowledge". In other words, now every invitee in addition to knowing that they are invited, also knows that everyone in the group knows that everyone knows that everyone knows....k times..that everyone is invited! (k being the number of group members)

Q2

In section 3 of the paper, the authors discuss a hierarchy of notions of group knowledge.

Suppose you have a distributed system where process P1 is stuck waiting for a message from process P2, P2 is stuck waiting for a message from process P3, and P3 is stuck waiting for a message from P1. In what sense (from the hierarchy in section 3) does the group have knowledge of the fact "processes P1, P2, and P3 are deadlocked"? What if you had a deadlock-detection mechanism by which another process in the system P4 learned of the deadlock? What if you had a broadcast mechanism by which P4 could announce the deadlock to P1, P2, and P3? At that point, would "processes P1, P2, and P3 are deadlocked" be common knowledge?

Discussion summary for Q2

DG - We say that knowledge K is distributed in G if someone who knew everything that each member of the Group knows would know K. In this case, each process knows that it itself is waiting on another process for a message. So if we combine the knowledge of every process, we would comprehend the knowledge K that the system is in deadlock.

SG - When someone in the group G knows knowledge k of the overall state. In this case, P4 knows of the state of the P1, P2, and P3, which is in deadlock.

EG - When all the members of group G know knowledge K of the overall state. In this case, all the processes learn of the knowledge K because it was shared by process P4, but each process doesn’t know if the other processes have the same state of knowledge

Common Knowledge - when everyone knows that everyone knows that everyone knows...that every process knows that the other processes also know about the deadlock. In this case, P4 would have to successfully deliver this information until everyone knows that everyone knows that everyone knows…. However, we can’t achieve common knowledge in practice.

Q3

Halpern and Moses write, "Knowledge is just the dual of possibility". What does this mean? Discuss with your group.

Discussion summary for Q3

Dual of 2 properties mean that one property can be expressed in terms of the other property. In the paper, it means that knowledge can be expressed in terms of possibility and vice-versa.

For example, ‘for all’ (∀) and ‘there exists’ (∃) are dual

∀x : P(X) = true → ∄x : P(X) = false
∃x : P(X) = true → !∀x : makes P(X) = false

In terms of knowledge and possibility: (! = not/negation)
Knowledge: Always (x) -- x is always true
Possibility: Sometimes (x) -- x is sometimes true
Always (x) = !Sometimes (!x)
Sometimes (x) = !Always (!x)

In other words, if P(x) always holds (knowledge) then it’s equivalent to saying that it isn’t possible that there’s an x that makes P(x) not hold (possibility). If there’s a possible x where P(x) holds (possibility), then it’s equivalent to saying that P(x) is not always false (knowledge).

Errata

Running list of typos / issues found in the paper:

• N/A

Other

Any interesting points or questions from the group discussion that didn't fit above:

• N/A