10.07.16 - 15.07.16, Seminar 16282

Topological Methods in Distributed Computing

The following text appeared on our web pages prior to the seminar, and was included as part of the invitation.


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.