Livesey, Joseph and Wojtczak, Dominik 
ORCID: 0000-0001-5560-0546
(2021)
Minimal Number of Calls in Propositional Protocols.
.
|
Text
Joe_Gossip_Paper.pdf - Author Accepted Manuscript Download (298kB) | Preview |
Abstract
Gossip protocols are programs that can be used by a group of agents to synchronise what information they have. Namely, assuming each agent holds a secret, the goal of a protocol is to reach a situation in which all agents are experts, i.e., know all secrets. Distributed epistemic gossip protocols use epistemic formulas in the component programs for the agents. In this paper, we investigate in-depth one of the simplest classes of such gossip protocols: propositional gossip protocols, in which whether an agent wants to initiate a call depends only the set of secrets that the agent currently knows. We establish important properties about the order of calls possible in a correct propositional gossip protocol, i.e., a one that terminates in the desired all-expert state. This allows us to solve the following open problem: all correct propositional gossip protocols for n≥ 4 agents require at least 2 n- 2 calls in the worst case.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | timestamp: Wed, 03 Nov 2021 08:28:17 +0100 biburl: https://dblp.org/rec/conf/rp/LiveseyW21.bib bibsource: dblp computer science bibliography, https://dblp.org |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 19 Nov 2021 08:14 |
| Last Modified: | 18 Jan 2023 21:24 |
| DOI: | 10.1007/978-3-030-89716-1_9 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3143441 |
Dimensions
Dimensions
