A Topological Method for Colorless Distributed Computability

Yannis Coutouly (LIS)

Summary

We will present a serie of classical and recent results using geometrical and topological methods in distributed computability.

In this part, we will see what is the connection between having a distributed algorithm on a sub-IIS model for a specific task $(I,O,\Delta)$ and the existence of a continuous function between a space $X$ in $|I|$ to the complex $|O|$. This result is an extension of the ACT theorem, we will see the proof of such theorem and explicit the difficulty to obtain the generalization to sub-model of IIS.

At the end, we will see that despite such connection, there exist some interesting counter-examples that show that some classic topological invariants may not be enough to obtain a classification of the distributed task.