Livesey, Joseph and Wojtczak, Dominik 
ORCID: 0000-0001-5560-0546
(2022)
Propositional Gossip Protocols under Fair Schedulers.
In: Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}, 2022-7-23 - 2022-7-29.
|
Text
final-2205211403.pdf - Author Accepted Manuscript Download (252kB) | Preview |
Abstract
<jats:p>Gossip protocols are programs that can be used by a group of agents to synchronize 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 know all secrets. Distributed epistemic gossip protocols use epistemic formulas in the component programs for the agents. In this paper, we study the simplest classes of such gossip protocols: propositional gossip protocols, in which whether an agent wants to initiate a call depends only on the set of secrets that the agent currently knows. It was recently shown that such a protocol can be correct, i.e., always terminates in a state where all agents know all secrets, only when its communication graph is complete. We show here that this characterization dramatically changes when the usual fairness constraints are imposed on the call scheduler used. Finally, we establish that checking the correctness of a given propositional protocol under a fair scheduler is a coNP-complete problem.</jats:p>
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 16 Jun 2022 13:41 |
| Last Modified: | 15 Mar 2024 03:32 |
| DOI: | 10.24963/ijcai.2022/56 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3156598 |
Dimensions
Dimensions
