On Decidability of a Logic of Gossips

Apt, Krzysztof R and Wojtczak, Dominik (2016) On Decidability of a Logic of Gossips. .

Text jelia16-final.pdf - Author Accepted Manuscript Download (231kB)

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, see, e.g., [11]. In [1], building upon [3], we studied distributed epistemic gossip protocols, which are examples of knowledge based programs introduced in [6]. These protocols use as guards formulas from a simple epistemic logic. We show here that these protocols are implementable by proving that it is decidable to determine whether a formula with no nested modalities is true after a sequence of calls. Building upon this result we further show that the problems of partial correctness and of termination of such protocols are decidable, as well.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	46 Information and Computing Sciences, 4602 Artificial Intelligence
Depositing User:	Symplectic Admin
Date Deposited:	20 Feb 2017 12:32
Last Modified:	20 Jun 2024 20:24
DOI:	10.1007/978-3-319-48758-8_2
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005460