Robustness of Epistemic Gossip Protocols Against Data Loss

The gossip problem seeks to determine the minimum number of calls required for all agents in a network to share their secrets. To address this problem in a distributed manner, epistemic gossip protocols have been proposed, where each agent decides whom to call based on their knowledge. While extensive research has explored the feasibility of information dissemination under various protocols and environmental conditions, a recent study introduced a model that assumes the presence of unreliable agents. In this model, when an agent fails, it loses both the secrets and telephone numbers obtained from previous calls and returns to its initial state. In this context, the robustness of some existing protocols against data loss due to failures, as well as a sufficient condition for agents to detect failures, has been demonstrated. The objective of this paper is to complement the previous study through a comprehensive analysis and to explore methods for designing robust epistemic gossip protocols. Our contributions are threefold. First, we clarify the necessary and sufficient conditions regarding network structure for existing protocols to succeed (i.e., for all agents to know all secrets) at different levels. Second, we elucidate the necessary and sufficient conditions for failure detection. Finally, we present protocols in which agents, upon detecting their own or others' failures, take actions to recover the lost data and analyze the robustness of these protocols.