Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

On the Computational Complexity of Gossip Protocols

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:50:26Z
dc.abstract.enGossip 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryNowa Zelandia
dc.conference.datefinish2017-08-25
dc.conference.datestart2017-08-19
dc.conference.placeMelbourne
dc.conference.seriesInternational Joint Conference on Artificial Intelligence
dc.conference.seriesInternational Joint Conference on Artificial Intelligence
dc.conference.seriesshortcutIJCAI
dc.conference.shortcutIJCAI 2017
dc.conference.weblinkhttp://ijcai-17.org/
dc.contributor.authorKopczyński, Eryk
dc.contributor.authorApt, Krzysztof
dc.contributor.authorWojtczak, Dominik
dc.date.accessioned2024-01-25T15:46:06Z
dc.date.available2024-01-25T15:46:06Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.identifier.doi10.24963/IJCAI.2017/106
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/114791
dc.pbn.affiliationcomputer and information sciences
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleOn the Computational Complexity of Gossip Protocols
dc.typeJournalArticle
dspace.entity.typePublication