Knowledge and Gossip (ESSLLI 2022)

Instructors: Hans van Ditmarsch and Malvin Gattinger

Description

Gossip protocols facilitate peer-to-peer information sharing in possibly partial networks of agents. Each agent starts with some private information and the goal is to share this information among all agents. In distributed gossip protocols, there is no central processor or controller deciding who may call whom, but this is determined by independent pro-active agents and chance. In epistemic gossip protocols, knowledge conditions may restrict possible calls, for example you may not wish to call an agent who you know already to know your secret. In dynamic gossip, agents also exchange 'telephone numbers', which leads to network expansion.

This course gives a survey of results and methods in distributed epistemic gossip. Topics include constructing and revising gossip graphs, exhaustively enumerating call sequences, and model checking the conditions of protocols in suitable logics. We will present both the theory and implementations.

Schedule

Week 1 of ESSLLII 2022
Monday 8th - Friday 12th August
09:00-10:30
Room: AC204

Exercises

See this separate page. These exercises are meant for self-study — no model answers are provided. Feel free to ask other students or us, or use the software tools to verify your answers.

Additional Material

Hans van Ditmarsch: Reasoning about Gossip (book manuscript, selected parts)

Monday

Slides: [Part 1] [Part 2]

References (all in one PDF here, collected by Torsten Sillke):

Software:

Tuesday

Slides: [Part 1] [Part 2]

References:

Software:


Wednesday

Slides: [Part 1] [Part 2]

References:

Thursday

[Slides]

References:


Friday

Slides: [Part 1] [Part 2]

References: