Axiomatising Protocol-Dependent Knowledge in Gossip
Wouter Smit

Abstract:
The gossip problem is an information distribution problem where agents try to share information between each other in the most efficient way. While an optimal order of communication is easily computed, agents often find themselves in a decentralised system and therefore rely on gossip protocols for efficiently coordinating their communication. Protocol-dependent knowledge in epistemic logic expresses knowledge that an agent can deduce by assuming that a certain protocol is common knowledge. Protocol-dependent epistemic logic for the gossip problem has been studied semantically, but a sound and complete axiomatisation is yet to be found. While axiomatisations exist for various versions of the gossip problem, none of these include protocol-dependent knowledge.
In this thesis we provide a sound and complete axiomatisation for the logic of gossip with a single protocol-dependent knowledge modality and we further show that these axioms remain sound for the logic including multiple such modalities. In order to do so we analyse existing axiomatisations for non-protocol-dependent gossip and link them to existing semantic results, and we show that the language of gossip with multiple protocol modalities is considerably more expressive than the language without any such modalities.
These results aid in understanding the effects of protocols on agent knowledge in the gossip problem and provide insight in the effects of protocol-dependent knowledge modalities on expressivity of epistemic logic.