Apt, Krzysztof R, Kopczyński, Eryk and Wojtczak, Dominik
(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) |
---|---|
Uncontrolled Keywords: | 5003 Philosophy, 4606 Distributed Computing and Systems Software, 46 Information and Computing Sciences, 50 Philosophy and Religious Studies |
Depositing User: | Symplectic Admin |
Date Deposited: | 17 Jan 2019 08:51 |
Last Modified: | 20 Jun 2024 20:24 |
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 |