Algebraic Topology applied to Distributed Asynchronous Systems


As stated in this brief introduction to fault tolerance by the mean of group communication, the problem of consensus (distributed agreement) play a central role in the theory of distributed computing. Since it has been proven to be unsolvable by deterministic algorithms in a purely asynchronous system, it was a real challenge to explicitly determine the border that exists between solvable and unsolvable problems in asynchronous systems. This problem is remained unsolved till the publication of a seminal paper by Maurice Herlihy and Nir Shavit. In fact at the reading of this paper, one can understand that all the previous approaches where prone to fail. Indeed, all of them kept on using the traditional way of modelling an asynchronous system, namely by the mean of a graph of local states. This technic can be successful, when there is only one crash in the system. However, it does not scale well, when the number of crashes increases. On the contrary, Herlihy and Shavit have chosen to model the evolution of the system through the use of high dimensional geometrical objects.

Further Elements

I have written slides that attempt to introduce the basic notions of algebraic topology that are necessary to understand the last advances in theory of distributed systems (unfortunately in French, an English version soon):

Related Links

Frédéric Tronel
Last modified: Thu Oct 18 11:10:25 MEST 2001