Saraswati, goddess of knowledge

We usually reason about distributed systems by asking, what can one process know about the state of the system? E.g., if a majority of Raft nodes tell the leader that they have replicated a log entry, the leader knows the entry is durable. Therefore the leader can take various actions, like replying to the user who submitted the log entry. On the other hand, if a Raft follower hasn’t heard from the leader in a while, it might suspect the leader has crashed, but it can never know for sure. A process must somehow gather enough information to deduce the facts it must know to take the correct action. I think about knowledge all the time when I’m analyzing a distributed algorithm.

On the other hand, my main tool for checking the correctness of an algorithm is TLA+ and the TLC model-checker. There’s no notion of knowledge in a TLA+ specification, just a mindless state machine obeying if-then instructions. When I read a TLA+ spec I might think, “In this state, the leader knows the log entry is majority-replicated.” But that’s anthropomorphism. The spec just says: if this, then do that.

I’m studying the 1990 paper, “Knowledge and Common Knowledge in a Distributed Environment”, by Joseph Halpern and Yoram Moses. They bring a theory of knowledge and belief to distributed systems. It’s a hard paper for me, so I’ll blog it as I read, a few sections at a time. My goals are to understand the material and explain it to you. I also want to explore a new direction: integrating knowledge into TLA+. This might be a dead end, we’ll see!

Muddy Children #

The paper begins with the muddy children puzzle, apparently a classic of epistemology:

Imagine n children playing together. The mother of these children has told them that if they get dirty there will be severe consequences. So, of course, each child wants to keep clean, but each would love to see the others get dirty. Now it happens during their play that some of the children, say k of them, get mud on their foreheads. Each can see the mud on others but not on his own forehead. So, of course, no one says a thing. Along comes the father, who says, “At least one of you has mud on your head,” thus expressing a fact known to each of them before he spoke (if k > 1). The father then asks the following question, over and over: “Can any of you prove you have mud on your head?” Assuming that all the children are perceptive, intelligent, truthful, and that they answer simultaneously, what will happen?

Halpern and Moses introduce this puzzle to warm up the reader’s thinking about knowledge in distributed systems. When is it important for one process to know what another process knows? What is “common knowledge” and when is it needed?

The solution to the muddy children puzzle is: the first k - 1 times the father asks the question, all children simultaneously reply “no”: they can’t prove they’re muddy. The k^th time, the muddy children say “yes” and the clean children say “no.” But if the father hadn’t announced “at least one is muddy” at the start, the muddy children would never figure out they’re muddy. Even when k > 1, and all the children can see with their own eyes that at least one is muddy, the father’s announcement of this fact is crucial.

This result is well-known to logicians, so the paper doesn’t explain it in depth. But I will. Let’s work the problem for k from 1 to 3. (The number of clean children is actually irrelevant.)

Here are our variables:

• k: the number of muddy children.
• m: the father’s announcement, “at least one of you is muddy.”
• q: the number of times the father has asked, “can you prove you’re muddy?”

One muddy child #

The first time the father asks the question, the muddy child sees that all the other children are clean. Since the father announced m, the muddy child knows it must be the muddy one, and says “yes.” Incidentally, the muddy child knows k = 1. The other children see one muddy child. They don’t know whether they’re also muddy (they don’t know if k is 1 or 2), so they say “no”.

The purpose of the father’s announcement m is clear here: without it, the muddy child doesn’t know if the reason it sees only clean children is because k = 0, or because k = 1 and it has mud on its face.

Two muddy children #

Here’s where things get freaky. The father announces m, which all the children can already see is true, and yet his announcement is necessary for solving the puzzle.

When the father asks his question the first time, can Child a answer “yes”? It sees that Child b is muddy. It considers some possibilities:

• a could have mud on its own face or not.
• b could think it has mud on its own face, or not.

These two pairs of possibilities lead to four possible worlds in a’s mind:

But the father’s announcement m is “common knowledge”: that is, everyone knows that k ≥ 1, and everyone knows that everyone knows … (ad infinitum) … that k ≥ 1. So a knows b knows the world where all children are clean is impossible:

Since a could be muddy or clean, depending on which world is real, it replies “no” to the father’s question. Child b replies “no” for the same reason (swapping a and b).

Child a hears b’s answer, and now a has learned something. Child a knows that b sees a muddy child! If b hadn’t seen a muddy child, then b would’ve said “yes”, because of m. This eliminates the other world where b sees no muddy child:

All worlds where a is clean are now eliminated, so the next time the father asks his question, a replies “yes”: it knows it’s muddy. Child b does the same.

So the father’s announcement of m is crucial to a, even though a knows k ≥ 1 already: m ensures that a knows b knows k ≥ 1.

Three muddy children #

I’ll work this problem similarly, but without diagrams. At the start, before the father announces m, a sees 2 muddy children, so:

Initial condition, before father announces m:
a knows:
  k ∈ [2, 3]
  b knows:
    k ∈ [1, 3]
    c knows:
      k ∈ [0, 3]

The text above is my attempt to represent statements like, “a knows k is between 2 and 3 inclusive, and a knows b knows k is between 1 and 3 inclusive,” and so on. Why does a know b knows that? Because:

• a knows b sees mud on c (definitely 1 muddy child)
• b could think its own face is muddy (maybe 1 more muddy child)
• b (in a’s mind) might see mud on a (maybe 1 more muddy child)

Hence b (in a’s mind) could think there are 1, 2, or 3 muddy children.

How could a think b thinks c thinks there are 0 muddy children, even though a knows c sees the mud on b’s face? Well, if a is clean (in a’s mind), and b thinks its own face is clean (in a’s mind), then b thinks c might see no muddy children (still in a’s mind). So a thinks it’s possible for b to think c sees no muddy children, although a knows that’s wrong!

But then the father announces m. Now it’s common knowledge that k ≥ 1:

After father announces m:
a knows:
  k ∈ [2, 3]
  b knows:
    k ∈ [1, 3]
    c knows:
      k ∈ [1, 3]

The father asks the question, “can you prove you’re muddy?”, once:

After father announces m, and q=1:
a knows:
  k ∈ [2, 3]
  b knows:
    k ∈ [2, 3]
    c knows:
      k ∈ [1, 3]

Child c says “no,” which must mean it sees a muddy child. Child a knows b knows c is muddy as well, so a knows b knows k ≥ 2.

The father asks a second time:

After father announces m, and q=2:
a knows:
  k ∈ [3, 3]
  b knows:
    k ∈ [2, 3]
    c knows:
      k ∈ [1, 3]

Since b said “no,” and a knows b knew k ≥ 2, a knows b sees 2 muddy children. Child a also knows b is muddy, so a knows k ≥ 3. Since a only sees 2 muddy children, a knows the third muddy child is itself and k = 3. The third time the father asks, a says “yes.” The other muddy children are reasoning identically to a, so they also say “yes.”

The battle of wits in The Princess Bride.

k muddy children #

We’ve seen that for each k from 1 to 3, when the father asks the question for the k^th time, all muddy children answer “yes” and the others answer “no.” Let’s say a sees 3 muddy children and assumes it has no mud on its own face, i.e. it assumes k = 3. If the father asks 3 times and all children still answer “no,” then a knows its assumption was false, so a knows it’s muddy and k = 4. Child a then correctly answers “yes” to the 4^th question. Same for the other children. And so on for all k > 4, inductively.

A hierarchy of states of knowledge #

We’ve seen a weird phenomenon, where the father’s announcement of a fact that everyone already knows somehow gives the children useful information. I explained to myself and to you how this works in the muddy children puzzle. Halpern and Moses explain it in general, by defining a hierarchy of states of knowledge. To begin, they introduce the notation:

This is read, “i knows $\varphi$.” Some agent (or process or whatever) i knows a fact $\varphi$ (Greek letter “phi” for “fact”). I’ll discuss the authors’ definition of knowledge later, it’s terrific, stay tuned! For now, let’s just say an agent’s knowledge can depend only on the agent’s local history, i.e. its initial state and the actions it’s taken and observed. Also, knowledge is always true. A belief can be false, but if an agent knows $\varphi$, then $\varphi$ is a true fact.

Here’s the authors’ hierarchy of knowledge, from weakest to strongest:

• $D_G \varphi$     “the group G has distributed knowledge of $\varphi$”
  
  A fact $\varphi$ is distributed knowledge if someone with a global view could infer $\varphi$ from everything known by every agent in some group G, even if no individual agent in G knows.

• $S_G \varphi$     “someone in G knows $\varphi$”
  
  Defined as: $K_i \varphi$ for some i in G.

• $E_G \varphi$     “everyone in G knows $\varphi$”
  
  Defined as: $K_i \varphi$ for all i in G.

• $E_G^k \varphi$     “$\varphi$ is $E^k$-knowledge in G”
  
  Everyone in G knows that everyone in G knows that … everyone in G knows $\varphi$, where “everyone in G knows that” is repeated k times.

• $C_G^k \varphi$     “$\varphi$ is common knowledge in G”
  
  Defined as, $E_G^k \varphi$ for all k ≥ 1.

The authors point out, using this framework, that when the muddy children puzzle begins, $E_G^{k-1} m$ is true. E.g., if there are two muddy children, then everyone knows m. If there are three muddy children, everyone knows that everyone knows m, because everyone sees at least 2 muddy children, so everyone knows everyone else sees at least 1 muddy child. But to solve the puzzle, they must upgrade their knowledge from $E_G^{k-1} m$ to $E_G^k m$, which is what the father’s announcement does. (The father’s announcement goes farther, making m common knowledge, but all he must do is upgrade m to $E_G^k m$.)

This is a useful way to think about nodes in a distributed system: each has limited knowledge, but there is distributed knowledge implicit in the whole system. To correctly take certain actions, nodes need a certain level of knowledge or higher. Nodes exchange messages to promote their knowledge up the hierarchy. Each level in the hierarchy implies all the lower levels:

Knowledge hierarchies in Raft #

Halpern and Moses don’t talk much about actual distributed protocols, but I kept thinking about Raft—how does the Raft protocol look if it’s recast as a flow of knowledge?

Let’s say a Raft leader creates a log entry. I’ll call the fact that the entry exists $\varphi$, and right now only the leader knows $\varphi$.

The leader sends the log entry to its two followers, but they haven’t acknowledged it yet:

Now everyone knows $\varphi$, but the leader doesn’t know any follower knows $\varphi$. Let’s say G is the set of all nodes and F is the set of followers. Using Halpern and Moses’s notation:

Let’s call the fact “the entry is durable” $\psi$, the Greek letter psi. This fact is true if the entry is replicated to at least a majority of nodes, so it’s certainly true if it’s replicated by all nodes—that is, if everyone knows $\varphi$ then $\psi$ is true. But currently only God can see that all nodes have the entry, so $\psi$ is distributed knowledge.

Then the leader receives an acknowledgment.

We can say the leader knows $\psi$ if it knows any follower knows $\varphi$:

(This is true because the leader + one follower is a majority. If there were more than 3 nodes we’d need a different rule.) Now $\psi$ has been upgraded, from distributed knowledge to something that someone knows:

The leader tells the followers that the entry is committed.

Now $\psi$ has been upgraded again, from a fact that someone knows to a fact that everyone knows.

But (according to the Raft paper) followers don’t tell the leader which entries they know are committed, so $\psi$ doesn’t become something that everyone knows that everyone knows, much less common knowledge.

Onward #

This covers the first three sections of the paper. We’ve seen Halpern and Moses’s knowledge hierarchy, and how it’s useful for analyzing the muddy children puzzle and Raft. Next, we’ll briefly visit the famous Byzantine Generals, who are still trying to decide when to attack their common enemy. After that we’ll get into the meat of the paper, which offers a remarkably satisfying definition of knowledge.

Lakshmi and Saraswati