Livesey, J and Wojtczak, D 
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
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.
| Item Type: | Conference Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | 46 Information and Computing Sciences, 4602 Artificial Intelligence |
| Divisions: | Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 16 Jun 2022 13:41 |
| Last Modified: | 24 Jan 2026 03:43 |
| DOI: | 10.24963/ijcai.2022/56 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3156598 |
| Disclaimer: | The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate. |
Altmetric
Altmetric