Lehnherr, David Benjamin (2025). Simplicial Structures for Epistemic Reasoning in Multi-agent Systems. (Thesis). Universität Bern, Bern
|
Text
25lehnherr_d.pdf - Thesis Available under License Creative Commons: Attribution (CC-BY 4.0). Download (1MB) | Preview |
Abstract
Over the past decades, using modal logic to represent the knowledge of processes has proven to be a powerful framework for formally reasoning about distributed systems. Another story of success is modeling the views of processes with the help of (chromatic) simplicial complexes. Due to the rich toolbox of combinatorial topology, this approach has yielded many fundamental insights. However, the connection between these two models, namely simplicial semantics for modal logic, has been discovered only recently. This thesis continues the structural study of simplicial semantics by changing the standard properties of chromatic simplicial complexes. Originally, a colored vertex is interpreted as a possible local state of the agent corresponding to that color. Global states are certain faces of the simplicial complex, and indistinguishability is based on the containment of vertices. We investigate three different simplicial structures by altering simplicial complexes in the following separate ways: allowing adjacent vertices to share the same color (polychromatic complexes), introducing directed faces (directed complexes), and permitting parallel faces (semi-simplicial sets). We explore polychromatic complexes and directed simplicial complexes as models for belief. Different to knowledge, beliefs may be false. Models for belief are of great importance when using simplicial models to reason about distributed systems with malicious agents. In such a setting, an adversarial agent can manipulate honest agents. Thus, trustworthy agents may need to make decisions based on their beliefs. Polychromatic complexes allow us to doxastically interpret the multiplicity of a color within a face. Different to the original model, vertices correspond to doxastic states of an agent. The fewer doxastic alternatives an agent has in a face, the more plausible it becomes. If there is exactly one doxastic state, belief becomes knowledge. We analyze the notion of most plausible belief, i.e., what an agent believes when only considering adjacent faces with the lowest multiplicity of its color. The notion of most plausible belief is often hidden in cryptographic properties of the form: algorithm guarantees property P with overwhelming probability. This statement could be read as: it is most plausible that, when using , the property P holds”. Lastly, we explore how an alternative interpretation of polychromatic complexes can model quorum systems. Directed complexes provide an intuitive framework for modeling belief, because they preserve the interpretation of standard (undirected) simplicial complexes, i.e., vertices still correspond to “physical” local states. Directions are assigned to faces from the perspective of a vertex and can be either 1 or 0. We interpret 1 as being possible and 0 as being impossible. For evaluating belief, an agent only considers adjacent facets with direction 1. Notably, our models allow for merely introspective beliefs, as the accessibility relation is not required to be serial. This is achieved by assigning direction 0 to all adjacent facets. Moreover, we introduce a logic of belief and prove it to be sound and complete with respect to models based on directed complexes. To conclude, we position our directed models within the literature by showing them to be as expressive as one of the original variants of simplicial models. A novelty of simplicial semantics is that the indistinguishability relation is based on connectivity, which implies that it inherits properties of the underlying structure. A generalization of simplicial complexes are semi-simplicial sets, which may contain parallel faces. This indicates that there might be indistinguishability relations based on higher-order connectivity, and not just on the containment of vertices. Unlike usual notions of group knowledge, the rich structure of semi-simplicial sets allows us to unfold relations (or synergies) among members of a group. We refer to this construct as an agent pattern. Moreover, we introduce an explicit representation of semi-simplicial sets and identify an indistinguishability relation for agent patterns. Our indistinguishability relation induces a new modality, which we term synergistic knowledge. We present the logic of synergistic knowledge and show its soundness and completeness with respect to models based on semi-simplicial sets. Furthermore, we illustrate applications of our models for various settings of distributed computing. Examples include the hierarchy of consensus and the dining cryptographers problem. Finally, we discuss a different reading of agent patterns, which is still based on our indistinguishability relation, inducing an additional modality that enables reasoning about group knowledge of processes with respect to the underlying network topology.
| Item Type: | Thesis |
|---|---|
| Dissertation Type: | Cumulative |
| Date of Defense: | 8 December 2025 |
| Subjects: | 000 Computer science, knowledge & systems 500 Science > 510 Mathematics |
| Institute / Center: | 08 Faculty of Science |
| Depositing User: | Sarah Stalder |
| Date Deposited: | 24 Dec 2025 16:52 |
| Last Modified: | 24 Dec 2025 16:56 |
| URI: | https://boristheses.unibe.ch/id/eprint/7008 |
Actions (login required)
 |
View Item |