💻 computer science

Axiomatisation for an asynchronous epistemic logic with sending and receiving messages

Dit artikel stelt een infinitaire axiomatisatie, AA*, voor voor een asynchrone epistemische logica die rekening houdt met willekeurige geschiedenissen van het verzenden en ontvangen van berichten, en die eerder werk generaliseert door de aanpak van reductiesystemen en de aanname dat geen berichten zijn ontvangen, te verlaten.

Oorspronkelijke auteurs: Philippe Balbiani, Hans van Ditmarsch, Clara Lerouvillois

Gepubliceerd 2026-04-29

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Philippe Balbiani, Hans van Ditmarsch, Clara Lerouvillois

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een groep vrienden voor die een mysterie proberen op te lossen, maar die communiceren via een zeer vreemde, defecte berichtenapp. Deze app heeft twee duidelijke problemen:

De knop "Verzenden" en de knop "Ontvangen" bevinden zich op verschillende planeten. Het feit dat Alice op "verzenden" drukt, betekent niet dat Bob het bericht direct ontvangt. In feite kan het uren duren voordat Bob het ontvangt, of hij kan het ontvangen voordat Alice zelfs maar de volgende zin heeft getypt.
Iedereen raadt de tijdlijn. Alice weet niet of Bob haar bericht al heeft gelezen, of hij op het punt staat het te lezen, of hij zich volledig bewust is dat het bestaat. Ze weet ook niet of Bob andere berichten heeft ontvangen die zij nog niet heeft gezien.

Dit artikel gaat over het opstellen van een regelspel (een logica) om precies te beschrijven wat Alice weet in deze rommelige, asynchrone wereld.

Het Kernprobleem: De "Snapshot" versus de "Film"

In de meeste logische raadsels bevinden zich iedereen zich op hetzelfde moment op dezelfde pagina. Als Alice zegt "Het regent", hoort iedereen het direct. Dit is als het maken van een snapshot van een kamer; iedereen ziet hetzelfde beeld.

Maar in de echte wereld (en in computernetwerken) is communicatie een film.

Verzenden is als een regisseur die "Actie!" schreeuwt.
Ontvangen is als een acteur die de aanwijzing hoort.
De "geschiedenis" is het script van alles wat tot nu toe is gebeurd.

De auteurs, Philippe, Hans en Clara, vragen zich af: Hoe schrijven we een regelspel voor kennis wanneer het "script" (de geschiedenis van berichten) voor elke persoon anders is?

De Twee Soorten Regels die Ze Hebben Gemaakt

Het artikel stelt twee verschillende manieren voor om deze regels te schrijven, afhankelijk van hoe je naar het verhaal kijkt.

1. De "Nieuwe Start"-Regels (De Lege Geschiedenis)

Stel je voor dat de groep net kennis heeft gemaakt. Er zijn nog geen berichten verzonden. Het "script" is blanco.

De Regel: Als we vanaf nul beginnen, kunnen we de regels vereenvoudigen. We kunnen elke complexe zin over "wat er gebeurt nadat een bericht is verzonden" vertalen naar een simpele zin over "wat op dit moment waar is".
De Analogie: Het is als een schaakspel waarbij je de volgende zet kunt voorspellen op basis alleen van het huidige bord. Je hoeft niet de hele spelgeschiedenis te onthouden om de regels te kennen. De auteurs noemen dit systeem AA. Het is een "reductiesysteem", wat betekent dat het complexe problemen terugbrengt tot simpele problemen.

2. De "Elk Moment"-Regels (De Oneindige Geschiedenis)

Nu, stel je voor dat de groep al dagenlang praat. Alice heeft 5 berichten ontvangen, Bob heeft 3 ontvangen en Charlie heeft 7 ontvangen. Ze kijken allemaal naar verschillende delen van het script.

Het Probleem: De "Nieuwe Start"-regels werken hier niet. Je kunt de regels niet zomaar vereenvoudigen omdat de geschiedenis te rommelig is. Alice weet misschien iets wat Bob niet weet, simpelweg omdat zij een bericht heeft ontvangen dat hij nog niet heeft gezien.
De Nieuwe Regel: De auteurs hebben een nieuw, veel complexer regelspel bedacht dat AA* heet.
De Haken: Dit regelspel is oneindig groot. Je kunt de complexe zinnen niet meer terugbrengen tot simpele zinnen. Je moet accepteren dat sommige regels gewoon te ingewikkeld zijn om te vereenvoudigen.
De "Leeg"-Controle: Om dit werkbaar te maken, hebben ze een speciale "magische controle" bedacht die empty heet. Deze controle vraagt: "Is het script op dit moment volledig blanco?"
- Als het antwoord JA is, kunnen we de simpele regels gebruiken.
- Als het antwoord NEE is (wat meestal het geval is midden in een gesprek), moeten we de complexe, oneindige regels gebruiken.

Waarom is dit moeilijk? (Het "Eén Persoon"-Probleem)

Het artikel stuit op een muur wanneer er maar één persoon in de groep is.

De Metafoor: Stel je voor dat Alice de enige persoon in het universum is. Ze stuurt een bericht naar zichzelf.
Het Probleem: In een groep weet Alice dat ze een bericht niet heeft ontvangen omdat ze het niet heeft gezien, en ze weet dat Bob dat misschien wel heeft. Maar als Alice alleen is, kan ze niet onderscheiden tussen "Ik heb een bericht niet ontvangen" en "Er is nooit een bericht verzonden".
Het Resultaat: De auteurs geven toe dat ze het regelspel voor een enkele persoon nog niet hebben kunnen oplossen. De truc die ze gebruikten voor groepen (controleren of iedereen weet dat de geschiedenis leeg is) werkt niet meer als er maar één persoon is. Ze zeggen: "We hebben een nieuwe methode hiervoor nodig, misschien later."

De "Drie-Waardige" Twist

Het artikel noemt iets interessants over "waarheid".

In normale logica is een stelling ofwel Waar ofwel Onwaar.
In deze asynchrone wereld kan een stelling Ongedefinieerd zijn.
De Analogie: Stel je voor dat Alice op een pakket wacht.
- Als het pakket aankomt, is de stelling "Ik heb het pakket" Waar.
- Als het pakket verloren is gegaan, is het Onwaar.
- Maar als het pakket onderweg is en ze niet weet of het komt of verdwenen is, is de stelling Ongedefinieerd.
De logica van de auteurs gaat zorgvuldig om met deze "Ongedefinieerde" staat. Het is niet zomaar een fout; het is een fundamenteel onderdeel van hoe asynchrone kennis werkt.

Samenvatting

Dit artikel is een wiskundige poging om in kaart te brengen wat je weet wanneer je niet weet wat anderen weten, en je niet weet wanneer zij hun informatie hebben ontvangen.

Als je fris begint: Je kunt de regels vereenvoudigen.
Als je midden in een chaotisch gesprek zit: Je hebt een enorme, oneindige set regels nodig die niet kunnen worden vereenvoudigd.
Als je alleen bent: De huidige regels werken niet meer, en we hebben nieuwe ideeën nodig.

De auteurs hebben succesvol het "Oneindige Regelspel" (AA*) voor groepen gebouwd, en bewezen dat we zelfs in een chaotische, asynchrone wereld waar berichten op verschillende tijdstippen aankomen, nog steeds logisch kunnen beschrijven wat iedereen weet.

1. Probleemstelling

Het artikel adresseert de uitdaging om asynchrone communicatie in multi-agent systemen te modelleren met Dynamic Epistemic Logic (DEL).

Het Gat: Standaard DEL (bijvoorbeeld Public Announcement Logic) behandelt communicatie als onmiddellijk en gesynchroniseerd: een bericht wordt gelijktijdig verzonden en ontvangen door alle agenten. Dit faalt in het vastleggen van real-world gedistribueerde systemen waar verzenden en ontvangen distincte gebeurtenissen zijn die op verschillende tijdstippen plaatsvinden.
De Specifieke Uitdaging: De auteurs streven naar het formaliseren van een logica waarin:
1. Agenten temporale onzekerheid hebben over de geschiedenis van berichten (ze weten niet hoeveel berichten anderen hebben ontvangen).
2. Agenten epistemische onzekerheid hebben over de toestand van de wereld.
3. De logica onderscheidt tussen het verzenden van een bericht (broadcast) en het ontvangen van een bericht (individuele actie).
4. Het systeem validiteit moet hanteren in twee contexten:
  - $\epsilon$ -validiteit: Waarheid in de initiële toestand (lege geschiedenis).
  - $\ast$ -validiteit (Altijd-validiteit): Waarheid in elke toestand gegeven elke voorgaande geschiedenis van verzenden en ontvangen.

Vorig werk (specifiek referentie [4]) bood een axiomatisatie ($AA$) voor $\epsilon$ -validiteiten aan met een reductiesysteem (het reduceren van dynamische modaliteiten tot statische epistemische modaliteiten). Deze reductiebenadering faalt echter voor $\ast$ -validiteiten, omdat de eigenschappen van het systeem fundamenteel veranderen zodra er een geschiedenis bestaat (bijvoorbeeld: agenten kunnen een verschillend aantal berichten hebben ontvangen).

2. Methodologie

2.1 Taal en Syntaxis

De auteurs definiëren een taal $\mathcal{L}$ die multi-agent modale logica uitbreidt met twee soorten dynamische modaliteiten:

Broadcasting: $\langle \varphi \rangle \psi$ (De formule $\varphi$ wordt aangekondigd/broadcast; vervolgens geldt $\psi$ ).
Receiving: $\langle a \rangle \psi$ (Agent $a$ ontvangt het volgende bericht in zijn wachtrij; vervolgens geldt $\psi$ ).
Geschiedeniswoorden: Sequenties van agenten en formules (bijvoorbeeld $p.a.q$ ) representeren de reeks gebeurtenissen. Een geschiedenis is een woord waarbij, voor elke agent, het aantal ontvangen berichten nooit het aantal verzonden berichten overschrijdt (FIFO-beperking).

2.2 Semantiek

De semantiek wordt gedefinieerd over paren $(s, \alpha)$ , waarbij $s$ een toestand is in een Kripkemodel en $\alpha$ een geschiedeniswoord is.

Uitvoerbaarheid ( $\triangleright\triangleleft$ ): Een relatie die bepaalt of een geschiedenis $\alpha$ $α$ in toestand $s$ $s$ kan worden uitgevoerd. Dit zorgt ervoor dat:
1. De geschiedenis een geldige reeks is (FIFO).
2. Alle aangekondigde formules waar waren op het moment van hun broadcast.
3. Agenten alleen geschiedenissen als uitvoerbaar beschouwen in toestanden die ze mogelijk achten.
Zichtrelatie ( $\triangleright_a$ ): Definieert wat agent $a$ mogelijk acht. Agent $a$ acht een geschiedenis $\beta$ mogelijk ten opzichte van de werkelijke geschiedenis $\alpha$ als de reeks berichten die $a$ in $\beta$ heeft ontvangen exact overeenkomt met wat ze in $\alpha$ hebben ontvangen. Cruciaal: agenten verbeelden geen geschiedenissen die berichten bevatten die ze nog niet hebben ontvangen.
Drie-waardige Smaak: De semantiek gedraagt zich enigszins als een drie-waardige logica. Als een geschiedenis niet uitvoerbaar is in een toestand ( $s \not\triangleright\triangleleft \alpha$ ), zijn formules in dat paar noch waar noch onwaar, hoewel de logica standaard validiteiten behoudt.

2.3 De "Lege" Formule

Een centrale technische innovatie is de definitie van een formule empty:
$\text{empty} := \bigwedge_{a \in A} [a]\bot \land \bigwedge_{a,b \in A} K_a [b]\bot$
Deze formule karakteriseert de toestand waarin de geschiedenis leeg is ( $\alpha = \epsilon$ ). Het stelt dat niemand berichten heeft ontvangen en dat iedereen dit weet. Dit is alleen mogelijk in een multi-agent setting ( $|A| \ge 2$ ).

3. Belangrijkste Bijdragen

3.1 Axiomatisatie $AA^*$

De primaire bijdrage is de voorstelling van $AA^*$ , een axiomatisatie voor $\ast$ -validiteiten (altijd-validiteiten).

Infinitaire Aard: In tegenstelling tot het eerdere op reductie gebaseerde systeem $AA$, is $AA^*$ infinitair. Het kan dynamische modaliteiten niet reduceren tot statische modaliteiten, omdat de waarheid van formules afhangt van de specifieke geschiedenis.
De Regel $(R^*)$ : Het systeem bevat een infinitaire regel:
- Premisse: Voor alle woorden $\alpha$ is $\text{empty} \to [\alpha]\varphi$ afleidbaar.
- Conclusie: $\varphi$ is afleidbaar.
  Deze regel reduceert $\ast$ -validiteit effectief tot $\epsilon$ -validiteit door de geschiedenis via de empty-formule te "resetten" naar leeg.
Axioma's: Het systeem bevat axioma's voor:
- Distributie van kennis en dynamische modaliteiten.
- Voorwaarden voor uitvoerbaarheid (bijvoorbeeld: een bericht kan alleen worden ontvangen als het is verzonden).
- Atomische permanentie (waarheidswaarden van atomen veranderen niet).
- Een specifiek axioma voor kennis in asynchrone settings: $\text{empty} \to (K_a \varphi \leftrightarrow ([\alpha]\bot \lor \bigvee_{\alpha \triangleright_a \beta} K_a [\beta]\varphi))$ .

3.2 volledigheid en Geluid

Geluid: De auteurs bewijzen dat elke stelling in $AA^*$ $\ast$ -valid is.
Volledigheid: Ze bewijzen dat elke $\ast$ -valid formule een stelling is van $AA^*$ . Het bewijs maakt gebruik van een canoniek modelconstructie gebaseerd op maximaal consistente theorieën. Een significante technische hindernis was het definiëren van de toegankelijkheidsrelaties op het canonieke model om ervoor te zorgen dat ze equivalentierelaties vormen alleen wanneer ze beperkt zijn tot theorieën die empty bevatten.

3.3 De Beperking tot Eén Agent

Het artikel demonstreert rigoureus dat de voorgestelde methode faalt voor één agent.

In een single-agent systeem weet een agent altijd dat ze alle berichten die ze hebben gezien, hebben ontvangen. Er is geen formule equivalent aan empty die een lege geschiedenis kan onderscheiden van een niet-lege geschiedenis waarin de agent alles heeft ontvangen.
Bijgevolg is de reductie van $\ast$ -validiteit tot $\epsilon$ -validiteit via empty onmogelijk in het single-agent geval. De auteurs laten de axiomatisatie voor het single-agent geval als een open probleem achter.

4. Resultaten

Formeel Systeem: Een volledige en geluidige infinitaire axiomatisatie ( $AA^*$ ) voor asynchrone epistemische logica met aparte verzend/ontvang-modaliteiten.
Reductiemechanisme: Een nieuwe methode om "altijd-validiteit" te hanteren door de empty-formule te gebruiken om de logica terug te ankeren bij de initiële toestand, waardoor de noodzaak voor een eindig reductiesysteem wordt omzeild.
Onderscheid met S5: De logica voldoet niet aan het standaard S5-waarheidaxioma ( $K_a \varphi \to \varphi$ ) globaal. Kennis is alleen feitelijk als de agent weet dat de geschiedenis leeg is. Anders gedraagt de modale operator zich meer als "consistent geloof".
Vergelijking met Gedistribueerd Rekenen: De semantiek sluit aan bij het concept van consistent cuts in gedistribueerde systemen, maar verfijnt dit door waarheidscondities (uitvoerbaarheid) direct in de logica op te nemen, waardoor inconsistente toestanden worden voorkomen (bijvoorbeeld: een bericht ontvangen voordat het is verzonden, of een onwaar aankondiging ontvangen).

5. Betekenis

Theoretische Vooruitgang: Dit werk overbrugt de kloof tussen standaard Dynamic Epistemic Logic (die synchronie aanneemt) en de realiteit van gedistribueerd rekenen (asynchronie). Het biedt het eerste rigoureuze logische kader dat verzenden en ontvangen behandelt als distincte, asynchrone gebeurtenissen met aparte modaliteiten.
Omgaan met Temporale Onzekerheid: Het modelleert succesvol het specifieke type onzekerheid waarbij agenten onzeker zijn over de lengte van de communicatiegeschiedenis ten opzichte van anderen, een scenario dat veel voorkomt in gossip-protocollen en gedistribueerde consensus.
Methodologische Innovatie: Het gebruik van een infinitaire regel ( $R^*$ ) gecombineerd met een specifieke "reset"-formule (empty) biedt een nieuw sjabloon voor het axiomatiseren van logica's waarbij dynamische eigenschappen niet via eindige herschrijving tot statische eigenschappen kunnen worden gereduceerd.
Toekomstige Richtingen: Het artikel identificeert duidelijke paden voor toekomstig onderzoek, waaronder het uitbreiden van de logica naar groepskennis (gedistribueerde kennis), niet-publieke communicatie, en het oplossen van het single-agent axiomatisatieprobleem.

Kortom, het artikel vestigt een robuuste logische basis voor redeneren over kennis in asynchrone omgevingen, en bewijst dat terwijl standaard reductietechnieken falen, een zorgvuldig geconstrueerd infinitair systeem de volledige complexiteit van asynchrone berichtenuitwisseling kan vastleggen.