Everyone Knows that Everyone Knows: Gossip Protocols for Super Experts
This work addresses the problem of achieving higher-order knowledge (common knowledge of expertise) in distributed networks, which is relevant for distributed systems and multi-agent coordination.
This paper explores gossip protocols where the termination condition is that all agents know that all agents are experts, rather than simply all agents being experts. It investigates these 'super expert' protocols under synchronous and asynchronous conditions, showing that protocols with engaged agents (super experts stop calling) can terminate faster.
A gossip protocol is a procedure for sharing secrets in a network. The basic action in a gossip protocol is a pairwise message exchange (telephone call) wherein the calling agents exchange all the secrets they know. An agent who knows all secrets is an expert. The usual termination condition is that all agents are experts. Instead, we explore protocols wherein the termination condition is that all agents know that all agents are experts. We call such agents super experts. We also investigate gossip protocols that are common knowledge among the agents. Additionally, we model that agents who are super experts do not make and do not answer calls, and that this is common knowledge. We investigate conditions under which protocols terminate, both in the synchronous case, where there is a global clock, and in the asynchronous case, where there is not. We show that a commonly known protocol with engaged agents may terminate faster than the same commonly known protocol without engaged agents.