Open Problems in a Logic of Gossips

Apt, Krzysztof R and Wojtczak, Dominik ORCID: 0000-0001-5560-0546 (2019) Open Problems in a Logic of Gossips. Electronic Proceedings in Theoretical Computer Science, 297. pp. 1-18.

Text 1707.08734.pdf - Published version Download (205kB) | Preview

Abstract

Gossip protocols are programs used in a setting in which each agent holds a secret and the aim is to reach a situation in which all agents know all secrets. Such protocols rely on a point-to-point or group communication. Distributed epistemic gossip protocols use epistemic formulas in the component programs for the agents. The advantage of the use of epistemic logic is that the resulting protocols are very concise and amenable for a simple verification. Recently, we introduced a natural modal logic that allows one to express distributed epistemic gossip protocols and to reason about their correctness. We proved that the resulting protocols are implementable and that all aspects of their correctness, including termination, are decidable. To establish these results we showed that both the definition of semantics and of truth of the underlying logic are decidable. We also showed that the analogous results hold for an extension of this logic with the ‘common knowledge’ operator. However, several, often deceptively simple, questions about this logic and the corresponding gossip protocols remain open. The purpose of this paper is to list and elucidate these questions and provide for them an appropriate background information in the form of partial of related results.

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	19 Nov 2021 08:11
Last Modified:	18 Jan 2023 21:24
DOI:	10.4204/eptcs.297.1
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3143442