Mathematical Methods in Distributed Computing

• Applicant: Professor Dr. Dmitry Feichtner-Kozlov
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2014 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 258519225

The goal of this interdisciplinary project is to develop new mathematical tools in the analysis of distributed systems and to improve our understanding of complexity and computability bounds in distributed computing. Practically all computing systems, from fire alarms to Internet-scale services, are nowadays distributed: they consist of a number of computing units performing independent computations and communicating with each other to synchronize their activities. Our dependence on performance and reliability of the distributed computing becomes more and more imminent.The main complication here is the existing immense diversity of distributed applications, models of distributed computations, and performance metrics, combined with the lack of mathematical tools to handle this complexity. Recently, an impressive attempt to address this challenge was made: a number of long-standing open questions in distributed computability were resolved using some of the most advanced branches of modern mathematics, including the elements of combinatorial and algebraic topology. These encompass proving impossibility of solving the fundamental problems of Set Agreement, and Renaming in the wait-free manner. However, most of the existing applications of topology in distributed computing concern theoretical positive or negative results, i.e., proving that no solution to a given problem in a given model exists or proving the existence fact in a non-constructive way. With a few exceptions, there are no convincing examples of using advanced mathematical tools to design new efficient algorithms. At a higher level, this proposal aims at better understanding of what can and what cannot be implemented in specific distributed environments. In particular, we intend to apply the power of modern mathematics in deriving new algorithms and tight lower bounds for distributed computing problems.

• DFG Programme: Research Grants
• International Connection: France
• Participating Persons: Professor Petr Kuznetsov; Professor Michel Raynal