At the turn of the 21st century, a significant breakthrough has been achieved in distributed computing, by analyzing computation using tools from combinatorial topology. The topological approach led to numerous outstanding results regarding the design and analysis of distributed algorithms for a large class of tasks, and a large variety of models. However, the “topological revolution” mostly impacted shared memory computing models, while the models related to distributed computing in networks, and the tasks related to graph problems were left aside. As a result, despite tremendous progress, the techniques used in distributed network computing, for both lower and upper bounds, remain ad hoc, and a global conceptual understanding of computing in networks is still missing. Thanks to the use of algebraic topology, the project DUCAT aims at providing distributed network computing with the same conceptual benefits and generic tools as the ones obtained by distributed shared memory computing.
Monsieur Pierre Fraigniaud (Institut de Recherche en Informatique Fondamentale)
The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.
IRIF Institut de Recherche en Informatique Fondamentale
LIS Laboratoire d'Informatique et Systèmes
Help of the ANR 279,266 euros
Beginning and duration of the scientific project: March 2021 - 48 Months