Reachability of Five Gossip Protocols



van Ditmarsch, Hans ORCID: 0000-0003-4526-8687, Gattinger, Malvin ORCID: 0000-0002-2498-5073, Kokkinis, Ioannis ORCID: 0000-0001-7521-0553 and Kuijer, Louwe B ORCID: 0000-0001-6696-9023
(2019) Reachability of Five Gossip Protocols. In: 13th International Conference on Reachability Problems (RP19).

[img] Text
Reachability_in_Sequential_and_Parallel_Gossip(1).pdf - Author Accepted Manuscript

Download (321kB) | Preview

Abstract

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 ANY, LNS, CO, TOK, and SPI. We find that TOK and ANY 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.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 30 Jul 2019 09:10
Last Modified: 04 Mar 2024 09:17
DOI: 10.1007/978-3-030-30806-3_17
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3050607