Topological Methods in Distributed Computing

July 10 – 15 , 2016, Dagstuhl Seminar 16282

Dmitry Feichtner-Kozlov (Universität Bremen, DE)
Sergio Rajsbaum (Universidad Nacional Autonoma – Mexico, MX)
Michel Raynal (University of Rennes, FR)
Damien Imbs (Universität Bremen, DE)

In the early 1990’s, it was realized that topological methods are applicable in proving impossibility results in theoretical distributed computing. There followed a process of further penetration of simplicial and combinatorial methods, which by now have gained a definite foothold in distributed computing.

The mathematics needed for the wait-free shared memory model is essentially that of simplicial complexes and carrier maps between them. With subsequent maturing of the theory and diversification of the considered questions, many further mathematical fields are coming in: for example, one needs to consider group actions and equivariant maps, as well as simplicial and carrier maps which satisfy other, less standard conditions. Many of the questions which arise in this setup are somewhat different from the questions classically studied in the simplicial context.

There has been some work on mathematical foundations, though much remains to be done when it comes to precise definitions and rigorous proofs. There is a large variety of distributed tasks (e.g., computing the independent set in a graph) where the mathematical component is very substantial, and the answer would need to be phrased mathematically.

The main goal of this seminar is to bring together experts in different fields of computer science and mathematics so as to create an interdisciplinary forum at which the current state of the art of the subject can be clearly communicated, and future developments can be outlined in broad terms.

Data Structures / Algorithms / Complexity
Semantics / Formal Methods
Distributed protocols
Shared-memory communication
Combinatorial topology

See the corresponding webpage.