Apt, Krzysztof R, Kopczyński, Eryk and Wojtczak, Dominik 
ORCID: 0000-0001-5560-0546
(2017)
On the Computational Complexity of Gossip Protocols.
In: Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017-8-19 - 2017-8-26.
Abstract
<jats:p>Gossip protocols deal with a group of communicating agents, each holding a private information, and aim at arriving at a situation in which all the agents know each other secrets. Distributed epistemic gossip protocols are particularly simple distributed programs that use formulas from an epistemic logic. Recently, the implementability of these distributed protocols was established (which means that the evaluation of these formulas is decidable), and the problems of their partial correctness and termination were shown to be decidable, but their exact computational complexity was left open. We show that for any monotonic type of calls the implementability of a distributed epistemic gossip protocol is a P^{NP}_{||}-complete problem, while the problems of its partial correctness and termination are in coNP^{NP}.</jats:p>
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Depositing User: | Symplectic Admin |
| Date Deposited: | 17 Jan 2019 08:51 |
| Last Modified: | 19 Jan 2023 01:06 |
| DOI: | 10.24963/ijcai.2017/106 |
| Open Access URL: | https://www.ijcai.org/proceedings/2017/0106.pdf |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3031320 |
Dimensions
Dimensions
