Abstract: In this talk I will present a ‘distributed’ variant of the so-called gossip problem. The problem concerns n agents. They all know one piece of information (a secret), which is unknown to the others, and they communicate by one-to-one interactions (e.g., telephone calls). After each interaction the two agents involved in it learn all secrets the other agent knows at the time of the call. The problem consists in finding sequences of calls (under different constraints, typically minimal length) which disseminate all the secrets among the agents in the group. It was widely investigated in the 70s and 80s.
The standard formulation of the problem assumes a centralized perspective: a planner finds a suitable sequence of calls and schedules agents’ calls accordingly. I will present the problem from a decentralized perspective: agents perform calls not according to a centralized schedule, but following individual epistemic protocols they run in a distributed fashion. These protocols tell the agents whom to call next depending on what they know, or do not know, about the information state of the other agents in the group. I will elaborate on this model as a useful abstraction to understand processes of information diffusion in groups.

The talk reports on joint work with Maduka Attamah (University of Liverpool), Wiebe van der Hoek (University of Liverpool), Hans van Ditmarsch (LORIA), Krzysztof Apt (CWI). This is work-in-progress and I will put emphasis on open problems and future directions of research.