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
- Armando Castaneda (National Autonomous University of Mexico, MX)
- Yoram Moses (Technion - Haifa, IL)
- Ulrich Schmid (TU Wien, AT)
- Hans Van Ditmarsch (CNRS - Toulouse, FR)
Contact
- Michael Gerke (for scientific matters)
- Simone Schilke (for administrative matters)
Schedule
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.
Creative Commons BY 4.0
Armando Castaneda, Hans van Ditmarsch, Yoram Moses, and Ulrich Schmid
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.
Armando Castaneda, Yoram Moses, Ulrich Schmid, and Hans Van Ditmarsch
- Alexandru Baltag (University of Amsterdam, NL) [dblp]
- Henning Basold (Leiden University, NL) [dblp]
- Armando Castaneda (National Autonomous University of Mexico, MX) [dblp]
- Faith Ellen (University of Toronto, CA) [dblp]
- Pierre Fraigniaud (CNRS, Paris, FR & Université Paris Cité, FR) [dblp]
- Krisztina Fruzsa (TU Wien, AT) [dblp]
- Murdoch Jamie Gabbay (Heriot-Watt University - Edinburgh, GB) [dblp]
- Guy Goren (Protocol Labs - Kibbutz Nahsholim, IL) [dblp]
- Joseph Y. Halpern (Cornell University - Ithaca, US) [dblp]
- Roman Kniazev (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Sophia Knight (University of Minnesota - Duluth, US) [dblp]
- Roman Kuznets (TU Wien, AT) [dblp]
- Jérémy Ledent (University of Strathclyde - Glasgow, GB) [dblp]
- David Lehnherr (Universität Bern, CH) [dblp]
- Shihao (Jason) Liu (University of Toronto, CA)
- Yoram Moses (Technion - Haifa, IL) [dblp]
- Susumu Nishimura (Kyoto University, JP) [dblp]
- Thomas Nowak (ENS - Gif-sur-Yvette, FR) [dblp]
- Ami Paz (CNRS - Gif-sur-Yvette, FR) [dblp]
- Sergio Rajsbaum (National Autonomous University of Mexico, MX) [dblp]
- Rojo Randrianomentsoa (TU Wien, AT)
- Hugo Rincón Galeana (TU Wien, AT) [dblp]
- David A. Rosenblueth (Universidad Nacional Autonoma - Mexico, MX) [dblp]
- Ulrich Schmid (TU Wien, AT) [dblp]
- Sonja Smets (University of Amsterdam, NL) [dblp]
- Thomas Studer (Universität Bern, CH) [dblp]
- Hans Van Ditmarsch (CNRS - Toulouse, FR) [dblp]
- Diego A. Velázquez (Universidad Nacional Autonoma - Mexico, MX) [dblp]
Classification
- Distributed / Parallel / and Cluster Computing
- Logic in Computer Science
- Multiagent Systems
Keywords
- distributed systems
- epistemic logic
- combinatorial topology
