Abstract
Gossip protocols deal with a group of communicating agents, each holding a private information, and
aim at arriving at a situation in which all the agents
know each other secrets. Distributed epistemic gossip protocols are particularly simple distributed programs that use formulas from an epistemic logic.
Recently, the implementability of these distributed
protocols was established (which means that the
evaluation of these formulas is decidable), and the
problems of their partial correctness and termination
were shown to be decidable, but their exact computational complexity was left open. We show that for
any monotonic type of calls the implementability
of a distributed epistemic gossip protocol is a P
NP
k -
complete problem, while the problems of its partial
correctness and termination are in coNPNP
.