A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks

Hans van Ditmarsch, Éric Goubault, Marijana Lazić, Jérémy Ledent, Sergio Rajsbaum

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we study the solvability of the equality negation task in a simple wait-free model where two processes communicate by reading and writing shared variables or exchanging messages. In this task, the two processes start with a private input value in the set {0,1,2}, and after communicating, each one must decide a binary output value, so that the outputs of the processes are the same if and only if the input values of the processes are different. This task is already known to be unsolvable; our goal here is to prove this result using the dynamic epistemic logic (DEL) approach introduced by Goubault et al. (2018) [18]. We show that in fact, there is no epistemic logic formula that explains why the task is unsolvable. Furthermore, we observe that this task is a particular case of an epistemic covering task. We thus establish a connection between the existing DEL framework and the theory of covering spaces in topology, and prove that the same result holds for any epistemic covering task: no epistemic formula explains the unsolvability.
Original languageEnglish
Article number100662
Number of pages26
JournalJournal of Logical and Algebraic Methods in Programming
Volume121
Early online date4 Feb 2021
DOIs
Publication statusE-pub ahead of print - 4 Feb 2021

Keywords

  • dynamic epistemic logic
  • distributed computing
  • topology
  • simplicial complexes

Fingerprint Dive into the research topics of 'A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks'. Together they form a unique fingerprint.

Cite this