逸仙逻辑讲坛第一期预告 | Hans van Ditmarsch：Gossip and Knowledge

逸仙逻辑讲坛✦

     Hans van Ditmarsch is professor of artificial intelligence at Open University of the Netherlands. He has previously also been based at the Open University of the Netherlands, 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). He has also been associated researcher at Institute of Mathematical Sciences, Chennai, India, for many years. His PhD is from the University of Groningen. 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 and monograph Dynamic Epistemic Logic, an editor of the Handbook of Epistemic Logic, and an author of the logic puzzles book One Hundred Prisoners and a Light Bulb. He has been the recipient of an ERC (European Research Council) starting grant Epistemic Protocol Synthesis. 

     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.