Chennai Mathematical Institute


11.30 -- 12.30, Lecture Hall 1
Gossip Protocols and the Logic of Knowledge

Hans van Ditmarsch


A well-studied phenomenon in network theory since the 1970s are optimal schedules to distribute information by one-to-one communication between nodes. 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. Statistical approaches to gossip have taken a large flight since then. It is typical to assume a global scheduler who executes a possibly non-deterministic or randomized protocol. A departure from this methodology is to investigate distributed epistemic gossip protocols, where 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. The expected termination of such protocols may differ from that of non-epistemic or of globally scheduled protocols. This is also a function of the amount of information exchanged in a call, and of the epistemic goal of the protocol. A number of works have appeared over the past years or are in progress, of which we present a survey, including open problems yet to be solved by the community.


Hans van Ditmarsch is a senior researcher at CNRS (the French National Research Organization), and based at LORIA in Nancy, where he is heading the research team CELLO (Computational Epistemic Logic in LOrraine). From January to June 2018 he is working at ReLaX (Research Lab in Computer Science), Indo-French Research Unit, CNRS UMI 2000, in Chennai.