Speaker: Krzysztof Apt
Date and Time: Thursday, December 6th 2018, 17:00-18:30
Venue: ILLC Seminar Room F1.15, Science Park 107.
Title: The logic of gossiping.
Abstract. Gossip protocols are concerned with the spread of knowledge in a social network. They aim at arriving at a situation in which all agents know each other secrets. Recently distributed epistemic gossip protocols were introduced that employ epistemic logic (for instance in statements such as ‘if I do not know whether agent i knows my secret I communicate it to him’). To discuss such protocols we developed a simple epistemic logic that allows us to express statements like ‘agent a knows that agent b is familiar with the secret of agent c.’ An analysis of such statements is surprisingly subtle.
We show that the semantics and truth relation of this logic are decidable, which is relevant for the correctness study of the gossip protocols. Also, we discuss an extension allowing one to express common knowledge. Many questions remain open, notably sound and complete axiomatization. Further, there are several types of communication between pairs of agents, each resulting in a different notion of knowledge.
The talk is based on joint works with Davide Grossi, Wiebe van der Hoek, and Dominik Wojtczak.