Simple epistemic planning: generalised gossiping
This work addresses communication network design by generalizing gossip problems to include epistemic depth and negative constraints, offering insights for protocol optimization in distributed systems.
The paper extends the gossip problem to arbitrary epistemic depths, requiring agents to know not only all secrets but also that others know them, and provides optimal protocols for various communication settings. It also shows that testing protocol existence with negative goals is NP-complete, whereas it is polynomial-time for positive goals.
The gossip problem, in which information (known as secrets) must be shared among a certain number of agents using the minimum number of calls, is of interest in the conception of communication networks and protocols. We extend the gossip problem to arbitrary epistemic depths. For example, we may require not only that all agents know all secrets but also that all agents know that all agents know all secrets. We give optimal protocols for various versions of the generalised gossip problem, depending on the graph of communication links, in the case of two-way communications, one-way communications and parallel communication. We also study different variants which allow us to impose negative goals such as that certain agents must not know certain secrets. We show that in the presence of negative goals testing the existence of a successful protocol is NP-complete whereas this is always polynomial-time in the case of purely positive goals.