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

Paper overview

Information is not evenly distributed in the distributed system. Hence, having a proper model to abstract this unbalancing can benefit people who want to improve the distributed system. The paper introduces "knowledge" instead of "causality" to express how much information a processor knows in a distributed system. The paper introduces a hierarchy knowledge level to show the state of each processor. Knowledge always starts from the lowest level and can be upgraded once something happens in the distributed system. The authors point out that it is impossible to upgrade knowledge from "everyone knowing" to "common knowledge". The authors used "The muddy children puzzle" and "Coordinated Attack Revisited" examples to show that only an ideal arbiter can let all processors know one knowledge simultaneously.

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 (assuming that more than one does). 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 from the public announcement of a fact they already know?

Discussion summary for Q1

The father’s announcement makes it common knowledge that at least one child has mud on their head. Even though each child may have had “everyone knows” about the mud, “common knowledge” is defined as everyone now knows that everyone else knows. In essence, every child now has the same level of awareness about the mud facts, and they know that every child has the same level of awareness.

One real world example might be a zoom meeting. For example, participants in a meeting may not know the criteria to begin the meeting or who must be present. They may have an idea based on the list of attendees, but that only goes as far as becoming "everyone knows" knowledge. This knowledge becomes "common knowledge," when the host of the meeting makes an official announcement that all required attendees have arrived and the meeting can officially begin.

Another example may be a cryptocurrency ledger. When two individuals participate in a blockchain transaction, only the 2 individuals have a level of "everyone knows" knowledge. However, when the ledger is posted at the end of the day, that information becomes public, even for people that were not involved in the original transaction. So, that now becomes "common knowledge."

Q2

In section 3 of the paper, the authors discuss a hierarchy of notions of group knowledge. These notions include "distributed knowledge" of a fact G, "someone knows" G, "everyone knows" G, and so on, up to "common knowledge" of G.

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

The knowledge level is "D" for P1, P2, and P3 are deadlock. This knowledge exists in the system but no one notices it. We can only glean distributed knowledge from looking at the distributed system as a whole.

If P4 knows this knowledge, the knowledge level upgrades to "S". Only one person in the system notices the knowledge. P4 would be the "someone knows" process that discovers that the other processes in the system are deadlocked.

If P4 broadcasts the knowledge, the knowledge level upgrade to "E". Everyone in the system knows the knowledge. P4 makes the announcement, and P1, P2, and P3 now know they are deadlocked, but they do not know that the other processes also received the same announcement. So, this knowledge becomes "everyone knows."

However, this knowledge can not become the common knowledge which is the "C" knowledge level. P4 can send a message to each of P1, P2, and P3 to ensure they know the knowledge. They have a chance to respond to it or not. For those who respond, they also need to ensure that the response is received for P4. Then they will send messages for the response and wait for a response. This behavior creates an infinite loop so that the "E" knowledge can not upgrade to "C" knowledge.

This knowledge only becomes common knowledge if we have a reliable broadcast message with some additional message or metadata that communicates that the other processes have received the same announcement. Getting to a "common knowledge" level is unrealistic as all real-world systems have some level of unreliability.

Q3

William and Gurpreet want to find a time to play Street Fighter tonight. Neither of them wants to play unless the other one will be online too. William sends a message to Gurpreet: “How about 7pm tonight?” Gurpreet receives (and delivers) the message and responds to William: “Works for me.” William receives and delivers Gurpreet’s response. William and Gurpreet both know that they are communicating over an unreliable network where messages can be lost.

Does Gurpreet know for sure that William will be online and ready to play at 7pm? Does William know for sure that Gurpreet will be? Explain your reasoning in both cases and relate it to the paper.

Discussion summary for Q3

The answer to the first question is no, Gurpreet does not know for sure that William will be online and ready to play at 7pm. This is because even though William received Gurpreet's response, he has no confirmation that his original message was actually delivered to Gurpreet, and that that is the message Gurpreet is responding to. This is a case of distributed knowledge, or the weakest form of knowledge in a distributed system.

The answer to the second question is also no, William does not know for sure that Gurpreet will be online. William does receive and deliver Gurpreet's response, but William has no confirmation that his original message was received and delivered by Gurpreet. So both people at this point have sent messages communicating their intent to play Street Fighter, but they don't know that the other person has received and delivered all of their messages, and they don't actually know for sure what the other person has and has not seen. So, this would be a case of everyone knows, to the degree of total number of messages sent.

We can actually never get to the level of common knowledge in this system because neither William nor Gurpreet can view the system from a god-like perspective. We can increase the verbosity of our "everyone knows" knowledge level with each additional message we send, but can't actually move higher in the knowledge hierarchy.