Minimal Number of Calls in Propositional Protocols



Livesey, Joseph and Wojtczak, Dominik
(2021) Minimal Number of Calls in Propositional Protocols. .

[thumbnail of Joe_Gossip_Paper.pdf] 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
Uncontrolled Keywords: 46 Information and Computing Sciences, 4602 Artificial Intelligence
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: 20 Jun 2024 20:24
DOI: 10.1007/978-3-030-89716-1_9
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3143441