💻 computer science

Axiomatisation for an asynchronous epistemic logic with sending and receiving messages

Dieser Artikel schlägt eine infinitäre Axiomatisierung AA* für eine asynchrone epistemische Logik vor, die beliebige Historien des Sendens und Empfangens von Nachrichten berücksichtigt, indem er die Reduktionssystemmethode und die Annahme, dass keine Nachrichten empfangen wurden, aufgibt und damit frühere Arbeiten verallgemeinert.

Ursprüngliche Autoren: Philippe Balbiani, Hans van Ditmarsch, Clara Lerouvillois

Veröffentlicht 2026-04-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Philippe Balbiani, Hans van Ditmarsch, Clara Lerouvillois

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Gruppe von Freunden vor, die versuchen, ein Rätsel zu lösen, aber über eine sehr seltsame, fehleranfällige Messaging-App kommunizieren. Diese App hat zwei deutliche Probleme:

Die Taste „Senden" und die Taste „Empfangen" befinden sich auf verschiedenen Planeten. Nur weil Alice auf „Senden" klickt, bedeutet das nicht, dass Bob die Nachricht sofort erhält. Tatsächlich könnte es Stunden dauern, bis Bob sie erhält, oder er könnte sie erhalten, bevor Alice sogar den nächsten Satz getippt hat.
Jeder rät an der Zeitlinie. Alice weiß nicht, ob Bob ihre Nachricht bereits gelesen hat, ob er im Begriff ist, sie zu lesen, oder ob er völlig ahnungslos ist, dass sie existiert. Sie weiß auch nicht, ob Bob andere Nachrichten erhalten hat, die sie noch nicht gesehen hat.

Dieser Artikel handelt davon, ein Regelwerk (eine Logik) zu erstellen, das genau beschreibt, was Alice in dieser chaotischen, asynchronen Welt weiß.

Das Kernproblem: Der „Schnappschuss" versus der „Film"

In den meisten Logikrätseln befinden sich alle zur gleichen Zeit auf derselben Seite. Wenn Alice sagt „Es regnet", hört es jeder sofort. Das ist wie ein Schnappschuss eines Raumes; jeder sieht dasselbe Bild.

Aber in der realen Welt (und in Computernetzwerken) ist Kommunikation ein Film.

Senden ist wie ein Regisseur, der „Action!" ruft.
Empfangen ist wie ein Schauspieler, der den Hinweis hört.
Die „Geschichte" ist das Drehbuch von allem, was bisher passiert ist.

Die Autoren, Philippe, Hans und Clara, fragen: Wie schreiben wir ein Regelwerk für Wissen, wenn das „Drehbuch" (die Historie der Nachrichten) für jede Person unterschiedlich ist?

Die zwei Arten von Regeln, die sie erstellt haben

Der Artikel schlägt zwei verschiedene Wege vor, diese Regeln zu schreiben, je nachdem, wie man die Geschichte betrachtet.

1. Die „Frischer-Start"-Regeln (Die leere Historie)

Stellen Sie sich vor, die Gruppe hat sich gerade kennengelernt. Es wurden noch keine Nachrichten gesendet. Das „Drehbuch" ist blank.

Die Regel: Wenn wir bei Null anfangen, können wir die Regeln vereinfachen. Wir können jeden komplexen Satz über „was passiert, nachdem eine Nachricht gesendet wurde" in einen einfachen Satz über „was aktuell wahr ist" übersetzen.
Die Analogie: Es ist wie ein Schachspiel, bei dem man den nächsten Zug basierend nur auf dem aktuellen Brett vorhersagen kann. Man muss nicht die gesamte Spielhistorie im Kopf behalten, um die Regeln zu kennen. Die Autoren nennen dieses System AA. Es ist ein „Reduktionssystem", was bedeutet, dass es komplexe Probleme auf einfache herunterschrumpft.

2. Die „Jederzeit"-Regeln (Die unendliche Historie)

Stellen Sie sich nun vor, die Gruppe spricht seit Tagen. Alice hat 5 Nachrichten erhalten, Bob 3 und Charlie 7. Alle schauen auf verschiedene Teile des Drehbuchs.

Das Problem: Die „Frischer-Start"-Regeln funktionieren hier nicht. Man kann die Regeln nicht einfach vereinfachen, weil die Historie zu chaotisch ist. Alice könnte etwas wissen, was Bob nicht weiß, einfach weil sie eine Nachricht erhalten hat, die er noch nicht gesehen hat.
Die neue Regel: Die Autoren haben ein neues, viel komplexeres Regelwerk namens AA* erstellt.
Der Haken: Dieses Regelwerk ist unendlich groß. Man kann die komplexen Sätze nicht mehr auf einfache herunterschrumpfen. Man muss akzeptieren, dass einige Regeln einfach zu kompliziert sind, um sie zu vereinfachen.
Die „Leere"-Prüfung: Um dies funktionsfähig zu machen, erfanden sie einen speziellen „magischen Check" namens empty. Dieser Check fragt: „Ist das Drehbuch gerade völlig blank?"
- Wenn die Antwort JA ist, können wir die einfachen Regeln verwenden.
- Wenn die Antwort NEIN ist (was normalerweise der Fall ist, mitten in einem Gespräch), müssen wir die komplexen, unendlichen Regeln verwenden.

Warum ist das schwierig? (Das „Eine-Person"-Problem)

Der Artikel stößt an eine Wand, wenn sich nur eine Person in der Gruppe befindet.

Die Metapher: Stellen Sie sich vor, Alice ist die einzige Person im Universum. Sie sendet eine Nachricht an sich selbst.
Das Problem: In einer Gruppe weiß Alice, dass sie eine Nachricht nicht erhalten hat, weil sie sie nicht gesehen hat, und sie weiß, dass Bob sie vielleicht erhalten hat. Aber wenn Alice allein ist, kann sie nicht unterscheiden zwischen „Ich habe eine Nachricht nicht erhalten" und „Es wurde nie eine Nachricht gesendet".
Das Ergebnis: Die Autoren geben zu, dass sie das Regelwerk für eine einzelne Person noch nicht lösen konnten. Der Trick, den sie für Gruppen verwendeten (prüfen, ob alle wissen, dass die Historie leer ist), funktioniert nicht, wenn es nur eine Person gibt. Sie sagen: „Wir werden dafür eine neue Methode benötigen, vielleicht später."

Der „Drei-Wert"-Twist

Der Artikel erwähnt etwas Interessantes über „Wahrheit".

In der normalen Logik ist eine Aussage entweder Wahr oder Falsch.
In dieser asynchronen Welt kann eine Aussage Undefiniert sein.
Die Analogie: Stellen Sie sich vor, Alice wartet auf ein Paket.
- Wenn das Paket ankommt, ist die Aussage „Ich habe das Paket" Wahr.
- Wenn das Paket verloren geht, ist es Falsch.
- Aber wenn das Paket in Transit ist und sie nicht weiß, ob es kommt oder weg ist, ist die Aussage Undefiniert.
Die Logik der Autoren geht sorgfältig mit diesem „Undefinierten"-Zustand um. Es ist nicht nur ein Fehler; es ist ein fundamentaler Bestandteil davon, wie asynchrones Wissen funktioniert.

Zusammenfassung

Dieser Artikel ist ein mathematischer Versuch, das zu kartieren, was Sie wissen, wenn Sie nicht wissen, was andere wissen, und Sie nicht wissen, wann sie ihre Informationen erhalten haben.

Wenn Sie frisch beginnen: Können Sie die Regeln vereinfachen.
Wenn Sie mitten in einem chaotischen Gespräch stecken: Benötigen Sie einen massiven, unendlichen Satz von Regeln, die nicht vereinfacht werden können.
Wenn Sie allein sind: Brechen die aktuellen Regeln zusammen, und wir brauchen neue Ideen.

Die Autoren haben erfolgreich das „Unendliche Regelwerk" (AA*) für Gruppen erstellt und bewiesen, dass wir selbst in einer chaotischen, asynchronen Welt, in der Nachrichten zu unterschiedlichen Zeiten eintreffen, logisch beschreiben können, was jeder weiß.

1. Problemstellung

Das Paper adressiert die Herausforderung, asynchrone Kommunikation in Multi-Agenten-Systemen unter Verwendung der Dynamischen Epistemischen Logik (DEL) zu modellieren.

Die Lücke: Die Standard-DEL (z. B. Public Announcement Logic) behandelt Kommunikation als instantan und synchronisiert: Eine Nachricht wird gesendet und von allen Agenten gleichzeitig empfangen. Dies erfasst reale verteilte Systeme nicht, bei denen Senden und Empfangen distincte Ereignisse sind, die zu unterschiedlichen Zeitpunkten stattfinden.
Die spezifische Herausforderung: Die Autoren zielen darauf ab, eine Logik zu formalisieren, in der:
1. Agenten temporale Unsicherheit bezüglich der Historie der Nachrichten haben (sie wissen nicht, wie viele Nachrichten andere empfangen haben).
2. Agenten epistemische Unsicherheit bezüglich des Zustands der Welt haben.
3. Die Logik zwischen dem Senden einer Nachricht (Broadcast) und dem Empfangen einer Nachricht (individuelle Aktion) unterscheiden muss.
4. Das System Gültigkeit in zwei Kontexten behandeln muss:
  - $\epsilon$ -Gültigkeit: Wahrheit im Anfangszustand (leere Historie).
  - $\ast$ -Gültigkeit (Immer-Gültigkeit): Wahrheit in jedem Zustand unter Berücksichtigung jeder vorherigen Historie des Sendens und Empfangens.

Vorherige Arbeiten (insbesondere Referenz [4]) lieferten eine Axiomatisierung ($AA $) für$ \epsilon$-Gültigkeiten unter Verwendung eines Reduktionssystems (Reduktion dynamischer Modaloperatoren auf statische epistemische). Dieser Reduktionsansatz versagt jedoch bei $\ast$ -Gültigkeiten, da sich die Eigenschaften des Systems fundamental ändern, sobald eine Historie existiert (z. B. können Agenten unterschiedliche Anzahlen von Nachrichten empfangen haben).

2. Methodik

2.1 Sprache und Syntax

Die Autoren definieren eine Sprache $\mathcal{L}$ , die die Multi-Agenten-Modallogik um zwei Arten dynamischer Modaloperatoren erweitert:

Broadcasting: $\langle \varphi \rangle \psi$ (Die Formel $\varphi$ wird angekündigt/broadcastet; subsequently gilt $\psi$ ).
Empfangen: $\langle a \rangle \psi$ (Agent $a$ empfängt die nächste Nachricht in seiner Warteschlange; subsequently gilt $\psi$ ).
Historie-Wörter: Sequenzen von Agenten und Formeln (z. B. $p.a.q$ ) repräsentieren die Sequenz von Ereignissen. Eine Historie ist ein Wort, bei dem für jeden Agenten die Anzahl der empfangenen Nachrichten die Anzahl der gesendeten Nachrichten niemals überschreitet (FIFO-Bedingung).

2.2 Semantik

Die Semantik wird über Paare $(s, \alpha)$ definiert, wobei $s$ ein Zustand in einem Kripke-Modell und $\alpha$ ein Historie-Wort ist.

Ausführbarkeit ( $\triangleright\triangleleft$ ): Eine Relation, die bestimmt, ob eine Historie $\alpha$ $α$ in einem Zustand $s$ $s$ ausführbar ist. Dies stellt sicher, dass:
1. Die Historie eine gültige Sequenz ist (FIFO).
2. Alle angekündigten Formeln zum Zeitpunkt ihres Broadcasts wahr waren.
3. Agenten nur Historien als ausführbar in Zuständen betrachten, die sie für möglich halten.
Sicht-Relation ( $\triangleright_a$ ): Definiert, was Agent $a$ für möglich hält. Agent $a$ hält eine Historie $\beta$ relativ zur tatsächlichen Historie $\alpha$ für möglich, wenn die Sequenz der Nachrichten, die $a$ in $\beta$ empfangen hat, exakt mit dem übereinstimmt, was sie in $\alpha$ empfangen haben. Entscheidend ist, dass Agenten keine Historien mit Nachrichten imaginieren, die sie noch nicht empfangen haben.
Dreiwertiger Charakter: Die Semantik verhält sich gewissermaßen wie eine dreiwertige Logik. Wenn eine Historie in einem Zustand nicht ausführbar ist ( $s \not\triangleright\triangleleft \alpha$ ), sind Formeln in diesem Paar weder wahr noch falsch, obwohl die Logik Standard-Gültigkeiten beibehält.

2.3 Die „Leere" Formel

Eine zentrale technische Innovation ist die Definition einer Formel empty:
$\text{empty} := \bigwedge_{a \in A} [a]\bot \land \bigwedge_{a,b \in A} K_a [b]\bot$
Diese Formel charakterisiert den Zustand, in dem die Historie leer ist ( $\alpha = \epsilon$ ). Sie besagt, dass niemand Nachrichten empfangen hat und alle dies wissen. Dies ist nur in einem Multi-Agenten-Setting möglich ( $|A| \ge 2$ ).

3. Hauptbeiträge

3.1 Axiomatisierung $AA^*$

Der primäre Beitrag ist die Proposal von $AA^*$ , einer Axiomatisierung für $\ast$ -Gültigkeiten (Immer-Gültigkeiten).

Infinitärer Charakter: Im Gegensatz zum vorherigen reduktionsbasierten System $AA$ ist $AA^*$ infinitär. Es kann dynamische Modaloperatoren nicht auf statische reduzieren, da die Wahrheit von Formeln von der spezifischen Historie abhängt.
Die Regel $(R^*)$ : Das System enthält eine infinitäre Regel:
- Prämisse: Für alle Wörter $\alpha$ ist $\text{empty} \to [\alpha]\varphi$ ableitbar.
- Konklusion: $\varphi$ ist ableitbar.
  Diese Regel reduziert effektiv $\ast$ -Gültigkeit auf $\epsilon$ -Gültigkeit, indem sie die Historie über die Formel empty auf „leer" zurücksetzt.
Axiome: Das System enthält Axiome für:
- Verteilung von Wissen und dynamischen Modaloperatoren.
- Ausführbarkeitsbedingungen (z. B. kann eine Nachricht nur empfangen werden, wenn sie gesendet wurde).
- Atomare Permanenz (Wahrheitswerte von Atomen ändern sich nicht).
- Ein spezifisches Axiom für Wissen in asynchronen Settings: $\text{empty} \to (K_a \varphi \leftrightarrow ([\alpha]\bot \lor \bigvee_{\alpha \triangleright_a \beta} K_a [\beta]\varphi))$ .

3.2 Vollständigkeit und Korrektheit

Korrektheit: Die Autoren beweisen, dass jeder Theorem in $AA^*$ $\ast$ -gültig ist.
Vollständigkeit: Sie beweisen, dass jede $\ast$ -gültige Formel ein Theorem von $AA^*$ ist. Der Beweis verwendet eine kanonische Modellkonstruktion basierend auf maximal konsistenten Theorien. Eine signifikante technische Hürde bestand darin, die Zugänglichkeitsrelationen auf dem kanonischen Modell so zu definieren, dass sie Äquivalenzrelationen bilden, nur wenn sie auf Theorien eingeschränkt werden, die empty enthalten.

3.3 Die Einschränkung auf einen einzelnen Agenten

Das Paper zeigt rigoros, dass die vorgeschlagene Methode für einen einzelnen Agenten versagt.

In einem Single-Agenten-System weiß ein Agent immer, dass er alle Nachrichten empfangen hat, die er gesehen hat. Es gibt keine Formel, die empty entspricht und eine leere Historie von einer nicht-leeren Historie unterscheiden kann, in der der Agent alles empfangen hat.
Folglich ist die Reduktion von $\ast$ -Gültigkeit auf $\epsilon$ -Gültigkeit über empty im Single-Agenten-Fall unmöglich. Die Autoren lassen die Axiomatisierung für den Single-Agenten-Fall als offenes Problem.

4. Ergebnisse

Formales System: Eine vollständige und korrekte infinitäre Axiomatisierung ( $AA^*$ ) für asynchrone epistemische Logik mit separaten Senden/Empfangen-Modaloperatoren.
Reduktionsmechanismus: Eine neuartige Methode zur Behandlung von „Immer-Gültigkeit" durch die Verwendung der Formel empty, um die Logik wieder am Anfangszustand zu verankern und die Notwendigkeit eines endlichen Reduktionssystems zu umgehen.
Unterscheidung von S5: Die Logik erfüllt nicht global das Standard-S5-Wahrheitsaxiom ( $K_a \varphi \to \varphi$ ). Wissen ist nur faktisch, wenn der Agent weiß, dass die Historie leer ist. Andernfalls verhält sich der Modaloperator mehr wie „konsistente Überzeugung".
Vergleich mit Verteiltem Rechnen: Die Semantik stimmt mit dem Konzept der konsistenten Schnitte in verteilten Systemen überein, verfeinert es jedoch, indem sie Wahrheitsbedingungen (Ausführbarkeit) direkt in die Logik integriert und inkonsistente Zustände verhindert (z. B. den Empfang einer Nachricht vor dem Senden oder den Empfang einer falschen Ankündigung).

5. Bedeutung

Theoretischer Fortschritt: Diese Arbeit schließt die Lücke zwischen der Standard-Dynamischen Epistemischen Logik (die Synchronizität annimmt) und den Realitäten des verteilten Rechnens (Asynchronizität). Sie bietet den ersten rigorosen logischen Rahmen, der Senden und Empfangen als distincte, asynchrone Ereignisse mit separaten Modaloperatoren behandelt.
Behandlung temporaler Unsicherheit: Sie modelliert erfolgreich die spezifische Art von Unsicherheit, bei der Agenten unsicher über die Länge der Kommunikationshistorie relativ zu anderen sind, ein Szenario, das in Gossip-Protokollen und verteiltem Konsens üblich ist.
Methodische Innovation: Die Verwendung einer infinitären Regel ( $R^*$ ) kombiniert mit einer spezifischen „Reset"-Formel (empty) bietet eine neue Vorlage für die Axiomatisierung von Logiken, bei denen dynamische Eigenschaften nicht durch endliche Umformulierungen auf statische reduziert werden können.
Zukünftige Richtungen: Das Paper identifiziert klare Wege für zukünftige Forschung, einschließlich der Erweiterung der Logik auf Gruppenwissen (verteiltes Wissen), nicht-öffentliche Kommunikation und die Lösung des Axiomatisierungsproblems für den Single-Agenten-Fall.

Zusammenfassend etabliert das Paper eine robuste logische Grundlage für das Schließen über Wissen in asynchronen Umgebungen und beweist, dass, obwohl Standard-Reduktionstechniken versagen, ein sorgfältig konstruiertes infinitäres System die volle Komplexität asynchroner Nachrichtenübermittlung erfassen kann.