Reachability of Five Gossip ProtocolsVan 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 proceeding › Chapter › Academic › peer-review
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.
|Title of host publication||Reachability Problems|
|Subtitle of host publication||RP 2019: International Conference on Reachability Problems|
|Editors||Emmanuel Filiot, Raphaël Jungers, Igor Potapov|
|Place of Publication||Cham|
|Number of pages||14|
|Publication status||Published - 6-Sep-2019|
|Name||Lecture Notes in Computer Science|
- Gossip, Networks, Reachability
No data available