💻 computer science

Axiomatisation for an asynchronous epistemic logic with sending and receiving messages

This paper proposes an infinitary axiomatisation, AA*, for an asynchronous epistemic logic that accounts for arbitrary histories of message sending and receiving, generalizing prior work by abandoning the reduction system approach and the assumption that no messages have been received.

Original authors: Philippe Balbiani, Hans van Ditmarsch, Clara Lerouvillois

Published 2026-04-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Philippe Balbiani, Hans van Ditmarsch, Clara Lerouvillois

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to solve a mystery, but they are communicating through a very strange, glitchy messaging app. This app has two distinct problems:

The "Send" button and the "Receive" button are on different planets. Just because Alice hits "send" doesn't mean Bob gets the message instantly. In fact, Bob might not get it for hours, or he might get it before Alice even finishes typing the next sentence.
Everyone is guessing the timeline. Alice doesn't know if Bob has already read her message, if he's about to read it, or if he's completely unaware it exists. She also doesn't know if Bob has received other messages she hasn't seen yet.

This paper is about building a rulebook (a logic) to describe exactly what Alice knows in this messy, asynchronous world.

The Core Problem: The "Snapshot" vs. The "Movie"

In most logic puzzles, everyone is on the same page at the same time. If Alice says "It's raining," everyone hears it instantly. This is like taking a snapshot of a room; everyone sees the same picture.

But in the real world (and in computer networks), communication is a movie.

Sending is like a director shouting "Action!"
Receiving is like an actor hearing the cue.
The "history" is the script of everything that has happened so far.

The authors, Philippe, Hans, and Clara, are asking: How do we write a rulebook for knowledge when the "script" (the history of messages) is different for every person?

The Two Types of Rules They Created

The paper proposes two different ways to write these rules, depending on how you look at the story.

1. The "Fresh Start" Rules (The Empty History)

Imagine the group just met. No messages have been sent yet. The "script" is blank.

The Rule: If we start from zero, we can simplify the rules. We can take any complex sentence about "what happens after a message is sent" and translate it into a simple sentence about "what is currently true."
The Analogy: It's like a game of chess where you can predict the next move based only on the current board. You don't need to remember the whole game history to know the rules. The authors call this system AA. It's a "reduction system," meaning it shrinks complex problems down to simple ones.

2. The "Any Time" Rules (The Infinite History)

Now, imagine the group has been talking for days. Alice has received 5 messages, Bob has received 3, and Charlie has received 7. They are all looking at different parts of the script.

The Problem: The "Fresh Start" rules don't work here. You can't just simplify the rules because the history is too messy. Alice might know something Bob doesn't, simply because she got a message he hasn't seen yet.
The New Rule: The authors created a new, much more complex rulebook called AA*.
The Catch: This rulebook is infinitely large. You can't shrink the complex sentences down to simple ones anymore. You have to accept that some rules are just too complicated to simplify.
The "Empty" Check: To make this work, they invented a special "magic check" called empty. This check asks: "Is the script completely blank right now?"
- If the answer is YES, we can use the simple rules.
- If the answer is NO (which is usually the case in the middle of a conversation), we have to use the complex, infinite rules.

Why is this hard? (The "One Person" Problem)

The paper hits a wall when there is only one person in the group.

The Metaphor: Imagine Alice is the only person in the universe. She sends a message to herself.
The Issue: In a group, Alice knows she hasn't received a message because she hasn't seen it, and she knows Bob might have. But if Alice is alone, she can't distinguish between "I haven't received a message" and "No message was ever sent."
The Result: The authors admit they couldn't solve the rulebook for a single person yet. The trick they used for groups (checking if everyone knows the history is empty) breaks down when there's only one person. They say, "We'll need a new method for this, maybe later."

The "Three-Valued" Twist

The paper mentions something interesting about "truth."

In normal logic, a statement is either True or False.
In this asynchronous world, a statement can be Undefined.
The Analogy: Imagine Alice is waiting for a package.
- If the package arrives, the statement "I have the package" is True.
- If the package is lost, it's False.
- But if the package is in transit and she doesn't know if it's coming or gone, the statement is Undefined.
The authors' logic handles this "Undefined" state carefully. It's not just a mistake; it's a fundamental part of how asynchronous knowledge works.

Summary

This paper is a mathematical attempt to map out what you know when you don't know what others know, and you don't know when they got their information.

If you start fresh: You can simplify the rules.
If you are in the middle of a chaotic conversation: You need a massive, infinite set of rules that can't be simplified.
If you are alone: The current rules break, and we need new ideas.

The authors successfully built the "Infinite Rulebook" (AA*) for groups, proving that even in a chaotic, asynchronous world where messages arrive at different times, we can still logically describe what everyone knows.

1. Problem Statement

The paper addresses the challenge of modeling asynchronous communication in multi-agent systems using Dynamic Epistemic Logic (DEL).

The Gap: Standard DEL (e.g., Public Announcement Logic) treats communication as instantaneous and synchronized: a message is sent and received by all agents simultaneously. This fails to capture real-world distributed systems where sending and receiving are distinct events occurring at different times.
The Specific Challenge: The authors aim to formalize a logic where:
1. Agents have temporal uncertainty regarding the history of messages (they do not know how many messages others have received).
2. Agents have epistemic uncertainty regarding the state of the world.
3. The logic must distinguish between the sending of a message (broadcast) and the receiving of a message (individual action).
4. The system must handle validity in two contexts:
  - $\epsilon$ -validity: Truth in the initial state (empty history).
  - $\ast$ -validity (Always-validity): Truth in any state given any prior history of sending and receiving.

Previous work (specifically reference [4]) provided an axiomatisation ($AA$) for $\epsilon$ -validities using a reduction system (reducing dynamic modalities to static epistemic ones). However, this reduction approach fails for $\ast$ -validities because the properties of the system change fundamentally once a history exists (e.g., agents may have received different numbers of messages).

2. Methodology

2.1 Language and Syntax

The authors define a language $\mathcal{L}$ extending multi-agent modal logic with two types of dynamic modalities:

Broadcasting: $\langle \varphi \rangle \psi$ (The formula $\varphi$ is announced/broadcast; subsequently $\psi$ holds).
Receiving: $\langle a \rangle \psi$ (Agent $a$ receives the next message in their queue; subsequently $\psi$ holds).
History Words: Sequences of agents and formulas (e.g., $p.a.q$ ) represent the sequence of events. A history is a word where, for every agent, the number of received messages never exceeds the number of sent messages (FIFO constraint).

2.2 Semantics

The semantics are defined over pairs $(s, \alpha)$ , where $s$ is a state in a Kripke model and $\alpha$ is a history word.

Executability ( $\triangleright\triangleleft$ ): A relation determining if a history $\alpha$ $α$ can be executed in state $s$ $s$ . This ensures that:
1. The history is a valid sequence (FIFO).
2. All announced formulas were true at the moment of their broadcast.
3. Agents only consider histories executable in states they consider possible.
View Relation ( $\triangleright_a$ ): Defines what agent $a$ considers possible. Agent $a$ considers a history $\beta$ possible relative to actual history $\alpha$ if the sequence of messages $a$ has received in $\beta$ matches exactly what they have received in $\alpha$ . Crucially, agents do not imagine histories containing messages they haven't received yet.
Three-Valued Flavor: The semantics behaves somewhat like a three-valued logic. If a history is not executable in a state ( $s \not\triangleright\triangleleft \alpha$ ), formulas are neither true nor false in that pair, though the logic retains standard validities.

2.3 The "Empty" Formula

A central technical innovation is the definition of a formula empty:
$\text{empty} := \bigwedge_{a \in A} [a]\bot \land \bigwedge_{a,b \in A} K_a [b]\bot$
This formula characterizes the state where the history is empty ( $\alpha = \epsilon$ ). It asserts that no messages have been received by anyone, and everyone knows this. This is only possible in a multi-agent setting ( $|A| \ge 2$ ).

3. Key Contributions

3.1 Axiomatisation $AA^*$

The primary contribution is the proposal of $AA^*$ , an axiomatisation for $\ast$ -validities (always-validities).

Infinitary Nature: Unlike the previous reduction-based system $AA$, $AA^*$ is infinitary. It cannot reduce dynamic modalities to static ones because the truth of formulas depends on the specific history.
The Rule $(R^*)$ : The system includes an infinitary rule:
- Premise: For all words $\alpha$ , $\text{empty} \to [\alpha]\varphi$ is derivable.
- Conclusion: $\varphi$ is derivable.
  This rule effectively reduces $\ast$ -validity to $\epsilon$ -validity by "resetting" the history to empty via the empty formula.
Axioms: The system includes axioms for:
- Distribution of knowledge and dynamic modalities.
- Executability conditions (e.g., a message can only be received if it was sent).
- Atomic permanence (truth values of atoms do not change).
- A specific axiom for knowledge in asynchronous settings: $\text{empty} \to (K_a \varphi \leftrightarrow ([\alpha]\bot \lor \bigvee_{\alpha \triangleright_a \beta} K_a [\beta]\varphi))$ .

3.2 Completeness and Soundness

Soundness: The authors prove that every theorem in $AA^*$ is $\ast$ -valid.
Completeness: They prove that every $\ast$ -valid formula is a theorem of $AA^*$ . The proof uses a canonical model construction based on maximal consistent theories. A significant technical hurdle was defining the accessibility relations on the canonical model to ensure they form equivalence relations only when restricted to theories containing empty.

3.3 The Single-Agent Limitation

The paper rigorously demonstrates that the proposed method fails for a single agent.

In a single-agent system, an agent always knows they have received all messages they have seen. There is no formula equivalent to empty that can distinguish an empty history from a non-empty one where the agent has received everything.
Consequently, the reduction from $\ast$ -validity to $\epsilon$ -validity via empty is impossible in the single-agent case. The authors leave the axiomatisation for the single-agent case as an open problem.

4. Results

Formal System: A complete and sound infinitary axiomatisation ( $AA^*$ ) for asynchronous epistemic logic with separate send/receive modalities.
Reduction Mechanism: A novel method to handle "always-validity" by using the empty formula to anchor the logic back to the initial state, bypassing the need for a finite reduction system.
Distinction from S5: The logic does not satisfy the standard S5 truth axiom ( $K_a \varphi \to \varphi$ ) globally. Knowledge is only factual if the agent knows the history is empty. Otherwise, the modality behaves more like "consistent belief."
Comparison to Distributed Computing: The semantics aligns with the concept of consistent cuts in distributed systems but refines it by incorporating truth conditions (executability) directly into the logic, preventing inconsistent states (e.g., receiving a message before it is sent, or receiving a false announcement).

5. Significance

Theoretical Advancement: This work bridges the gap between standard Dynamic Epistemic Logic (which assumes synchrony) and the realities of distributed computing (asynchrony). It provides the first rigorous logical framework that treats sending and receiving as distinct, asynchronous events with separate modalities.
Handling Temporal Uncertainty: It successfully models the specific type of uncertainty where agents are unsure of the length of the communication history relative to others, a scenario common in gossip protocols and distributed consensus.
Methodological Innovation: The use of an infinitary rule ( $R^*$ ) combined with a specific "reset" formula (empty) offers a new template for axiomatising logics where dynamic properties cannot be reduced to static ones via finite rewriting.
Future Directions: The paper identifies clear paths for future research, including extending the logic to group knowledge (distributed knowledge), non-public communication, and solving the single-agent axiomatisation problem.

In summary, the paper establishes a robust logical foundation for reasoning about knowledge in asynchronous environments, proving that while standard reduction techniques fail, a carefully constructed infinitary system can capture the full complexity of asynchronous message passing.