Reasoning about Gossip
http://reasoningaboutgossip.eu
Gossip protocols are peer-to-peer communication protocols with the intent to maximize information dissemination among processes or agents while respecting network or transmission constraints. The subject of gossip protocols has been a standard feature in the networks and combinatorics community since the 1970s. From, roughly, the 1990s onward this topic has also become standard in the area of distributed computing. Since around the mid 2010s epistemic distributed versions of such protocols have been investigated. They focus on information-based (epistemic) choice for agents to communicate with other network nodes (agents) in order to speed up information dissemination. The subject thus became ever more rooted in distributed computing but including an intersection with epistemic logic and its dynamics. Smarter and more involved forms of communication, apart from messaging (to one agent), broadcasting (to all agent), and multi-casting (to some agents), seem to require ever more involved epistemic forms of analysis. 'Reasoning about gossip' provides an overview of the state of the art while simultaneously presenting the material in textbook fashion, including exercises and answers to exercises.
This textbook / monograph will appear in the series Cambridge Tracts in Theoretical Computer Science of Cambridge University Press. The publication date is not known yet. Versions of chapters can no longer be downloaded as the book is now in press. Note that all materials are copyright by the author Hans van Ditmarsch.
In due time on this website will also appear: a link to the publisher's site for Reasoning about Gossip, answers to selected exercises in the book, and slide presentations for individual chapters in pdf format.
Table of contents
Preface
1. Introduction
2. Call
3. Gossip protocol
4. Reachability
5. Dynamic gossip
6. Optimality
7. Epistemic logic
8. Knowledge of gossip protocols
9. Epistemic goals
10. Update
11. Axiomatization
12. Outlook
References