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

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

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

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 , 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). 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.

Domaines: Informatique [cs]

Hans van Ditmarsch, Éric Goubault, Marijana Lazić, Jérémy Ledent, Sergio Rajsbaum. A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks. Journal of Logical and Algebraic Methods in Programming, 2021, 121, pp.100662. ⟨10.1016/j.jlamp.2021.100662⟩. ⟨hal-04451568⟩