CSC 4509 – Algorithmique et communications des applications réparties

Référence principale : F.C. Gärtner, Fundamentals of Fault-Tolerant Distributed Computing in Asynchronous Environments, ACM Computing Surveys, 31(1):1–26, March 1999.
Autre référence : J. Snijders, C. Morrow, R. van Mook, Software Defects Considered Harmful, RFC/RFC9225, 10.17487/RFC9225, 1 April 2022.

• Diapositives de la présentation.

Tuteur : Pascal Hennequin

Les problématiques présentées dans les présentations qui suivent s'inscrivent dans une sensibilisation ou introduction aux primitives algorithmiques pour la tolérance aux fautes des systèmes répartis. Cette première étude a pour objectif de positionner la tolérance aux fautes dans le sujet plus général de la sûreté de fonctionnement. Par ailleurs, dans nos études d'articles de recherche, les solutions étudiées se focalisent sur la tolérance aux fautes par masquage. Par conséquent, l'approche « par masquage » est aussi située par rapport aux autres approches de tolérance aux fautes.

Dans cette étude, des liens sont effectués avec le chapitre introductif du cours, qui introduit les notions de modèle de systèmes répartis ou de synchronisme, ou encore de type de défaillances.

Référence : F.C. Freiling, R. Guerraoui, P. Kuznetsov, The Failure Detector Abstraction, ACM Computing Surveys, 43(2):40 pages, January 2011.

• Diapositives de la présentation.

Tuteur : Denis Conan

L'article précédent a permis de définir le périmètre de nos études d'articles de recherche : la tolérance aux fautes par masquage. Deux abstractions sont à mettre en œuvre pour tolérer les défaillances : 1)  la détection des défaillances et 2) le recouvrement (par retour en arrière [réplication passive, redondance dans le temps] et par poursuite [réplication active, redondance dans l'espace]).

Nous commençons dans l'article de Freiling et al. par la détection de défaillance. Le rôle du détecteur de défaillance est de rassembler dans un service ou composant la gestion des conditions temporelles de fonctionnement du système réparti : quels sont les processus corrects ou défaillants ? quels sont les liens de communications corrects ou défaillants ? L'aspect le plus important de cette étude est que, dans un système asynchrone, la détection de défaillance ne peut pas être parfaite (par cohérence avec le résultat d'impossibilité du consensus dans un système asynchrone avec des processus sujets à défaillance par arrêt franc [Théorème FLP]). Ensuite, l'article présente comment les détecteurs de défaillance sont utilisés pour comparer et classer les spécifications des problèmes : quel est le détecteur de défaillance le plus faible nécessaire pour résoudre le problème ?

Dans cette étude, des liens sont effectués avec le chapitre introductif du cours, et plus particulièrement, les modèles de systèmes répartis (synchrone, asynchrone) et la typologie des défaillances.

Référence : E.N. Elnozahy, L. Alivisi, Y.-M. Wang, and D.B. Johnson, A Survey of Rollback-Recovery Protocols in Message-Passing Systems, ACM Computing Surveys, 34(3):375–408, September 2002.

• Diapositives de la présentation.

Tutrice : Denis Conan

Dans cette approche architecturale de la tolérance aux fautes, le modèle de réplication est dit « passif » dans le sens où un processus qui est défaillant est « récupéré » en repartant d'une image antérieurement construite (appélée un point de reprise, en anglais checkpoint). L'adjectif « passif » signifie donc que le processus qui recouvre le processus défaillant doit être activé à partir d'une image mémoire. En outre, l'ensemble des processus de l'application répartie est considéré comme un tout, c'est-à-dire sans structuration en groupe ou partition de processus, et il s'agit de la tolérance aux fautes de l'application répartie. Les exemples prototypiques des applications réparties utilisant la tolérance aux fautes par recouvrement arrière sont les applications de calcul scientifique réparti sur de nombreuses machines et prenant beaucoup de temps: il faut éviter de recommencer tout le calcul.

Le recouvrement arrière implique la création de points de reprise des processus puis la reprise de tout ou partie de l'ensemble des processus lors de défaillances. Les conditions pour une telle reprise en termes de contenu aussi bien de l'état d'un point de reprise que des journaux des messages échangés constituent l'objet principal de l'étude.

Un exemple d'utilisation de techniques de recouvrement arrière peut être trouvé dans openMPI, une bibliothèque qui met en œuvre le standard de passage de messages le plus utilisé en calcul parallèle (MPI, Message Passing Interface).

La problématique ainsi que les travaux présentés dans cet état de l'art permettent de faire des liens avec les notions de causalité ou d'état global ou encore de coupure cohérente étudiées en cours.

Référence : G.V. Chockler, I. Keidar, and R. Vitenberg, Group Communication Specifications: A Comprehensive Study, ACM Computing Surveys, 33(4):427–469, December 2001.

• Diapositives de la présentation.

Tuteur : Denis Conan

Contrairement à l'approche précédente, la tolérance aux fautes à base de systèmes de communication de groupe met en œuvre le modèle de réplication active, c'est-à-dire dans lequel la tolérance d'une entité ou d'un composant du système est obtenue en exécutant concurremment plusieurs répliques de l'entité. Cette approche convient par exemple aux applications réparties structurées selon le paradigme client/serveur dans lequel le serveur doit être répliqué pour que le service rendu tolère les défaillances. Dans ce paradigme, les serveurs sont modélisés comme des « machine à états », c'est-à-dire comme un ensemble de variables et de commandes qui transforment ces variables. Chaque commande est mise en œuvre par un programme déterministe, est exécutée de manière atomique (par rapport aux autres commandes), et renvoie des résultats. Les clients accèdent en concurrence à la machine à états en appelant des commandes. Une version tolérante aux fautes de la machine à états est obtenue en répliquant la machine à états.

Les systèmes présentés dans cet article organise la réplication active des machines à états en deux services : la gestion de groupe et la diffusion de messages dans un groupe.

Les deux systèmes de communication de groupe les plus populaires (en logiciels libres) sont JGroups et The Spread Toolkit.

Cet article utilise les connaissances acquises dans le chapitre du cours sur les diffusions.

Référence : X. Défago, A. Schiper, P. Urban, Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey, ACM Computing Surveys, 36(4):372–421, December 2004.

• Diapositives de la présentation.

Tuteur : Michel Simatic

Faisant suite à l'étude générale des systèmes de communication de groupe, cet état de l'art se focalise sur les algorithmes de diffusion à ordre total. Les clients accèdent en concurrence à la machine à états en appelant des commandes; les commandes sont totalement ordonnées. Toutes les répliques démarrent leur exécution dans le même état. Les clients adressent leurs commandes à toutes les répliques. Puisque les commandes sont totalement ordonnées et exécutent des programmes déterministes, toutes les répliques possèdent le même état à la fin de la même séquence de commandes. Les répliques non défaillantes renvoient donc les mêmes résultats aux clients.

La diffusion à ordre total pour la réplication active est utilisée par certains systèmes de contrôle-commande (connus aussi sous le nom de SCADA) comme ceux d'Inductive Automation (cf. le paragraphe « FactoryPMI — Java Web Start based SCADA package »), ou bien, plus généralement, pour la réplication de serveurs Cloud (informatique en nuage) sur un même site géographique.

Cet article utilise les connaissances acquises dans le chapitre du cours sur les diffusions.

Références : J.N. Gray, L. Lamport, Consensus on Transaction Commit, ACM transactions on Database Systems, 31(1):133–160, March 2006.

• Diapositives de la présentation.

Tuteur : Pascal Hennequin

Cette dernière étude présente une autre architecture pour la tolérance aux fautes : les bases de données réparties répliquées. Dans cette approche, les concepteurs organisent le traitement des données dans des transactions, classiquement délimitées par des instructions begin transaction et end transactions.

En guise d'exemple, lors de l'achat d'un billet en ligne, une application effectue une transaction. Cette transaction contacte plusieurs entités, par exemple, une banque et une salle de concert. Dans cet article, Gray et Lamport étudient comment assurer des propriétés fondamentales telles que : 1) si le compte bancaire a été débité, l'utilisateur a bien un billet en retour ; 2) si l'utilisateur reçoit un billet, son compte est bien débité ; et 3) la transaction est validé (ou non) dans un temps imparti. Dans cette étude, c'est la validation qui est la plus intéressante : elle est construite sur un « consensus », ici avec l'algorithme Paxos.

Par curiosité et à titre indicatif, une séquence de courtes vidéos préparées par L. Lamport présente le langage de spécification formelle TLA+ ainsi que l'atelier TLAPS en utilisant par exemple l'algorithme transaction commit à base de Paxos (cf. les huit premières vidéos du The TLA+ Video Course).

Paxos est mis en œuvre dans de nombreux systèmes de gestion de Clouds (informatique en nuage) tels que Google App Engine ou Amazon Web Services. Contrairement à l'utilisation qui en est faite pour la validation des transactions dans cette étude, Paxos est le plus souvent utilisé pour la réplication active de machine à états. Nous avons choisi cet article car il permet d'introduire le concept important de « transaction ».

Cet article utilise les connaissances acquises dans le chapitre du cours sur les diffusions.