CSC 4509 – Algorithmique et communications des applications réparties

Référence : Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson. Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry, Epidemic Algorithms for Replicated Database Maintenance, SIGOPS Operating System Review, 22(1):8—32, January 1988).

Tuteur : Alexandre Nolin

Dans cette étude, contrairement à tous les algorithmes abordés dans le cours, nous vous proposons d'analyser un algorithme de propagation (probabiliste) d'informations, et ce dans le cadre des solutions pour la tolérance aux fautes. L'article s'intéresse à la question suivante : étant donnée une base de données répliquée sur plusieurs sites, comment partager l'information entre les différentes copies de façon à maintenir une base de donnée aussi cohérente que possible ? Plus précisément, on souhaite que les différences entre deux copies disparaissent avec le temps, mais on tolère également que des différences soient introduites temporairement de façon à accepter rapidement des modifications du contenu de la base de données.

L'étude décrit différents mécanismes utilisés en pratique, chacun avec ses avantages et ses inconvénients. Par exemple, comparer intégralement le contenu de deux copies de la base de donnée permet de résoudre toutes les différences entre les deux, mais est potentiellement très coûteux, et n'harmonise le contenu qu'entre deux copies. Un mécanisme où chaque modification ayant lieu à une copie de la base de données lui fait envoyer la modification à toutes les autres copies, est sensible aux pertes de messages, et fait porter le coût de la communication essentiellement à la copie où a eu lieu la modification. La troisième solution décrite et le coeur de l'article, un système de « propagation de rumeur » probabiliste rappelant les modèles de propagation de maladie en épidémiologie, peut être avantageuse par rapport aux limitations des autres méthodes évoquées précédemment, mais comporte plusieurs paramètres ajustables discutés dans l'article qui changent les propriétés de processus en terme d'efficacité et de tolérance aux fautes.

Les problématiques de cet article sont proches de celles du chapitre du cours sur les diffusions.

Référence : Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson, Impossibility of Distributed Consensus with One Faulty Process, Journal of the ACM, 32(2):374—382, April 1985.

Tuteur : Alexandre Nolin

Cette étude contient la preuve d'un des résultats les plus connus en algorithmique répartie, l'impossibilité du consensus en présence de crashs ou théorème FLP (ainsi nommé du nom des auteurs : Fischer, Lynch, et Paterson). L'article démontre qu'il est impossible pour un ensemble de processus de se mettre d'accord sur une valeur présente parmi les valeurs d'entrée données individuellement aux processus dans les conditions suivantes : la communication entre les processus est asynchrone, et il est possible qu'un processus défaille par arrêt franc (crash). La clé de cette impossibilité, comprise par les auteurs de l'article, est qu'il est impossible pour les autres processus de distinguer un processus défaillant d'un processus dont les messages émis mettent un temps extrêmement long à arriver. Ainsi, un algorithme atteignant le consensus même en cas d'arrêt franc d'un processus doit nécessairement arriver à une conclusion dans des configurations dans lesquelles des messages sont encore en transit, ce qui permet de créer des situations où les processus échouent à s'accorder sur une valeur unique.

Ce résultat d'impossibilité est fondamental, en ceci qu'il a guidé la recherche des décennies suivantes en matière de systèmes répartis et de tolérances aux fautes. De façon à contourner le résultat d'impossibilité, les concepteurs d'algorithmes ont dû relâcher une des hypothèses contenues dans cet article : soit supposer un système au moins partiellement synchrone, soit viser un type d'accord plus faible que le consensus, soit accepter de ne pas atteindre le consensus dans certaines exécutions. L'article a reçu le prix Dijkstra en 2001, qui récompense chaque année un article ayant eu une influence marquante sur la compréhension théorique des systèmes distribués. La page du prix contient un bref résumé de l'article et un texte des auteurs racontant son élaboration qui peuvent être une lecture intéressante pour mieux comprendre l'article. Il peut également être intéressant de consulter l'article A constructive proof for FLP par Hagen Völzer, qui offre une preuve différente du même résultat en construisant une exécution dans laquelle le consensus n'est pas atteint au lieu de simplement prouver l'existence d'une telle exécution.

Le résultat d'impossibilité FLP est mentionné à la section 3.8.1 du cours, la section 3.8 expliquant plus généralement le lien entre diffusion atomique et consensus. 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 principale : S. Gilbert et N. Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News (Technical Column), 33(2):51—59, June 2002.

Tuteur : Alexandre Nolin

Cette étude contient un autre résultat d'impossibilité, cette fois sur le fait de garantir 3 propriétés simultanément pour un service Web : les propriétés de cohérence (Consistency), de disponibilité (Availability), et de tolérance au partitionnement (Partition-Tolerance). La cohérence est l'idée que bien que réparti, le système se comporte comme une entité centralisée, donc qu'une requête effectuée auprès du service retourne la même réponse quel que soit le point d'accès utilisé pour accéder au service. La disponibilité est l'idée qu'une réponse soit apportée à chaque requête. Enfin, la tolérance aux partitions est l'idée que le système doit continuer à fonctionner même si les machines fournissant le service sont temporairement déconnectées les unes des autres.

Ce résultat avait été conjecturé par Eric Brewer 2 ans avant la publication de l'article par Gilbert et Lynch. L'article formalise les trois notions avant de prouver l'impossibilité de satisfaire les trois en même temps, que ce soit dans un système asynchrone ou partiellement synchrone. L'article montre néanmoins qu'il est possible de satisfaire n'importe quelle combinaison de 2 des 3 propriétés, ainsi qu'une version plus faible des 3 propriétés en contexte partiellement synchrone.

Douze ans après la publication de cet article, le journal Computer de la IEEE Computing Society publia un numéro intitulé « The CAP Theorem's Growing Impact ». Le numéro contient notamment une rétrospective sur l'impact du théorème par Eric Brewer, celui qui avait formulé informellement le théorème avant que Gilbert et Lynch le prouvent. Nommé « CAP Twelve Years Later: How the "Rules" Have Changed », il peut être une lecture intéressante pour prendre la mesure de l'influence qu'a eu CAP ainsi que mieux comprendre ses subtilités.

L'article traite de sujets étudiés dans le chapitre introductif du cours, qui introduit les notions de modèles de systèmes répartis, de synchronisme, ou encore de types de défaillances, ainsi que de cohérence, concept évoqué dès la section 3.5 du cours.

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

Tuteur : Guillermo TOYOS MARFURT

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.

Tuteur : Humberto VALERA (voire, 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.

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érences : J.N. Gray, L. Lamport, Consensus on Transaction Commit, ACM transactions on Database Systems, 31(1):133–160, March 2006.

Tuteur : Guillermo TOYOS MARFURT

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 transaction.

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.