Reasoning about Gossip

TITLE
Reasoning about Gossip

ABSTRACT
A well-studied phenomenon in network theory since the 1970s are optimal schedules to distribute information by one-to-one communication between nodes that are connected in the network. One can take these communicative actions to be telephone calls, and protocols to spread information this way are known as gossip protocols or epidemic protocols. A common abstraction is to call the information of each agent its secret, and that the goal of information dissemination is that all agents know all secrets: that is the termination condition of gossip protocols. Following investigations assuming a global scheduler, it is now typically assumed that gossip protocols are distributed in some way, where the only role of the environment is to ensure randomization. Statistical approaches to gossip have taken a large flight since then, wherein network topology is an important parameter.

In epistemic gossip protocols, an agent (node) will call another agent not because it is so instructed by a scheduler, or at random, but based on its knowledge or ignorance of the distribution of secrets over the network and of other agents’ knowledge or ignorance of that. One such protocol requires that an agent may only call another agent if it does not know the other agent’s secret. Epistemic features of gossip protocols may affect their termination, the (order of complexity) expectation of termination, their reachability (what distributions of secrets may occur before all agents know all secrets), and so on. Variations involve agents exchanging telephone numbers in addition to agents exchanging secrets (which results in network expansion), or agents exchanging knowledge about secrets; we may also assume common knowledge of the protocol; further generalizations would involve multi-casts. We present a survey of distributed epistemic gossip protocols.

BIO
Hans van Ditmarsch is professor of artificial intelligence at Open University of the Netherlands. He has previously also been based at the OU, and at the University of Groningen, the University of Otago, the University of Aberdeen, the University of Sevilla, and CNRS (the University of Lorraine / LORIA). For many years he has been associated researcher at Institute of Mathematical Sciences, Chennai, India. His research is on the dynamics of knowledge and belief, information-based security protocols, modal logics, and combinatorics. He has frequently taught at ESSLLI summer schools, and he was an organizer or chair of events such as LOFT, M4M, ESSLLI, Tools for Teaching Logic, and LORI. He has been an editor of the Journal of Philosophical Logic. He is an author of the textbook Dynamic Epistemic Logic, an editor of the Handbook of Epistemic Logic, and an author of the puzzlebook One Hundred Prisoners and a Light Bulb. He has been the recipient of an ERC (European Research Council) starting grant Epistemic Protocol Synthesis.