Algebraic Topology applied to Distributed Asynchronous Systems
Introduction
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
- An excellent book on algebraic topology,
freely available, by Allen Hatcher at Cornell.
- Maurice Herlihy's homepage. A lot of pointers
to the important papers in the field of distributed computing and algebraic topology.
- Sergio Rajsbaum's homepage.
- Eli Gafni's homepage.
Frédéric Tronel
Last modified: Thu Oct 18 11:10:25 MEST 2001
