TY - GEN
T1 - A Dynamic Epistemic Logic Analysis of the Equality Negation Task
AU - Goubault, Éric
AU - Lazić, Marijana
AU - Ledent, Jérémy
AU - Rajsbaum, Sergio
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - In this paper we study the solvability of the equality negation task in a simple wait-free model where processes communicate by reading and writing shared variables or exchanging messages. In this task, 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, Ledent and Rajsbaum in GandALF 2018. We show that in fact, there is no epistemic logic formula that explains why the task is unsolvable. We fix this issue by extending the language of our DEL framework, which allows us to construct such a formula, and discuss its utility.
AB - In this paper we study the solvability of the equality negation task in a simple wait-free model where processes communicate by reading and writing shared variables or exchanging messages. In this task, 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, Ledent and Rajsbaum in GandALF 2018. We show that in fact, there is no epistemic logic formula that explains why the task is unsolvable. We fix this issue by extending the language of our DEL framework, which allows us to construct such a formula, and discuss its utility.
KW - Distributed computing
KW - Dynamic epistemic logic
KW - Equality negation
U2 - 10.1007/978-3-030-38808-9_4
DO - 10.1007/978-3-030-38808-9_4
M3 - Conference contribution
AN - SCOPUS:85079087053
SN - 9783030388072
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 53
EP - 70
BT - Dynamic Logic. New Trends and Applications - 2nd International Workshop, DaLí 2019, Proceedings
A2 - Soares Barbosa, Luís
A2 - Baltag, Alexandru
PB - Springer
T2 - 2nd International Workshop on Dynamic Logic, DALI 2019
Y2 - 7 October 2019 through 11 October 2019
ER -