{
"cells": [
{
"cell_type": "markdown",
"id": "680f937ae649",
"metadata": {},
"source": [
"# Chapter 20: Messages, Beliefs, and Consensus\n",
"\n",
"Alice sends a handoff and Bob receives it. Bob sends an acknowledgement, but Alice may never see that reply. Bob knows the request arrived; he does not automatically know that Alice knows it arrived. A protocol that treats one receipt as shared certainty can therefore split the parties' decisions.\n",
"\n",
"This notebook enumerates a bounded request-and-acknowledgement protocol. Alice commits after seeing an acknowledgement. Bob commits after seeing a request. Each party's local view is compared with every positive-probability world that looks the same to that party. The calculation reports agreement and limited knowledge separately. It does not turn a finite retry budget into a proof of common knowledge or asynchronous consensus.\n",
"\n",
"**Outcome:** Enumerate bounded message worlds and distinguish agreement from local knowledge.\n",
"\n",
"- Inspect the declared input contract\n",
"- Predict the hand-checkable case\n",
"- Run the shared computation\n",
"- Change the critical assumption\n",
"- Apply the method to the transfer data\n",
"\n",
"**Guided route:** Run the worked calculation, inspect its figure, change the stated assumption, and try the transfer case. Read the explanations beside each result before opening the answers.\n",
"\n",
"**Deeper route:** First read the mathematics and canonical equation reference. Audit the input contract, predict the changed result, then inspect the shared chapter implementation and solve the questions independently. Both routes use the same calculations and preserve the equations."
]
},
{
"cell_type": "markdown",
"id": "a7781f3ee7dc",
"metadata": {},
"source": [
"## Technical Requirements\n",
"\n",
"Python 3.11 or later, the complete laboratory folder, and the notebook dependencies listed in `requirements-notebooks.txt` (the launcher's **Install notebook tools** choice installs them; see START-HERE). Standard-library chapter commands also support Python 3.10. No API key, model account or network call is used by this experiment.\n",
"\n",
"Prior knowledge:\n",
"\n",
"- Python lists and dictionaries\n",
"- The mapped chapter and its notation"
]
},
{
"cell_type": "markdown",
"id": "483bdea52037",
"metadata": {},
"source": [
"## The question and its mathematics\n",
"\n",
"Each round has two potential delivery bits: request delivery and acknowledgement delivery. An acknowledgement exists only when that round's request arrives. With R rounds, the enumeration contains 2^(2R) constructed bit worlds. Their weights multiply independent delivery or drop probabilities.\n",
"\n",
"A party's view contains its local sends, received messages, and round ticks. Two worlds are indistinguishable to that party when these views match. Alice knows delivery in a world if every positive-probability world with her view contains at least one received request. Bob knows Alice received an acknowledgement only if every world with his view contains that acknowledgement receipt.\n",
"\n",
"Agreement compares Alice's acknowledgement-based commit with Bob's request-based commit. Disagreement occurs when Bob received some request but Alice received no acknowledgement. With drop probability d, its probability after R rounds is [1-(1-d)^2]^R-d^R. The first term means no successful request/ack pair; the second removes worlds where no request arrived at all. This is a bounded protocol calculation under a specific independent-drop law."
]
},
{
"cell_type": "markdown",
"id": "3d5faf4f7d37",
"metadata": {},
"source": [
"## A calculation you can run\n",
"\n",
"Supply a round budget and message-drop probability. The code enumerates bit histories, builds local views, and retains only positive-probability worlds for knowledge tests. Excluding impossible worlds matters at d=0 or d=1, where the declared probability model itself rules out certain histories.\n",
"\n",
"The metrics report world counts, agreement, Alice's delivery knowledge, Bob's acknowledgement-receipt knowledge, and Bob-only commitment. The chart uses request rounds on the horizontal axis and agreement probability on the vertical axis. Compare its analytic values with the enumerated final metric. In the changed case set drops to zero; predict how the possible-world set shrinks before rerunning. The transfer case checks a longer budget at a different loss probability.\n",
"\n",
"The next cell finds the bundle and imports the same computation used by the chapter skill. It does not change your system Python."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "42ebefc0e5c1",
"metadata": {},
"outputs": [],
"source": [
"from pathlib import Path\n",
"import sys, json\n",
"LAB_ROOT = next((p for p in [Path.cwd(), *Path.cwd().parents] if (p / \"lab-manifest.json\").is_file()), None)\n",
"if LAB_ROOT is None:\n",
" raise RuntimeError(\"Open this notebook from the complete extracted laboratory folder.\")\n",
"sys.path.insert(0, str(LAB_ROOT / \"src\"))\n",
"from math_ai_agents.core import analyze, report_text\n",
"from math_ai_agents.plotting import figure_svg\n",
"from IPython.display import SVG, display\n"
]
},
{
"cell_type": "markdown",
"id": "7fffde8c0edb",
"metadata": {},
"source": [
"Set the declared inputs below. These are constructed teaching values, not measurements from a production agent. Change a value only after predicting what it should change."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "c27770f69cff",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Chapter 20: bounded-message-knowledge\n",
"What can each party know after a request and an acknowledgement can be dropped?\n",
"Evidence: constructed teaching example\n",
"\n",
"Calculated quantities:\n",
"{\n",
" \"enumerated_worlds\": 16,\n",
" \"possible_worlds\": 16,\n",
" \"agreement_probability\": 0.8299,\n",
" \"alice_knows_delivery_probability\": 0.7399,\n",
" \"bob_knows_ack_receipt_probability\": 0.0,\n",
" \"bob_commits_without_alice_probability\": 0.1701\n",
"}\n",
"\n",
"Interpretation:\n",
"Alice commits after an acknowledgement; Bob commits after a request. Local knowledge is checked over indistinguishable positive-probability bounded histories.\n",
"\n",
"Assumptions:\n",
"- Independent drops per message opportunity.\n",
"- Bob does not observe whether his acknowledgement arrived.\n",
"- The model contains a fixed bounded number of rounds.\n",
"\n",
"Limitations:\n",
"- Finite agreement probability is not common knowledge or an asynchronous consensus theorem.\n",
"- No hidden timeout, failure detector, or extra receipt is assumed.\n",
"\n",
"Execution: completed locally; constructed inputs are not deployment measurements.\n"
]
}
],
"source": [
"chapter = 20\n",
"inputs = {'rounds': 2, 'drop_probability': 0.3}\n",
"report = analyze(chapter, inputs)\n",
"# This input was explicitly taken from the teaching fixture.\n",
"report['evidence_kind'] = 'constructed teaching example'\n",
"print(report_text(report))"
]
},
{
"cell_type": "markdown",
"id": "e7e2d1ba58e8",
"metadata": {},
"source": [
"At d=0.3 and R=2, no successful request/ack pair has probability 0.51^2=0.2601. No request arrives with probability 0.3^2=0.09. Bob-only commitment therefore has probability 0.1701, and agreement has probability 0.8299.\n",
"\n",
"With zero drops, only one positive-probability world remains. Requests and acknowledgements arrive, so both parties commit and agreement is 1. Bob can know acknowledgement receipt in this restricted model because delivery failure has been declared impossible. That conclusion depends on the model assumption, not on receiving an additional receipt.\n",
"\n",
"The plot below uses the calculated quantities. Read each panel's units before comparing its values."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "590f57e74048",
"metadata": {},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"Matplotlib is building the font cache; this may take a moment.\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(SVG(figure_svg(report)))"
]
},
{
"cell_type": "markdown",
"id": "aa2316ab2afb",
"metadata": {},
"source": [
"**Figure 20.L1:** Calculated chapter experiment. Each panel labels its input and output units; interpret it under the assumptions printed in the report."
]
},
{
"cell_type": "markdown",
"id": "43456b9eb10f",
"metadata": {},
"source": [
"## Change the assumption\n",
"\n",
"Increasing retries does not monotonically create stronger epistemic guarantees. It can alter agreement probability while leaving Bob unable to distinguish a lost acknowledgement from a delivered one. Probability of agreement and knowledge of agreement are different quantities.\n",
"\n",
"The bounded model also supplies synchronized round ticks and independent message losses. Real asynchronous systems may lack those assumptions or face crashes rather than simple drops. This notebook makes no impossibility or consensus theorem claim for those broader settings.\n",
"\n",
"A zero-drop result is especially easy to overread. Declaring failure probability zero removes alternate worlds by assumption. It does not prove the channel cannot fail. When the channel contract is uncertain, retain the plausible loss worlds and identify what extra receipt, timeout rule, or failure detector would be needed for the intended decision."
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "b2d8fcc091e7",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Chapter 20: bounded-message-knowledge\n",
"What can each party know after a request and an acknowledgement can be dropped?\n",
"Evidence: constructed changed-assumption example\n",
"\n",
"Calculated quantities:\n",
"{\n",
" \"enumerated_worlds\": 16,\n",
" \"possible_worlds\": 1,\n",
" \"agreement_probability\": 1.0,\n",
" \"alice_knows_delivery_probability\": 1.0,\n",
" \"bob_knows_ack_receipt_probability\": 1.0,\n",
" \"bob_commits_without_alice_probability\": 0.0\n",
"}\n",
"\n",
"Interpretation:\n",
"Alice commits after an acknowledgement; Bob commits after a request. Local knowledge is checked over indistinguishable positive-probability bounded histories.\n",
"\n",
"Assumptions:\n",
"- Independent drops per message opportunity.\n",
"- Bob does not observe whether his acknowledgement arrived.\n",
"- The model contains a fixed bounded number of rounds.\n",
"\n",
"Limitations:\n",
"- Finite agreement probability is not common knowledge or an asynchronous consensus theorem.\n",
"- No hidden timeout, failure detector, or extra receipt is assumed.\n",
"\n",
"Execution: completed locally; constructed inputs are not deployment measurements.\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"changed_inputs = {'rounds': 2, 'drop_probability': 0}\n",
"changed = analyze(chapter, changed_inputs)\n",
"changed['evidence_kind'] = 'constructed changed-assumption example'\n",
"print(report_text(changed))\n",
"display(SVG(figure_svg(changed)))"
]
},
{
"cell_type": "markdown",
"id": "136ae305a164",
"metadata": {},
"source": [
"**Figure 20.L2:** The changed-assumption result. Compare the printed quantities and the stated assumptions with the first run. A different input need not imply a causal effect in a deployed agent."
]
},
{
"cell_type": "markdown",
"id": "fed845d5fd1d",
"metadata": {},
"source": [
"## Try a new case\n",
"\n",
"At d=0.5 and R=3, Bob-only commitment is 0.75^3-0.5^3=0.296875. Agreement is 0.703125. Compute that before opening the generated result, then compare it with enumeration.\n",
"\n",
"For a local handoff protocol, map which messages each participant can observe and what decision each view permits. Include dropped replies and partial histories. If a release requires evidence that the other party received an acknowledgement, an unobserved send is insufficient. Export a procedure with receipt requirements and stop conditions rather than calling the protocol successful because some world reaches completion."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "fba2f168c0a9",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Chapter 20: bounded-message-knowledge\n",
"What can each party know after a request and an acknowledgement can be dropped?\n",
"Evidence: constructed transfer example\n",
"\n",
"Calculated quantities:\n",
"{\n",
" \"enumerated_worlds\": 64,\n",
" \"possible_worlds\": 64,\n",
" \"agreement_probability\": 0.703125,\n",
" \"alice_knows_delivery_probability\": 0.578125,\n",
" \"bob_knows_ack_receipt_probability\": 0.0,\n",
" \"bob_commits_without_alice_probability\": 0.296875\n",
"}\n",
"\n",
"Interpretation:\n",
"Alice commits after an acknowledgement; Bob commits after a request. Local knowledge is checked over indistinguishable positive-probability bounded histories.\n",
"\n",
"Assumptions:\n",
"- Independent drops per message opportunity.\n",
"- Bob does not observe whether his acknowledgement arrived.\n",
"- The model contains a fixed bounded number of rounds.\n",
"\n",
"Limitations:\n",
"- Finite agreement probability is not common knowledge or an asynchronous consensus theorem.\n",
"- No hidden timeout, failure detector, or extra receipt is assumed.\n",
"\n",
"Execution: completed locally; constructed inputs are not deployment measurements.\n"
]
}
],
"source": [
"transfer_inputs = {'rounds': 3, 'drop_probability': 0.5}\n",
"transfer = analyze(chapter, transfer_inputs)\n",
"transfer['evidence_kind'] = 'constructed transfer example'\n",
"print(report_text(transfer))"
]
},
{
"cell_type": "markdown",
"id": "2250fa39af00",
"metadata": {},
"source": [
"## Apply the method to your inputs\n",
"\n",
"The example file below has the exact input shape the method accepts. Copy it to a new file, replace its values, then point `reader_file` at your copy. Run the cell again. Supplied inputs retain their stated provenance; the program cannot establish that they are representative observations.\n",
"\n",
"- **rounds:** Integer request/acknowledgement rounds 1..6; enumeration has 2^(2 rounds) worlds.\n",
"- **drop_probability:** Independent per-message drop probability in [0,1]."
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "607c8a65d916",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Chapter 20: bounded-message-knowledge\n",
"What can each party know after a request and an acknowledgement can be dropped?\n",
"Evidence: supplied local inputs; provenance not independently verified\n",
"\n",
"Calculated quantities:\n",
"{\n",
" \"enumerated_worlds\": 64,\n",
" \"possible_worlds\": 64,\n",
" \"agreement_probability\": 0.703125,\n",
" \"alice_knows_delivery_probability\": 0.578125,\n",
" \"bob_knows_ack_receipt_probability\": 0.0,\n",
" \"bob_commits_without_alice_probability\": 0.296875\n",
"}\n",
"\n",
"Interpretation:\n",
"Alice commits after an acknowledgement; Bob commits after a request. Local knowledge is checked over indistinguishable positive-probability bounded histories.\n",
"\n",
"Assumptions:\n",
"- Independent drops per message opportunity.\n",
"- Bob does not observe whether his acknowledgement arrived.\n",
"- The model contains a fixed bounded number of rounds.\n",
"\n",
"Limitations:\n",
"- Finite agreement probability is not common knowledge or an asynchronous consensus theorem.\n",
"- No hidden timeout, failure detector, or extra receipt is assumed.\n",
"\n",
"Execution: completed locally; constructed inputs are not deployment measurements.\n"
]
}
],
"source": [
"reader_file = LAB_ROOT / 'data/examples/ch20.json'\n",
"reader_inputs = json.loads(reader_file.read_text())\n",
"reader_report = analyze(chapter, reader_inputs)\n",
"print(report_text(reader_report))"
]
},
{
"cell_type": "markdown",
"id": "ca7b98169e26",
"metadata": {},
"source": [
"## Questions\n",
"\n",
"1. Compute default disagreement.\n",
"\n",
"2. Why can Bob know acknowledgement receipt at zero drops?\n",
"\n",
"3. Compute transfer agreement.\n",
"\n",
"Answers: [separate solutions](../solutions/ch20.md). Try the calculation before opening them."
]
},
{
"cell_type": "markdown",
"id": "a87485bffa1f",
"metadata": {},
"source": [
"## Summary\n",
"\n",
"Messages create different local views. Bounded enumeration checks what follows from those views under a declared drop model and separates agreement from knowledge. The default has a measurable split-decision probability; zero drops remove that split by assumption; the transfer case checks the analytic formula. This is a finite protocol diagnostic, not proof of common knowledge, fault tolerance, or general consensus. Keep receipt requirements and model assumptions explicit.\n",
"\n",
"Limits of this experiment:\n",
"\n",
"- This is a local calculation under declared inputs, not an empirical claim about a deployed agent.\n",
"- Read the returned assumptions and limitations before applying the numerical result.\n",
"\n",
"The assistant skill is [`maa-20-bounded-message-knowledge`](../skills/maa-20-bounded-message-knowledge/SKILL.md). It uses this notebook's tested computation and input contract."
]
},
{
"cell_type": "markdown",
"id": "9cc9f25ba898",
"metadata": {},
"source": [
"## Equations from the chapter\n",
"\n",
"These are the unchanged display equations and their explanations from the canonical chapter. They are a reference for the experiment, not a claim that every equation is numerically implemented by this one method."
]
},
{
"cell_type": "markdown",
"id": "40f0907ca99d",
"metadata": {},
"source": [
"### Equation 20.1\n",
"\n",
"\n",
"\n",
"Defines each next mutual-knowledge level by having every party know preceding level.\n",
"\n",
"First level means every party knows F; each later level wraps that group condition once more.\n",
"\n",
"LaTeX source, preserved for inspection:\n",
"\n",
"```latex\n",
"\\operatorname{MK}_{\\mathcal P}^{n+1}(F) = \\bigwedge_{i \\in \\mathcal P} \\operatorname{Know}_i\\!\\left(\\operatorname{MK}_{\\mathcal P}^{n}(F)\\right), \\qquad \\operatorname{MK}_{\\mathcal P}^{1}(F) = \\bigwedge_{i \\in \\mathcal P} \\operatorname{Know}_i(F).\\tag{20.1}\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "92a2bebbfac1",
"metadata": {},
"source": [
"### Equation 20.2\n",
"\n",
"\n",
"\n",
"Defines common knowledge as every finite mutual-knowledge level holding together.\n",
"\n",
"Common knowledge requires no final depth: levels one, two, and every higher finite level hold.\n",
"\n",
"LaTeX source, preserved for inspection:\n",
"\n",
"```latex\n",
"\\operatorname{CK}_{\\mathcal P}(F) \\quad\\Longleftrightarrow\\quad \\bigwedge_{n=1}^{\\infty} \\operatorname{MK}_{\\mathcal P}^{n}(F).\\tag{20.2}\n",
"```"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Mathematics of AI Agents",
"language": "python",
"name": "maa-lab"
},
"lab_chapter": 20,
"lab_execution": {
"code_cells": 6,
"created_utc": "2026-10-02T05:15:56.108839+00:00",
"elapsed_seconds": 8.95288158301264,
"method": "fresh process; new ipykernel InProcessKernelManager; cells submitted as Jupyter execute requests",
"network_transport_tested": false,
"python": "3.11.15",
"source_sha256": "1e8069f13feb7c6050c6a9cb92e2d878714d1612d7bcc38544bad1d1fc8dac01"
},
"language_info": {
"name": "python"
}
},
"nbformat": 4,
"nbformat_minor": 5
}