TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Please select your role
to obtain appropriate quick-links.
As a LIPIcs/OASIcs author, you will be invited by e-mail to register at the Dagstuhl Submission Server. The server will guide you through the publication workflow. Preliminary information can be found here:
Quick Links

Dagstuhl Seminar 23272

Epistemic and Topological Reasoning in Distributed Systems

( Jul 02 – Jul 07, 2023 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23272
Organizers
Contact
Shared Documents
Publications
Schedule
Summary
Show Summary

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. Reasoning about distributed systems that provide these services is notoriously difficult, however, 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 the modeling, design, and analysis of distributed systems: combinatorial topology and the epistemic (or knowledge-based) approach for multi-agent systems. It is also worth noting that several different flavors of topology have been successfully applied in general modal logic and related fields as well.

In the context of distributed systems, the epistemic and the topological approach have evolved fairly independently for over more than three decades. In the last few years, however, researchers have started to combine the two approaches in productive ways. In particular, this is true for both of the two main variants of epistemic reasoning in such systems, the more traditional interpreted systems (IS) modeling and dynamic epistemic logics (DEL), where approaches and/or methods from combinatorial topology have been used successfully already. This is primarily due to a duality between the Kripke models, which underlie epistemic reasoning, and simplicial complexes, which are central to the analysis of distributed protocols using combinatorial topology. And indeed, meanwhile, there are encouraging relations and options for cross-fertilization with the communities of dynamic epistemic logic, knowledge-based analysis, and topological modal logics. This development makes a new level of abstraction possible, based on mutual incorporation of the extensive results established independently by all these approaches.

Seminar Goals and Structure

The main purpose of this Dagstuhl Seminar was to further stimulate the process of making this integration happening: Whereas there are researchers with expertise in more than one of the above fields, a majority of them is firmly grounded in only one of those. Consequently, we brought together 28 experts from the respective scientific communities, in an attempt to:

(A) Introduce the core topics, methods and accomplishments obtained in some field to the others.

(B) Stimulate discussions among members from different fields, to identify possible cross-fertilization opportunities.

(C) Further explore particularly interesting/promising/challenging cross-fertilization opportunities and shape collaborations on these.

The cornerstones of the seminar program were:

(i) 5 tutorials (90 min) by experts in the following specific areas:

  • Alexandru Baltag
    Epistemics and Topology
  • Hans van Ditmarsch
    Dynamic Epistemic Logic
  • Guy Goren
    Knowledge and Action
  • Jérémy Ledent
    Simplicial Models: From Global States to Local States, and What Lies In-between
  • Sergio Rajsbaum
    An Overview of Combinatorial Topology and Its Distributed Computing Perspective

(ii) 17 presentations (20 min) devoted to specific research topics, from all areas.

(iii) 3 short presentations (5 min) in a rump session, devoted to research topics that were identified in the course of the seminar.

(iv) Public sessions devoted to identifying particularly promising cross-fertilization opportunities.

(v) 3 focused discussion groups, devoted to the following cross-fertilization opportunities:

  • Extending Topology to Handle Data Structures
  • Interpreted Systems and Dynamic Epistemic Logic
  • Representing Epistemic Attitudes via Simplicial Complexes

Multiple discussion sessions of these groups were run in parallel, with two public reporting sessions. Seminar participants could join/swap the discussion groups freely.

Copyright Armando Castaneda, Hans van Ditmarsch, Yoram Moses, and Ulrich Schmid
Motivation
Show 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.

Copyright Armando Castaneda, Yoram Moses, Ulrich Schmid, and Hans Van Ditmarsch
Participants
Show Participants
Classification
  • Distributed / Parallel / and Cluster Computing
  • Logic in Computer Science
  • Multiagent Systems
Keywords
  • distributed systems
  • epistemic logic
  • combinatorial topology
Seminar 23272
© 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
ImprintContactAccessibilityPrivacy