https://www.dagstuhl.de/23272

July 2 – 7 , 2023, Dagstuhl Seminar 23272

Epistemic and Topological Reasoning in Distributed Systems

Organizers

Armando Castaneda (National Autonomous University of Mexico, MX)
Yoram Moses (Technion – Haifa, IL)
Ulrich Schmid (TU Wien, AT)
Hans Van Ditmarsch (Open University – Heerlen, NL)

For support, please contact

Simone Schilke for administrative matters

Michael Gerke for scientific matters

Motivation

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.

Motivation text license
  Creative Commons BY 4.0
  Armando Castaneda, Yoram Moses, Ulrich Schmid, and Hans Van Ditmarsch

Classification

  • Distributed / Parallel / And Cluster Computing
  • Logic In Computer Science
  • Multiagent Systems

Keywords

  • Distributed systems
  • Epistemic logic
  • Combinatorial topology

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.