Verification of Distributed Epistemic Gossip Protocols



Apt, Krzysztof and Wojtczak, Dominik
(2018) Verification of Distributed Epistemic Gossip Protocols. Journal of Artificial Intelligence Research, 62. pp. 101-133.

[thumbnail of aw18-elements.pdf] Text
aw18-elements.pdf - Author Accepted Manuscript

Download (518kB)

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. Distributed epistemic gossip protocols use as guards formulas from a simple epistemic logic and as statements calls between the agents. They are natural examples of knowledge based programs. We prove here that these protocols are implementable, that their partial correctness is decidable and that termination and two forms of fair termination of these protocols are decidable, as well. To establish these results we show that the definition of semantics and of truth of the underlying logic are decidable.

Item Type: Article
Uncontrolled Keywords: 4613 Theory Of Computation, 46 Information and Computing Sciences, 4602 Artificial Intelligence
Depositing User: Symplectic Admin
Date Deposited: 17 May 2018 06:25
Last Modified: 20 Jun 2024 20:24
DOI: 10.1613/jair.1.11204
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3021364