LIRa session: Sergio Rajsbaum

Speaker: Sergio Rajsbaum (Instituto de Matemáticas, UNAM, Mexico City)

Date and Time: Thursday, May 11th 2017, 15:30-17:00

Venue: KdVI Seminar Room F3.20, Science Park 107.

Title: A simplicial complex model of dynamic epistemic logic for fault-tolerant distributed computing.

Joint work with Eric Goubault (Ecole Polytechnique).

Abstract. The usual epistemic S5 model for multi-agent systems is a Kripke graph, whose edges are labeled with the agents that do not distinguish between two states. We propose to uncover the higher dimensional information implicit in the Kripke graph, by using as a model its dual, a chromatic simplicial complex. For each state of the Kripke model there is a facet in the complex, with one vertex per agent. If an edge $(u,v)$ is labeled with a set of agents $S$ , the facets corresponding to $u$ and $v$ intersect in a simplex consisting of one vertex for each agent of $S$ . Then we use dynamic epistemic logic to study how the simplicial complex epistemic model changes after the agents communicate with each other. We show that there are topological invariants preserved from the initial epistemic complex to the epistemic complex after an action model is applied, that depend on how reliable the communication is. In turn, these topological properties determine the knowledge that the agents may gain after the communication happens.
We choose distributed computing as a case study to work out in detail the dynamic epistemic simplicial complex theory. The reason is that distributed computability has been studied using combinatorial topology, where the set of all possible executions in a distributed system is represented by a simplicial complex. We establish a formal, categorical equivalence between Kripke models and simplicial complex epistemic models.
In one direction, the connection provides a dynamic epistemic logic semantics to distributed computability, opening the possibility of reasoning about knowledge change in distributed computing. In the other direction, the connection allows to bring in the topological invariants known in distributed computing, to dynamic epistemic logic, and in particular show that knowledge gained after an epistemic action model is intimately related to higher dimensional topological properties.