Calculabité et complexité pour des systèmes distribués tolérants aux pannes

E. Goubault

18 novembre 2002






On peut caractériser dans certains cas [6, 7, 5] par des moyens géométriques ce qui peut être calculé dans certains systèmes distribués tolérants aux pannes. Un exemple typique de ``fonction'' que l'on veut calculer est le consensus: chaque processeur commence son exécution avec une valeur locale (par exemple son numéro IP), et essaie de communiquer avec ceux qui sont encore vivants pour qu'ils se mettent tous d'accord sur un des numéros initiaux.

Un vieux résultat [1] montre que dès que l'on peut s'autoriser au moins une panne dans un système distribué à mémoire partagée avec écriture et lecture atomiques, alors on ne peut pas programmer le consensus. Depuis beaucoup d'autres résultats (voir par exemple [4]) ont été démontrés, mais les fondations sémantiques sont encore mal assurées. Une solution serait de savoir calculer la représentation géométrique utilisée dans ces travaux, à partir d'une sémantique géométrique du langage utilisé sur une architecture distribuée donnée. Des premiers éléments peuvent être trouvés en [3, 2].

References

[1]
M. Fisher, N. A. Lynch, and M. S. Paterson. Impossibility of distributed commit with one faulty process. Journal of the ACM, 32(2):374--382, April 1985.

[2]
E. Goubault. The dynamics of wait-free distributed computations. Technical report, Research Report LIENS-96-26, December 1996.

[3]
E. Goubault. Optimal implementation of wait-free binary relations. In Proceedings of the 22nd CAAP. Springer Verlag, 1997.

[4]
E. Goubault. Geometry and concurrency: A users' guide. Mathematical Structures in Computer Science, 2000.

[5]
M. Herlihy and S. Rajsbaum. A primer on algebraic topology and distributed computing. In J. van Leeuwen, editor, Computer Science Today, volume LNCS 1000, pages 203--217. Springer-Verlag, 1995.

[6]
M. Herlihy and N. Shavit. The asynchronous computability theorem for t-resilient tasks. In Proc. of the 25th STOC. ACM Press, 1993.

[7]
M. Herlihy and N. Shavit. A simple constructive computability theorem for wait-free computation. In Proceedings of STOC'94. ACM Press, 1994.
This document was translated from LATEX by HEVEA.