Reachability of Five Gossip Protocols

Van Ditmarsch, H., Gattinger, M., Kokkinis, I. & Kuijer, L. B., 6-Sep-2019, Reachability Problems: RP 2019: International Conference on Reachability Problems. Filiot, E., Jungers, R. & Potapov, I. (eds.). Cham: Springer, p. 218-231 14 p. (Lecture Notes in Computer Science; vol. 11674).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Copy link to clipboard



Gossip protocols use point-to-point communication to spread information within a network until every agent knows everything. Each agent starts with her own piece of information (‘secret’) and in each call two agents will exchange all secrets they currently know. Depending on the protocol, this leads to different distributions of secrets among the agents during its execution. We investigate which distributions of secrets are reachable when using several distributed epistemic gossip protocols from the literature. Surprisingly, a protocol may reach the distribution where all agents know all secrets, but not all other distributions. The five protocols we consider are called 햠햭햸, 햫햭햲, 햢햮, 햳햮햪, and 햲햯햨. We find that 햳햮햪 and 햠햭햸 reach the same distributions but all other protocols reach different sets of distributions, with some inclusions. Additionally, we show that all distributions are subreachable with all five protocols: any distribution can be reached, if there are enough additional agents.
Original languageEnglish
Title of host publicationReachability Problems
Subtitle of host publicationRP 2019: International Conference on Reachability Problems
EditorsEmmanuel Filiot, Raphaël Jungers, Igor Potapov
Place of PublicationCham
Number of pages14
ISBN (Electronic)978-3-030-30806-3
ISBN (Print)978-3-030-30805-6
Publication statusPublished - 6-Sep-2019

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


  • Gossip, Networks, Reachability

View graph of relations

Download statistics

No data available

ID: 97634595