Distributed services cover a wide range of our everyday activities. Examples of such services include cloud storage, cryptocurrencies and collaborative editing, as well as concurrent software that governs modern multicore computers. All of these give rise to distributed systems. Reasoning about distributed systems, however, is notoriously difficult due to the many sources of uncertainty that can occur: varying execution speeds, unpredictable transmission delays and partial failures. The design and analysis of protocols and algorithms for distributed systems is, hence, a difficult and error-prone task.

Two approaches have proved to be successful in raising the level of abstraction in modeling, design, and analysis of distributed algorithms. These are the combinatorial topology approach and the epistemic (or knowledge-based) approach. Both approaches have evolved fairly independently for over more than three decades. Recently, researchers have started to combine the two approaches in productive ways. This is based on a duality between the Kripke models that underly epistemic reasoning and simplicial complexes, which are central to the analysis of distributed protocols using combinatorial topology. In addition, two variants of epistemic reasoning, the more traditional interpreted systems modelling, and dynamic epistemic logics, have each been more directly related to the topological approach. This makes a new level of abstraction possible allowing the mutual incorporation of the extensive results on distributed computing established independently by the two approaches.

The main target of this Dagstuhl Seminar is to bring together experts on the combinatorial topology approach and the epistemic-based approach, with the aim of exploring the directions that the recent interaction between both approaches can take, identifying challenges and opportunities. There are also encouragingly strong relations and options for cross fertilization with the communities of dynamic epistemic logic, knowledge-based analysis, and topological modal logics.

Creative Commons BY 4.0

Armando Castaneda, Yoram Moses, Ulrich Schmid, and Hans Van Ditmarsch