Common Knowledge in a Logic of Gossips

Apt, Krzysztof R and Wojtczak, Dominik ORCID: 0000-0001-5560-0546 (2017) Common Knowledge in a Logic of Gossips. ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 251 (251). pp. 10-27.

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

Official URL: http://dx.doi.org/10.4204/eptcs.251.2

Abstract

Gossip protocols aim at arriving, by means of point-to-point or group communications, at a situation in which all the agents know each other secrets. Recently a number of authors studied distributed epistemic gossip protocols. These protocols use as guards formulas from a simple epistemic logic, which makes their analysis and verification substantially easier. We study here common knowledge in the context of such a logic. First, we analyze when it can be reduced to iterated knowledge. Then we show that the semantics and truth for formulaswithout nested common knowledge operator are decidable. This implies that implementability, partial correctness and termination of distributed epistemic gossip protocols that use non-nested common knowledge operator is decidable, as well. Given that common knowledge is equivalent to an infinite conjunction of nested knowledge, these results are non-trivial generalizations of the corresponding decidability results for the original epistemic logic, established in [2].

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:10
Last Modified:	26 Jan 2023 00:11
DOI:	10.4204/EPTCS.251.2
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3143443