On the Computational Complexity of Gossip Protocols
On the Computational Complexity of Gossip Protocols
复制标题
关于 Gossip 协议的计算复杂性
DOI：
10.24963/ijcai.2017/106
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
D. Wojtczak
中科院分区：
文献类型：
--
作者：
K. Apt;Eryk Kopczynski;D. Wojtczak
Gossip协议处理一组通信代理，每个代理持有私人信息，并旨在达到所有代理都知道彼此秘密的情况。分布式认知八卦协议是使用认知逻辑公式的特别简单的分布式程序。最近，这些分布式协议的可实现性被建立（这意味着这些公式的评估是可判定的），并且它们的部分正确性和终止性问题被证明是可判定的，但它们的精确计算复杂性是开放的。我们证明了，对于任何单调类型的调用，分布式认知八卦协议的可实现性是P^{NP}_{||}-完全问题，而其部分正确性和可终止性问题属于coNP^{NP}.
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}.
八卦协议公平终止的可判定性
DOI：
10.29007/62s4
发表时间：
--
期刊：
--
影响因子：
--
作者：
Apt K
通讯作者：
Apt K
影响因子：
--
作者：
Apt K
通讯作者：
Apt K