From Complex to Simple

All my working life as a logician epistemic logic came with Kripke models, in particular the kind for multiple agents with equivalence relations to interpret knowledge. Sure enough, I knew about enriched Kripke models, like subset spaces, or with topologies. But at some level of abstraction you get back your standard Kripke model. Imagine my surprise, around 2018, that there is an entirely dual sort of structure on which the epistemic logical language can be interpreted and that results in the same S5 logic: simplicial complexes. Instead of points that are worlds and links labeled with agents, we now have points that are agents and links labeled with worlds. Or, instead of edges (links), triangles, tetrahedrons, etcetera, that represent worlds. Simplicial complexes are well-known within combinatorial topology and have wide usage in distributed systems to model (a)synchronous computation. The link with epistemic modal logic is recent, spreading out from Mexico City and Paris to other parts of the world, like Vienna and Bern. Other logics are relevant too, for example KB4, in order to encode crashed processes/agents. Other epistemics are relevant too, and in particular distributed knowledge, which facilitates further generalizations from simplicial complexes to simplicial sets. It will be my pleasure to present my infatuation with this novel development connecting epistemic logic and distributed computing. Suggested introductory reading is:

https://arxiv.org/abs/2002.08863

https://link.springer.com/chapter/10.1007/978-3-030-75267-5_1

Knowledge and Simplicial Complexes

Hans van Ditmarsch, Eric Goubault, Jeremy Ledent, Sergio Rajsbaum

https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.7.34

Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)

Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, Ulrich Schmid

Section 4.3 Representing Epistemic Attitudes via Simplicial Complexes

Recently, much work has been carried out to study simplicial interpretations of modal logic. While notions of (distributed) knowledge have been well investigated in this context, it has been open how to model belief in simplicial models. We introduce polychromatic simplicial complexes, which naturally impose a plausibility relation on states. From this, we can define various notions of belief. In the end, we will also motivate ongoing work that relates polychromatic models to neighborhood semantics.

Pure simplicial complexes are a categorically dual semantics for epistemic logic that focuses on local rather than global states. This alternative focus is especially useful when applied to distributed systems where agents' local views determine their behavior. For instance, crashed agents can be easily and naturally represented by impure simplicial complexes. In view of this, it is desirable to establish independent methods of proving completeness that do not go through Kripke models via a back-and-forth translation. In this talk, we show how to perform a canonical model construction directly for simplicial complexes.

Reference:  doi.org/10.46298/lmcs-19(4:3)2023 

As an alternative to Kripke models, simplicial complexes are a versatile semantic primitive on which to interpret epistemic logic. Given a set of vertices, a simplicial complex is a downward closed set of subsets, called simplexes, of the vertex set. A maximal simplex is called a facet. Impure simplicial complexes represent that some agents (processes) are dead. It is known that impure simplicial complexes categorically correspond to so-called partial epistemic (Kripke) models. In my talk, I will present our results on bisimulation for impure simplicial complexes. 

Reference: https://doi.org/10.48550/arXiv.2406.16785

In the vast majority of contributions to multi-agent epistemic, doxastic, and coalition logic, a group is reduced to its extension, i.e., the set of its members. Membership in groups is common knowledge to all agents, with the counterintuitive consequence that groups change identity when their membership changes, and it precludes uncertainty about who is a member of a given group. This idealisation does not reflect the structure of groups or the structured way in which collective epistemic attitudes emerge in the intended application of logical models. Epistemic logics of intensional groups lift the extensionality assumptions above by seeing groups as given to us intensionally by a common property that can change their extension from world to world. We will outline an abstract algebraic and coalgebraic framework that replaces agent or group labels of epistemic modalities with names, and gives them an algebraic structure relevant to the types of collective epistemic attitudes in question. (The talk is based on ongoing collaborative work with Zoé Christoff, Wesley Fussner, Olivier Roy, and Igor Sedlár).

Information pooling has been extensively formalised across various logical frameworks in distributed systems, characterized by diverse information-sharing patterns. These approaches generally adopt an intersection perspective, aggregating all possible information, regardless of whether it is known or unknown to the agents. In contrast, this work adopts a unique stance, emphasising that sharing knowledge means distributing what is known, rather than what remains uncertain. This paper introduces new modal logics for knowledge pooling and sharing, ranging from a novel language of knowledge pooling to a dynamic mechanism for knowledge sharing. It also outlines their axiomatizations and discusses a potential framework for permissible knowledge pooling.

Sheaf theory provides a way to study global properties from data parametrized by a space. This presentation will show ongoing work to make this point of view compatible with the study of swarms of robots through their local interactions. Robot tasks and their solvability will be framed in the language of sheaves, and the sheaf Laplacian will be used as an algorithm for approximate gathering. A case will be made for applying this approach to localization and exploration tasks.