Decidability of Fair Termination of Gossip Protocols

Gossip protocols deal with a group of communicating agents, each holding some 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 as guards formulas from an epistemic logic. We showed recently that the implementability of these distributed gossip protocols and the problems of their partial correctness and termination are decidable, but the problem of decidability of their fair termination was left open. We study here rule-fair and agent-fair termination of these protocols and show that both properties are decidable.