Knowledge and Gossip (ESSLLI 2022)

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.

Monday

Slides: [Part 1] [Part 2]

• Introduction to 'classic', distributed, epistemic and dynamic gossip
• ElmGossip: graphs, calls, simple protocols

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

• Brenda Baker and Robert Shostak: Gossips and Telephones, Discrete Mathematics 2 (1972), 191-193.
• R. Tijdeman: On A Telephone Problem, Nieuw Archief voor Wiskunde (3), XIX (1971), 188-192.
• A. Hajnal, E. C. Milner and E. Szemerédi: A Cure For The Telephone Disease, Canad. Math. Bull. 15 (1972), 447–450.

Software:

• Ramon Meffert: ElmGossip: Explore dynamic gossip in your browser, 2021. [CODE] [Try it!]

Tuesday

Slides: [Part 1] [Part 2]

• Gossip terminology, parameters and variants
• Epistemic and distributed protocol conditions
• Gossip Model Checking with GoMoChe
• Checking simple gossip protocols in GoMoChe

References:

• Hans van Ditmarsch, Wiebe van der Hoek, Louwe B. Kuijer: The logic of gossiping, Artificial Intelligence, Volume 286, 2020. [DOI]
• Malvin Gattinger: GoMoChe: Gossip Model Checking, Upcoming talk at LAMAS&SR 2022. [PDF]

Software:

• Malvin Gattinger: GoMoChe. [CODE] [Try it!]

Wednesday

Slides: [Part 1] [Part 2]

• Success notions
• Dynamic gossip
• Characterization of successfull protocol termination in dynamic gossip.
• Sun graphs and LNS success in ElmGossip and GoMoChe
• Generation of execution trees in GoMoChe

References:

• Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber: Epistemic protocols for dynamic gossip. Applied Logic, Volume 20, 2017. [PDF] [DOI]
• Hans van Ditmarsch, Ioannis Kokkinis, Anders Stockmarr: Reachability and Expectation in Gossiping. PRIMA 2017. [PDF] [DOI] [CODE]
• Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber: Dynamic Gossip. Bulletin of the Iranian Mathematical Society, 45, 2019. [PDF] [DOI]

Thursday

[Slides]

• Common knowledge of the protocol
• Syntactic and Semantic Strengthening of gossip protocols
• Relation to Uniform Backward Induction
• Implementing strengthening in GoMoChe

References:

• Hans van Ditmarsch, Malvin Gattinger, Louwe B. Kuijer, Pere Pardo: Strengthening Gossip Protocols using Protocol-Dependent Knowledge. Applied Logics, 6 (1), 2019. [PDF]

Friday

Slides: [Part 1] [Part 2]

• Reachability of secret distributions
• Optimal and expected call sequence length at termination
• Reaching higher-order epistemic goals in gossip
• Unsatisfiability of higher-order knowledge
• There was no time for questions and discussion, but feel free to email us!

References:

• Hans van Ditmarsch, Malvin Gattinger, Ioannis Kokkinis, Louwe B. Kuijer: Reachability of Five Gossip Protocols. RP2019 [PDF] [DOI]
• Hans van Ditmarsch, Malvin Gattinger, Rahim Ramezanian: Everyone Knows that Everyone Knows: Gossip Protocols for Super Experts. Manuscript. [PDF]
• Hans van Ditmarsch and Malvin Gattinger: The Limits to Gossip: Second-order Shared Knowledge of all Secrets is Unsatisfiable, WoLLIC 2022, to appear. [PDF]