Alexandru Baltag
Slides
In this talk I focus on pure exchange events (as defined in the talk by S. Smets), and investigate operations on pure exchange event models, including a type of asynchronous iteration, that produces infinite asynchronous event models.
Contrary to received wisdom, I show that for having (finitary) DEL-type reduction axioms we do not need to assume that the event model is finite (or even finite-image). Instead, I use the notion of k-depth approximation of event-bisimilarity to define a notion of 'effective' event model, for which one can automatically generate a recursive set of finitary reduction axioms (for knowledge, distributed knowledge and common distributed knowledge). I then show that the reduction axioms can be extended to a full PDL-type logic, with ``exchange programs" built from pure exchange events using the usual regular operations (non-deterministic choice, sequential composition and Kleene star).
I apply this to the special case of in-group mutual-sharing events (-also known as `resolution') , obtaining a complete axiomatization (and proof of Finite Model Property and decidability) for an Asynchronous DEL of in-group mutual sharing. Finally, I use this work to provide a complete axiomatization (and proof of decidability) for the ``logic for resolving distributed knowledge" introduced in a recent paper by Balbiani, van Ditmarsch and Lerouvillois.
PS: Time-permitting, I may show how this work can be recast in terms of simplicial semantics, and how the proof of FMP can be even better understood when stated in terms of local states (vertices of a simplicial complex). Also, this setting can be extended with atoms for epistemic comparisons, and all the results go through.
References:
[5] A. Baltag. Pure Exchange Events and Asynchronous DEL. Manuscript, 2026..
Cameron Calk
An important question in the domain of distributed computing is that of task solvability : given a distributed task, the analog of a program specification for distributed systems, under which conditions can it be solved by some distributed protocol ? The topological approach to distributed computing represents tasks and protocols as relations between simplicial complexes, combinatorial objects which encode possible global states of the system. These have a spatial interpretation, which led to the Asynchronous Computability Theorem (ACT), which relates, for certain computational models, the existence of a continuous map to task solvability, using subdivisions of the input space.
In this talk, I will present a generalisation of the ACT for colourless protocols based on categorical and duality theoretic constructions. This is achieved by viewing an iterated protocol as an endofunctor on the category of simplicial complexes, along with a natural transformation encoding the relation between inputs and computational outputs. From this data we produce, for each possible set of inputs, a limit object in the form of a spectral space which encodes all possible computational outputs, and characterises the task solvability of the protocol. Indeed, a protocol can solve a task if, and only if, there exists a map from the associated spectral space to the space of outputs. This construction works for any iterated protocol, but we additionally show that it is compatible with the original approach using subdivision protocols, since in this case the geometric realisation, the space used in the original ACT, is a canonical subspace of the associated spectral space. A full version of the paper can be found here.
Armando Castañeda
Since the early 90s, a number of combinatorial and algebraic topology techniques have been successfully applied to distributed computing, which has resulted in a rich and solid computability theory of distributed computing. However, the theory has mostly been applied to study distributed problems that can be defined through the task formalism. Roughly speaking, a task is the equivalent of a function in a distributed setting. Very little is known about topology techniques applied to distributed problems that cannot be specified as tasks. A prominent example are concurrent objects, which are of great interest in the design of real-world systems, for example, linearizable concurrent data structures. In this talk I will present work in progress that attempts to extend the theory to encompass this type of distributed problems.
Juan Antonio Cordero-Fuentes
Relevant networked systems for content distribution (e.g., decentralized reliable multicast, ICN) can be modeled as distributed systems consisting of two types of autonomous agents, providers and requesters, that interact with each other (providers may serve requested contests; requesters request contents from providers) and take decisions (selection of providers, willingness to serve contents) only based on locally-collected information. We examine the case of concentrating policies, in which providers receiving a larger share of requests are more likely to serve contents; and those receiving a smaller share are more likely to refuse content serving. Depending on the environment parameters (network and providers characteristics) and the configuration parameters (requesters learning step, providers willingness threshold), the system may be able to adapt and learn the best possible choice for providers and requesters, so that these reach an optimal agreement; or present some suboptimal or degraded behavior (e.g., poor or no equilibrium). This talk explores the main findings resulting from the study of these systems, based both on theoretical analysis and simulations, and discusses remaining challenges and possible follow-ups and applications.
Djanira Gomes and Rojo Randrianomentsoa
Slides
We present a doxastic, relational variant of the simplicial model, which comes with a local semantics. That is, formulas are evaluated not just on global worlds, but on local states and arbitrary sets of local states. Simplicial models already make the local states of agents explicit as the core elements of which a global state is composed. The accessibility relation, however, is defined between global states. Thus, in order to compute Alice's beliefs about Bob's local state, we need to look at the entire global states that Alice considers possible. On our models, we instead define an accessibility relation directly between local states. Alice’s possible worlds are now merely collections of local states that Alice considers possible. This results in an interesting three-valued semantics that (superficially) resembles the semantics on impure simplicial complexes in Randrianomentsoa et al. (2023), but comes with radically different validities.
Hans van Ditmarch
Slides
not yet
Marta Bílková and Roman Kuznets
Simplicial complexes provide an agent-centric view of distributed systems. On the one hand, this shift may be treated as trivial due to the known categorical equivalence with the Kripke semantics. We approach the simplicial framework from the opposite side: a change of reasoner suggests a change in the reasoning mode. The first difference is that three-valued logic seems more appropriate than two-valued one to represent the agents' uncertainty about the alive/crashed status of other agents. We discuss the possibilities through the lens of bisimulation, deduction theorem, and algebraisability.
Eric Goubault
In this talk we will show that the now classical protocol complex approach to distributed task solvability of Herlihy et al. can be understood in standard categorical terms. First, protocol complexes are functors, from chromatic (semi-) simplicial sets to chromatic simplicial sets, that naturally give rise to algebras. These algebras describe the next state operator for the corresponding distributed systems. This is constructed for semi-synchronous distributed systems with general patterns of communication for which we show that these functors are always Yoneda extensions of simpler functors. Furthermore, for these protocol complex functors, we prove the existence of a free algebra on any initial chromatic simplicial complex, modeling iterated protocol complexes. Under this categorical formalization, protocol complexes are seen as transition systems, where states are structured as chromatic simplicial sets. We exploit the epistemic interpretation of chromatic simplicial sets and the underlying transition system (or algebra) structure to introduce a temporal-epistemic logic and its semantics on all free algebras on chromatic simplicial sets. Finally, we show how to extend this framework to more general dynamic network graphs and state-dependent protocols, and give examples in fault-tolerant distributed systems and mobile robotics.
Barteld Kooi
Probabilistic epistemic logic extends standard epistemic frameworks by incorporating agents’ degrees of belief. In this talk, I will provide an introduction to the basic ideas and motivations behind probabilistic epistemic logic. I will then discuss dynamic aspects, focusing on how agents update their beliefs in response to new information, and how this compares to other approaches. Finally, I will discuss open problems and directions for future research.
Sophia Knight
Slides
The coordinated attack problem models the challenges of coordinating a joint action that needs to be performed in a bounded amount of time, by communicating over unreliable links. It is the first distributed computing problem to be proven to be unsolvable, and it revealed the importance of common knowledge. However, randomized version of coordinated attack, which is solvable, has not, to the best of our knowledge, been studied through the lens of probabilistic epistemic logic.
In this work, we present an epistemic logic framework to study randomized algorithms with a bounded number of rounds. The framework is inspired by the operational model of Varghese and Lynch (Info. Comp. 1996) that introduced randomized coordinated attack. Using this framework, we analyze both the algorithm and the lower bound of Varghese and Lynch from a knowledge-theoretic perspective.
Joint work with David Lehnherr, Sergio Rajsbaum
Jérémy Ledent
In this talk, I will give an introduction to the simplicial complex semantics of epistemic logic. Conceptually, moving from Kripke frames to simplicial complexes represents a shift in perspective: the fundamental object of interest is no longer the possible worlds, but the agents’ points of view about the world. This reveals a geometric structure that is already implicit in the usual Kripke framework. I will focus on the notion of distributed knowledge, that is, the knowledge that a group of agents would acquire, if they were able to perfectly share their local information. As it turns out, distributed knowledge (as well as its infinite iteration, common distributed knowledge), admits a natural geometric interpretation in terms of higher-dimensional connectivity of the simplicial complex. I illustrate the approach with examples from distributed computing, in particular the majority consensus task.
Valentin Müller
Slides
Stephan Felber
Murdoch James Gabbay
Clara Lerouvillois and Hans van Ditmarsch
Joint talk with Hans van Ditmarsch, partially based on:
Philippe Balbiani, Hans van Ditmarsch, Clara Lerouvillois, Resolving Asynchronous Distributed Knowledge, Proceedings of Advances in Modal Logic 2026, to appear.
Yoram Moses
Thomas Schlögl
Philip Sink
Sonja Smets