Dagstuhl Seminar 16282
Topological Methods in Distributed Computing
( Jul 10 – Jul 15, 2016 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/16282
Organizer
- Dmitry Feichtner-Kozlov (Universität Bremen, DE)
Coordinator
- Damien Imbs (Universität Bremen, DE)
Contact
- Susanne Bach-Bernhard (for administrative matters)
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.
This seminar brought together 22 researchers in combinatorial topology and in theoretical distributed computing. Participants came from Germany, France, Israel, Switzerland, United States, Canada, Japan and Austria. The seminar featured a~combination of 1-hour talks, group sessions and an open problems session.
Scientific background and topics of the seminar
In the classical sequential computational model, computability is viewed through the Church-Turing thesis, where computations are reduced to those done by Turing machines, and complexity issues are of central importance. In the distributed setting, the situation is quite different. Since the threads of executions may intertwine in various ways (depending on the model), one of the central issues becomes dealing with execution ambiguity, and deciding whether certain standard tasks (Consensus, Renaming, etc.) are computable at all.
In this sense, the distributed setting is harder to analyze rigorously than the sequential one, or at least the difficulties are of quite different type. At the same time very many real-life situations need to be modeled by the distributed setting. These include networks of banking machines, or networks of flight controllers and airplanes, who need to reach a common decision in a decentralized setting. Another example is the parallel chip design, where we need to understand what type of elementary operations - so-called computational primitives, have to be implemented on the hardware level, so that the resulting computational system is powerful enough for our needs.
In the 80s it was realized (due in particular to the work of Fischer, Lynch and Paterson) that certain standard tasks (Consensus) cannot be solved in standard computational models (such as Message-Passing) in the presence of even simple processor crash failures. As spectacular as it is, it has become one of the steps in the development of a sophisticated and beautiful subject of theoretical distributed computing; we refer here to the classical books of Lynch and Attiya & Welch.
In the late 90s and in the early years of our millenium, it was realized by at least 3 independent groups of researchers that topological methods are applicable in proving impossibility results in theoretical distributed computing. There followed a process of further penetration of topological methods, which by now have gained a definite foothold in distributed computing. Additionally, there has also been some work on mathematical foundations, though much remains to be done when it comes to precise definitions and rigorous proofs. Independently, we feel that it is of great interest to develop the mathematics which is inspired by these methods.
The state-of-the-art of the subject was recently summarized in a book by Herlihy, Kozlov and Rajsbaum. One of the paradigms introduced there is to replace the computational task specification by the triple: input complex, output complex, and task specification map, there the input and the output complexes are simplicial complexes with additional structure, and the task specification map is what we call a carrier map, whose definition reflects our desire to restrict ourselves to the wait-free protocols. All the wait-free tasks can be encoded this way, and as a result one obtains both well-known as well as new structures from combinatorial topology.
Furthermore, one can consider the simplicial model for the totality of all executions of a given protocol -- the so-called protocol complex. In the full formal setting one actually considers a triple of two simplicial complexes and a carrier map, each one equipped with an additional structure. The intuition here is that the second simplicial complex, as well as the carrier map depend heavily on the model of computation that we choose. One standard example is to take the so-called Immediate Snapshot model. On Figure 1 we show the protocol complex for the one-round execution of the standard immediate snapshot protocol for 3 processors. As already this example shows, frequently there is a purely combinatorial description of the arising simplicial structure. The question of wait-free computability of a given task in a given computational model reduces then to the question of existence of a~simplicial map from the protocol complex to the output complex, the so-called decision map, which satisfies certain conditions, which in essence mean that the outputs obtained by the protocol are valid under the task specification. Furthermore, we also have mathematical models for anonymous tasks, and anonymous protocols, as well as for colorless tasks.
As one can see, the mathematics needed for the current model is essentially that of simplicial complexes and carrier maps between them. With subsequent deepening 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.
Creative Commons BY 3.0 Unported license
Dmitry Feichtner-Kozlov and Damien Imbs
- Peva Blanchard (EPFL - Lausanne, CH) [dblp]
- Jeremie Chalopin (Aix-Marseille University, FR) [dblp]
- Emanuele Delucchi (University of Fribourg, CH) [dblp]
- Dmitry Feichtner-Kozlov (Universität Bremen, DE) [dblp]
- Etienne Fieux (Université Paul Sabatier - Toulouse, FR) [dblp]
- Eli Gafni (UCLA, US) [dblp]
- Emmanuel Godard (Aix-Marseille University, FR) [dblp]
- Hans Hagen (TU Kaiserslautern, DE) [dblp]
- Damien Imbs (Universität Bremen, DE) [dblp]
- John Frederick Jardine (University of Western Ontario - London, CA)
- Petr Kuznetsov (Telecom Paris Tech, FR) [dblp]
- Jan-Philipp Litza (Universität Bremen, DE)
- Hammurabi Mendes (University of Rochester, US) [dblp]
- Roy Meshulam (Technion - Haifa, IL) [dblp]
- Susumu Nishimura (Kyoto University, JP) [dblp]
- Ami Paz (Technion - Haifa, IL) [dblp]
- Eloi Perdereau (Aix-Marseille University, FR)
- Thibault Rieutord (Telecom Paris Tech, FR) [dblp]
- Matthieu Roy (LAAS - Toulouse, FR) [dblp]
- Ulrich Schmid (TU Wien, AT) [dblp]
- Jan Felix Senge (Universität Bremen, DE)
- Julien Michel Stainer (EPFL - Lausanne, CH) [dblp]
Related Seminars
- Dagstuhl Seminar 12121: Applications of Combinatorial Topology to Computer Science (2012-03-18 - 2012-03-23) (Details)
Classification
- data structures / algorithms / complexity
- networks
- semantics / formal methods
Keywords
- distributed protocols
- solvability
- shared-memory communication
- concurrency
- combinatorial topology
