On the Computational Complexity of Gossip Protocols
Authors: Krzysztof R. Apt, Eryk Kopczyński, Dominik Wojtczak
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that for any monotonic type of calls the implementability of a distributed epistemic gossip protocol is a PNP complete problem, while the problems of its partial correctness and termination are in co NPNP. |
| Researcher Affiliation | Academia | Krzysztof R. Apt CWI, The Netherlands University of Warsaw, Poland apt@cwi.nl Eryk Kopczy nski University of Warsaw, Poland erykk@mimuw.edu.pl Dominik Wojtczak University of Liverpool, UK d.wojtczak@liv.ac.uk |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use any datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |