The Mathematics of AI Agents, laboratory reader ยท Chapter 20

Messages, Beliefs, and Consensus

Sending, receiving, acknowledging and committing are different events, and an unreliable final message cannot make them one.

These four demonstrations follow the chapter's two divisions that can win only by attacking together and can talk only by a messenger who may be lost. They show who knows what after each message and why no number of messages gives common knowledge, why a rule built on the last message fails, how an escrow state with a deadline stays safe when private messages do not, and why a high chance of agreement is not knowledge of agreement.

Every example in these readers is a constructed teaching example. The probabilities, utilities and cases are declared inputs chosen to make the mathematics visible. They are not measurements of any deployed agent, product or team.

Demonstration 1 of 4

One more message, one more level

After a few messages have been delivered, how many levels of mutual knowledge exist, who blocks the next one, and what makes a fact common knowledge?

The last sender of a delivered message cannot see that it arrived, so its view is the same in the run where it arrived and the one where it was lost. Equation (20.1) needs both parties to know the previous level, so the newest message's sender is always the one who fails. Each further delivered message passes the block to the other party and raises the highest level by exactly one, but the walk back through runs a party cannot tell apart always reaches the silent run, so Equation (20.2) never holds. A fact that is true in every run, like a public clock both can read, holds at every level with no message at all.

Equation (20.1), written in LaTeX: \operatorname{MK}_{\mathcal P}^{n+1}(F) = \bigwedge_{i \in \mathcal P} \operatorname{Know}_i(\operatorname{MK}_{\mathcal P}^{n}(F)), \operatorname{MK}_{\mathcal P}^{1}(F) = \bigwedge_{i \in \mathcal P} \operatorname{Know}_i(F).

Equation (20.2), written in LaTeX: \operatorname{CK}_{\mathcal P}(F) \Longleftrightarrow \bigwedge_{n=1}^{\infty} \operatorname{MK}_{\mathcal P}^{n}(F).

Scroll sideways for the whole equation

P = {A, B} is the set of the two parties. F is a fact: either 'message 1, from A to B, was delivered' or 'dawn is the attack time on a public clock'. Know_i(F) means party i knows F. MK^1(F) means both A and B know F; MK^(n+1)(F) means each party knows MK^n(F). CK(F) is common knowledge of F: every level MK^n(F) holds. A run is labelled by k, the number of messages delivered in order (4 are planned): A sends the odd-numbered messages, B the even-numbered ones, and each is sent only after the one before it arrived. A party's view is the messages it sent and received. A party knows a fact only if the fact is true in every run that looks the same to it. A fact is common knowledge in the actual run exactly when it is true in every run reachable by links between runs a party cannot tell apart.

Predict first. Set 3 messages delivered, with the fact 'message 1 was delivered'. Which is the highest level of mutual knowledge, and who cannot reach the next one?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: One more message, one more level. Left, runs 0 to 4 with F true from run 1; boxes show the runs each party cannot tell apart, with run 2 marked. Right, levels 1 to 5: levels up to 1 hold and the next fails, and common knowledge fails.
Messages delivered (4 planned): 2, Fact being tested: Message 1 was delivered
Constructed example: a chain of messages defined for this reader to follow the chapter's two-division story, with who-knows-what computed from the runs and a public clock defined as a contrasting fact.

Calculated values

Messages delivered
2 of 4 planned
B knows F (Know_B)
yes
A knows F (Know_A)
yes
Highest level that holds
1
Next level blocked by
B
Runs reachable from the actual run
5 of 5
Common knowledge of F (Equation 20.2)
fails

F is 'message 1 was delivered'. Highest level that holds = 2 - 1 = 1. Level 1 holds because both parties know level 0. Level 2 fails because B does not know level 1: B sent the newest delivered message (number 2) and cannot tell runs 1 and 2 apart, and in the other run the level does not hold. The links between runs lead from run 2 down to run 0 in 2 - 0 = 2 steps, and F is false in run 0, so Equation (20.2) fails: every delivered message pushes the highest level up by one and the walk back to run 0 is always there.

Worked steps

  1. Run 2: 2 of 4 messages delivered; A sends the odd-numbered messages, B the even-numbered ones.
  2. The newest delivered message is number 2, sent by B, who cannot tell runs 1 and 2 apart.
  3. Highest level of mutual knowledge of F that holds = 2 - 1 = 1.
  4. Level 2 fails because B does not know level 1.
  5. Walking back through runs a party cannot tell apart takes 2 - 0 = 2 steps and ends in run 0, where F is false.
  6. So F is not common knowledge (Equation 20.2) however many messages arrive.

Use the idea

When a log shows request, reply and confirmation, write down who saw each message. The deepest level of mutual knowledge the exchange supports, for the fact that message 1 was delivered in a chain where each message is sent only after the previous one arrived, is one less than the number of messages delivered, and the next level depends on a message nobody can confirm. Before counting acknowledgements, list the facts every participant can observe and knows the others observe.

Where the conclusion applies

One chain of messages in which each is sent only after the previous one arrived, and a message lost is not signalled to its sender. Other message patterns, a shared clock, or a signal when a message is lost would change which runs look the same. The level count depends on the choice of F; a fact both parties already knew would start higher. A public clock still needs a shared reading of time and a rule tying time to action.

Common wrong turn: Enough acknowledgements make it common knowledge
The chapter calls this an appealing but incorrect move: choosing a large enough number of acknowledgements and treating the remaining uncertainty as irrelevant by definition. There is a strict gap between every finite depth and common knowledge.
What this does not settle

Finite unreliable messages can deepen awareness without common knowledge, so they cannot guarantee coordinated attack. The chapter's point is narrower than a ban on messages: a private acknowledgement chain is not a guaranteed shared trigger for an irreversible simultaneous act.

Chapter 20 source: "What this does not settle".

Check your understanding: If 4 messages are delivered out of 4 planned, what is the highest level of mutual knowledge of message 1, and how many link steps lead back to the silent run?
Highest level = 4 - 1 = 3. Level 4 fails because B sent message 4 and cannot tell run 3 from run 4. The walk back crosses 4 - 0 = 4 links to run 0, where message 1 was not delivered, so common knowledge fails.

Chapter 20 source: section "Stage three: finite depth has a boundary". Demonstration C20-D01.

Demonstration 2 of 4

A rule that trusts the last message

Can a rule that tells each division to attack after receiving enough messages be safe and ever attack?

A rule can be written as a pair of thresholds on received messages. For every pair that ever makes a division attack, some run has one attacking and one holding, because the party that sent the final message cannot tell the last run from the one before it. The right panel replays the chapter's reduction: remove the last delivered message, the sender's view is unchanged so its decision is unchanged, and repeating this reaches the no-message run where nobody attacks. With each division needing at least one received message (the chapter's no-message nonattack base), the only pair that is safe is the one that never attacks.

Equation, written in LaTeX: \operatorname{Know}_i(F)

Scroll sideways for the whole equation

Know_i(F) means division i knows F, where F is any statement about which messages arrived; i knows F when F is true in every run that looks the same to i, so a decision rule for i can use only i's own sent and received messages. Three messages are sent in order: a proposal from A, an acknowledgement from B, a confirmation from A. A receives only the even-numbered message (the acknowledgement) and B the odd-numbered ones (the proposal and the confirmation), so after k messages have been delivered A has received k / 2 and B has received (k + 1) / 2, each rounded down to a whole message. A attacks once it has received at least its needed number of messages, B likewise. Safety means that in every run either both attack or neither does.

Predict first. Keep A needing 1 and B needing 2 (the chapter's rule). Which single run makes exactly one division attack?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: A rule that trusts the last message. Left, a grid of attack or hold decisions for A and B in runs 0 to 3 with the runs each cannot tell apart boxed, and an outcome row marking unsafe runs. Right, the four runs from 3 down to 0 joined by arrows labelled with the party that cannot tell neighbouring runs apart, coloured by outcome.
Messages A needs to have received: 1, Messages B needs to have received: 2
Constructed example: the chapter's three-message table (acknowledgement then confirmation), with the needed numbers of received messages varied.

Calculated values

A attacks in runs
2, 3
B attacks in runs
3
Unsafe runs (exactly one attacks)
2
Safe in every run
no
Both attack when all 3 arrive
yes

Run 2: A has received 2 / 2 = 1.0, rounded down to 1 message(s), needs 1. B has received (2 + 1) / 2 = 1.5, rounded down to 1, needs 2. So A attacks and B holds: the rule is unsafe. The rule does make both attack when all three arrive, but the unsafe run shows a lost message breaks it. This is the chapter's three-message table. A's decision is the same in runs that look the same to A, and B's likewise, so a rule cannot make the last message decisive without making one lost message harmful.

Worked steps

  1. Rule: A attacks after receiving at least 1 message(s), B after at least 2.
  2. Run 3 (all delivered): A has received 3 / 2 = 1.5, rounded down to 1; B has received (3 + 1) / 2 = 2.
  3. Run 3 outcome: both attack.
  4. Remove message 3 (sent by A): A's view is unchanged, so A decides the same in run 2 (attacks).
  5. Remove message 2 (sent by B): B's view is unchanged, so B decides the same in run 1 (holds).
  6. Remove message 1 (sent by A): A's view is unchanged, so A decides the same in run 0 (holds).
  7. Run 0 is the no-message base, where nobody attacks.
  8. Unsafe run: 2.

Use the idea

Test a handoff specification by asking what happens if the last message is lost. If the outcome changes for one party only, the specification has hidden a final delivery that nobody can observe.

Where the conclusion applies

A threshold rule over three messages that are sent in sequence and can each be lost. A rule that uses a public clock or a shared record is outside this model. A rule that accepts some chance of mismatch makes a different promise from the one tested here.

Common wrong turn: One more confirmation fixes it
The chapter's answer to requiring B to acknowledge once more is that it moves the vulnerable boundary back to A. Every delivered message looks like extra protection and often is for a local decision, but a final delivery does not have a final acknowledgement within a finite exchange.
What this does not settle

The test is not a substitute for a full protocol proof; it locates a hidden assumption instead. Randomized rules cannot restore an absolute all-runs guarantee, and a public commitment already authorizing both attacks lies outside this result.

Chapter 20 source: "The test is not a substitute for a full protocol proof".

Check your understanding: If A needed 1 and B needed 1, in which run does only B attack?
In run 1 only the proposal arrived: B has received (1 + 1) / 2 = 1, enough, and A has received 1 / 2 = 0.5, rounded down to 0. So B attacks alone.

Chapter 20 source: section "Stage four: why last message cannot save attack". Demonstration C20-D02.

Demonstration 3 of 4

Escrow with a deadline

If two private decisions can strand a token, what does an escrow state with a deadline guarantee, and what does it give up?

With two private decisions, each division acts on its own view, so the run where A has released but B has not taken leaves the token stranded: the last-message problem again. With escrow, the irreversible step moves to a shared authority that applies one rule at a deadline, so the owner is the same in every run and the private messages no longer decide it. What changes is the guarantee: the escrow always has an owner, but a transfer happens only when the public condition is visible.

Equation, written in LaTeX: \operatorname{Know}_i(F)

Scroll sideways for the whole equation

Know_i(F) means division i knows F. Three messages are sent in order (proposal, acknowledgement, confirmation) and a run is the number k that were delivered. Two private decisions: A releases the token once it has received the acknowledgement, B takes it once it has received the confirmation. Escrow with a deadline: A places the token in escrow, and at the deadline a shared authority releases it to B if a named condition is visible and returns it to A if not. 'Exactly one owner' means the token is with A, with B or in escrow, never held by nobody.

Predict first. With two private decisions, in which run is the token held by nobody?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: Escrow with a deadline. Left, a lane picture of the three messages with 2 delivered and the next one lost. Right, for the policy 'Two private decisions', decisions and the token owner in each of four runs; the token ends with nobody holds it in the boxed run.
Messages delivered (of 3): 2, Policy: Two private decisions
Constructed example: the chapter's two-agent resource transfer with an escrow state and deadline (Figure 20.4), with the three-message rule of Demonstration 2 used for the private decisions.

Calculated values

Policy
Two private decisions
Messages delivered
2 of 3
Token at dawn
nobody holds it
Exactly one owner in this run
no
Runs with exactly one owner
3 of 4

A has received 2 / 2 = 1.0, rounded down to 1 message(s), and releases the token when it has received 1. B has received (2 + 1) / 2 = 1.5, rounded down to 1, and takes it when it has received 2. So the token ends with nobody (A released it and B did not take it). Runs with exactly one owner = 4 - 1 = 3. Each division acts on its own private view, so run 2 is lost: A cannot tell run 2 from run 3, which is the same last-message problem as Demonstration 2.

Worked steps

  1. A releases the token once it has received B's acknowledgement; B takes it once it has received the confirmation.
  2. A has received 2 / 2 = 1.0, rounded down to 1, so A releases the token.
  3. B has received (2 + 1) / 2 = 1.5, rounded down to 1, so B waits.
  4. Token at dawn: nobody holds it.
  5. Runs with exactly one owner = 4 - 1 = 3 of 4.

Use the idea

For a handoff that moves an external effect, put the irreversible act behind one authority with a deadline and a named condition, and state the fallback, instead of making two private acknowledgements trigger it.

Where the conclusion applies

A constructed token and three messages in sequence. The authority is reliable, its rule and deadline are known to both parties, and the named condition is a declared input, not a message. Real systems must also say who observes the condition, how clock skew is handled and what happens if the authority is unreachable.

Common wrong turn: A timeout proves what happened remotely
The chapter says timeouts do not reveal what happened remotely: they end local waiting under a shared policy. Their value is a predictable, safe response to uncertainty, so the escrow rule here never uses a guess about which messages arrived.
What this does not settle

The result does not rank protocols, set retry counts, or require a public ledger. Engineering chooses deadlines, recovery paths, and delivery assumptions.

Chapter 20 source: "What this does not settle".

Check your understanding: With two private decisions and 3 messages delivered, who holds the token, and how many of the four runs end with exactly one owner?
A has received 3 / 2 = 1.5, rounded down to 1, and releases; B has received (3 + 1) / 2 = 2 and takes it. B holds it. Only run 2 strands the token, so 4 - 1 = 3 of 4 runs end with exactly one owner.

Chapter 20 source: section "Stage seven: building agent protocols that fail safely". Demonstration C20-D03.

Demonstration 4 of 4

High chance of agreement, no knowledge of it

If parties usually end up committing together, do they know that they will?

Bob commits alone when some request arrives but no reply gets back: probability [1 - (1 - d)^2]^R - d^R. For a small drop probability more rounds shrink it. For a large one the first term decays slowly and agreement can dip before it recovers (at d = 0.5 it goes 0.75, 0.6875, 0.703, 0.746). Bob's view never shows whether his reply arrived, so the worlds he cannot tell apart always include a lost reply, and his knowledge stays at 0 unless losses are declared impossible.

Equation (20.2), written in LaTeX: \operatorname{CK}_{\mathcal P}(F) \Longleftrightarrow \bigwedge_{n=1}^{\infty} \operatorname{MK}_{\mathcal P}^{n}(F).

Scroll sideways for the whole equation

P = {Alice, Bob} is the set of the two parties. Each round, Alice sends a request and Bob, if it arrives, sends a reply; each message is dropped independently with probability d. Alice commits if she sees a reply; Bob commits if he sees a request. Agreement means both or neither commit. 'Alice knows' means that in every possible message pattern that looks the same to her, the request arrived. The same test is used for Bob and his reply. R is the number of rounds.

Predict first. At a drop probability of 0.5, does a second round raise agreement above the one-round value of 0.75?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: High chance of agreement, no knowledge of it. Left, horizontal bars of four probabilities for 2 rounds at drop probability 0.3: agreement 0.830, Alice knows 0.740, Bob knows 0.000, Bob commits alone 0.170. Right, agreement and Bob's knowledge against the number of rounds.
Rounds of request and reply: 2, Probability that a message is dropped: 0.3
Constructed example: the laboratory's bounded request-and-reply model with the notebook's default (2 rounds, 0.3), changed (2 rounds, 0) and transfer (3 rounds, 0.5) cases, computed with the laboratory's own function.

Calculated values

Agreement probability
0.8299
Alice knows the request arrived
0.7399
Bob knows his reply arrived
0.0000
Bob commits without Alice
0.1701
Delivery bit patterns allowed
16 of 16

A round in which the reply does not get back to Alice = 1 - (1 - 0.3) x (1 - 0.3) = 0.51. Bob commits alone = 0.51^2 - 0.3^2 = 0.2601 - 0.09 = 0.1701, so agreement = 1 - 0.1701 = 0.8299. Bob's chance of knowing his reply arrived stays 0: a lost reply looks the same to him as a delivered one. An agreement probability, high or not, is a statement about outcomes, not about what each party knows at every level, so it is not common knowledge in the sense of Equation (20.2).

Worked steps

  1. Drop probability d = 0.3; a round has a request and a reply, each dropped independently.
  2. A round fails to bring a reply back = 1 - (1 - 0.3) x (1 - 0.3) = 0.51.
  3. Bob commits alone when every round fails but at least one request arrives: 0.51^2 - 0.3^2 = 0.1701.
  4. Agreement = 1 - 0.1701 = 0.8299.
  5. Bob knows his reply arrived: 0.0000, because a lost reply looks the same to him as a delivered one.

Use the idea

A report that two components usually agree is not a guarantee that either can act on the agreement. Ask what each party can observe, and whether the gap between agreeing and knowing it matters for the action.

Where the conclusion applies

A fixed number of rounds with synchronized ticks, independent drops, and Alice and Bob each acting on one local trigger. Real systems can crash or reorder messages. At drop probability 0 the model rules out loss by assumption; that is a statement about the model, not evidence that a channel cannot fail. This does not prove the theorem; it shows the two quantities differ.

Common wrong turn: A high agreement probability is knowledge of agreement
The chapter's companion notebook shows that probability of agreement and knowledge of agreement are different quantities. Great depth can make an accident very unlikely under a probabilistic model, but it cannot satisfy the logical demand that neither division attacks unless the other will.
What this does not settle

The bounded model adds probabilities to a finite exchange. It shows that the two quantities differ, and it does not prove the theorem.

Chapter 20 source: "it does not prove the theorem".

Check your understanding: With a drop probability of 0.2 and 2 rounds, what is the chance that Bob commits and Alice does not?
A round in which the reply does not get back to Alice has probability 1 - 0.8 x 0.8 = 0.36. So Bob commits alone with probability 0.36^2 - 0.2^2 = 0.1296 - 0.04 = 0.0896, and agreement is 0.9104.

Chapter 20 source: section "Stage eight: consensus begins with a shared event model". Demonstration C20-D04.