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

## Paper overview

This paper talks about the relationship of shared knowledge within the context of distributed systems. Having knowledge about the system allows for many useful applications such as coordination within the asynchronous distributed system model.

One of the main points they talk about is the hierarchy of knowledge within systems. The hierachy states are as follows.
- Distributed Knowledge of fact F
- Someone in the group G knows fact F
- Everyone in G knows fact F
- (Everyone knows that)$^k$ knowledge
- Common knowledge

Each state on knowledge builds upons the previous and with this we can work up towards a greater state. To illustrate this, the author uses the Muddy Children problem to show the different states of knowledge and how each can be built upon to eventually reach common knowledge.

Of the states of knowledge, the most valuable is common knowledge where each member of a system has information of the everything happening in the system as a whole. The author however proves that common knowledge is unattainable for distributed systems because they have the possibility of message failure. They give the Two Generals problems as an example of how coordination is impossible in a system without reliable message delivery.

## Discussion questions

### Q1

In this paper, Halpern and Moses identify several "states of knowledge" of participants in a distributed system, which they put in a hierarchy from weakest to strongest. What are the states of knowledge that the paper discusses? Describe each one informally. What's the difference between "Group G has distributed knowledge of fact F" and "Someone in group G knows fact F"?

#### Discussion summary for Q1

Distributed Knowledge of fact F:
- The group, as a whole, knows a certain fact F, but no one individually know the fact F. For example: if Alice knows there is a cat in the kitchen, and Bob knows the cat is black, then the group as a whole knows there is a black cat in the kitchen, but none of the members knows this fact individually.
- In a sense, it is the idea that the members in a group have a collection of facts that lead to a larger truth, but no one knows the larger truth.

Someone in G knows fact F:
- There exists at least one person in the group G knows the complete knowledge of fact F.
- $\exists$p(p$\in$G $\wedge$ Knows(p, F))

Everyone in G knows fact F:
- Everyone in G knows fact F.
- $\forall$p(p$\in$G $\wedge$ knows(p, F))

F is the E-k knowledge in G:
- If you are to print the logical statement out with code, it would look like this:
`print("everyone in G knows that " * k + "F is true")`
- For example, when `k=1`, the statement is:
`everyone in G knows that F is true`
This is the same as "Everyone in G knows fact F"
- When `k=2`, the statement is:
`everyone in G knows that everyone in G knows that F is true`
It's a deeper level of knowledge where not only does everyone know F, but they also know that everyone else knows F.
A fun example for this: Suppose you are preparing for an epic heist for Queen Elizabeth's crown jewel, and there is another person - your rival - that is planning the same thing. The key to this heist is knowing the location of the crown jewel. Both you and your rival got to know this location.
Naturally, because you are rivals, you and your rival also hacked eachother's computer. Now 1. you know that the rival knows the location, and 2. your rival knows you know the location, but 3. neither of you and your rival know that you have been hacked. This is a E-2 knowledge situation. In the case that you both find out you have been hacked, it would be a E-3 knowledge situation.

F is Common Knowledge in G:
- F is said to be the common knowledge in a group G if F is the E-k knowlege in G for all `k>=1`.
- Common Knowledge is said to be unachievable in a group that relies on messages to exchange information. In the case of the muddy child problem, the fact that at least one child has mud on the forehead becomes a common knowledge as the father announces it. At the moment of the announcement, all the children: 1) know the knowledge, 2) know that this knowledge is broadcasted to everyone, 3) know that everyone has received this knowledge, 4) everyone knows 1~3 ... this could go on forever.
- An example for why the common knowledge is impossible in message-based systems is the Two Generals problem.
- In this sitation there are two units who are trying to coordinate an attack on one enemy, but they can only communicate through a messenger who travels in between. They can only attack if they are both sure that the other will attack as well.
- The first general sends a request to attack to the second general, however the sender is still not sure unless they get an acknowledgement back. They are unsure of this because of the chance the messenger gets lost or caught by the enemy.
- If the second general sends the acknowledgement to the first, they become also unsure if their acknowledgement message was sent properly unless they also get an acknowledgement back.
- The first general, then would have send an acknowledgement, but then the first becomes unsure and so on.
- This leads to a situation where both are constantly waiting for acknowledgement from each other. Due to this, they never are fully sure if they are both going on, so there is no consesus(which is required for common knowledge).

### Q2

Using post-it notes that say "clean" or "muddy", act out the "muddy children" puzzle from section 2 of the paper in your group.

Have one group member play the "father" and all other group members be the children who might be clean or muddy. The "father" should put a post-it note on everyone's forehead that says "clean" or "muddy". The "father" in the group gets to decide how many post-it notes say "dirty", but pick an interesting number (i.e., more than 1). Can you follow the reasoning in the paper (with the father repeatedly asking, "Can any of you prove that you are muddy?", and everyone else answering out loud) to get to the point where every muddy person has learned that they are muddy?

#### Discussion summary for Q2

In the first round each child thinks the same thing:
- If I see no other muddy children, then the muddy child must be me!
- If I see one other muddy child, they might be the only muddy child, or I might be muddy as well. Since that child must be thinking what I’m thinking, I know they will leave after the first round of questioning if I am clean.
- If not, then I must be muddy too, and I will have to leave after round 2.

In the second round:
- If I see two other muddy children and I am clean, then by my previous reasoning, they must leave after 2 rounds.
- If not, then I must be muddy too, and I will have to leave after round 3.

And so on and so forth until k rounds have passed, where k is the number of children that are muddy.

### Q3

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 of Halpern and Moses' paper) 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 Q3

There are three cases we need to consider for broadcast:
- All messages are lost -> Then we have distributed knowledge
- Some messages are delivered -> Someone in group G knows fact F
- All messages are received -> Everyone in the group G knows fact F

This problem is similar to the coordinated attack problem. Even if we had a broadcast system available and the deadlocked processes could send and recieve messages, the system would never be able to reach a point of common knowledge. All the processes would know that there is a deadlock, but they would not know whether the other processes are aware of the deadlock unless we assume that the communication channel is reliable and never fail. So, even after a series of infinite acknowledgments, the processes would still be unable to confirm that the other processes have the information that everyone is deadlocked. This is a loop in which gaining a new piece of information creates another loop.

## Errata

Typos or other issues found in the paper:

[TODO for scribes]

## Other

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

[TODO for scribes]