Authors
H.P. van Ditmarsch
B.R.M. Gattinger
Wouter J. Smit
Date (dd-mm-yyyy)
2025-07-30
Title
Completeness and Decidability of Protocol-Dependent Knowledge in Gossip
Publication Year
2025-07-30
Number of pages
16
Publisher
Springer
Document type
Conference contribution
Abstract
In the gossip problem, a group of agents aims to efficiently share information using one-to-one communication. This often occurs in decentralised systems, where agents must rely on protocols to efficiently coordinate their communication. Recent work has used epistemic logic to define gossip protocols, including protocol-dependent knowledge modalities: agent knowledge assuming common knowledge that all agents follow said protocol. While axiomatisations exist for various versions of the gossip problem, none of these include protocol-dependent knowledge. We show that protocol-dependent knowledge is strictly more expressive than standard knowledge, and we provide axiomatisations for four logics of gossip with protocol-dependent knowledge. We show that all four axiomatisations are sound and complete, as well as decidable.
Permalink
https://hdl.handle.net/11245.1/a24a6c5d-718a-4119-8d25-3a4cc07bea22