Propositional Gossip Protocols under Fair Schedulers
Authors: Joseph Livesey, Dominik Wojtczak
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Finally, we establish that checking the correctness of a given propositional protocol under a fair scheduler is a co NP-complete problem. We show exactly the same computational complexity but with modified proofs to account for the fairness constraints. Theorem 5. Checking if a given propositional gossip protocol agent-fairly or rule-fairly terminates is co NP-complete. |
| Researcher Affiliation | Academia | Joseph Livesey and Dominik Wojtczak University of Liverpool, UK {joseph.livesey, d.wojtczak}@liverpool.ac.uk |
| Pseudocode | No | The paper describes protocol rules using formal notation and natural language, but it does not include any clearly labeled 'Pseudocode' or 'Algorithm' blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve experiments with datasets, therefore no dataset access information is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve experiments with datasets, therefore no training/validation/test split information is provided. |
| Hardware Specification | No | As a theoretical paper, no specific hardware specifications for running experiments are mentioned. |
| Software Dependencies | No | As a theoretical paper, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or training configurations. |