Initiation à l’algorithmique répartie

Initiation à l’algorithmique répartie Denis Conan Revision : 151 CSC4509 Télécom SudParis Avril 2020 Initiation à l’algorithmique répartie Table des matières Initiation à l’algorithmique répartie Denis Conan, , Télécom SudParis, CSC4509 Avril 2020 1 Licence 4 Utilisation du cours 5 Plan du document 6 1 Éléments introductifs 7 1.1 Modèle de système réparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.1 Modèle de transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.2 Synchronisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.3 Types de défaillances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Conventions de codage des algorithmes répartis . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3 Relation « arrivé avant » aussi appelée précédence causale, Lamport 1978 . . . . . . . . . . . . 15 1.3.1 Algorithme de calcul des horloges scalaires de Lamport 1978 . . . . . . . . . . . . . . . 16 1.3.2 Algorithme de calcul des horloges vectorielles de Fidge 1991 . . . . . . . . . . . . . . . . 17 1.3.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.4 Vague et traversée de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.4.1 Algorithme de vague centralisé Écho de Segall, 1983 . . . . . . . . . . . . . . . . . . . . 20 1.4.2 Algorithme de vague décentralisé de Finn, 1979 - . . . . . . . . . . . . . . . . . . . . . . 22 1.4.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2 Élection 24 2.1 Propriétés et vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Élection dans un anneau, algorithme de Le Lann, 1977 . . . . . . . . . . . . . . . . . . . . . . . 26 2.3 Élection avec l’algorithme de vague Écho de Segall, 1983 . . . . . . . . . . . . . . . . . . . . . . 28 2.3.1 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3 Diffusion 31 3.1 Spécification des diffusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Diffusion fiable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2.1 Algorithme de diffusion fiable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3 Diffusion FIFO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.1 Algorithme de diffusion FIFO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Diffusion causale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.1 Algorithme de diffusion causale construit à partir d’un algorithme de diffusion FIFO . . 40 3.4.2 Algorithme de diffusion causale à base d’horloge vectorielle de Birman et Joseph, 1987 . 42 3.4.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.5 Diffusion atomique (ou totale) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.6 Relations entre les diffusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.7 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.8 Diffusion atomique et consensus - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.8.1 Résultat d’impossibilité du consensus - . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.8.2 Algorithmes de diffusion temporisée - . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.9 Propriété d’uniformité - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.10 Inconsistance et contamination - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4 Exclusion mutuelle 54 4.1 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2 Algorithmes à base de permissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2.1 Structure informationnelle générique de Sanders, 1987 . . . . . . . . . . . . . . . . . . . 57 4.2.2 Algorithme générique de Sanders, 1987 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2.3 Quelques algorithmes (dérivés de l’algorithme générique) . . . . . . . . . . . . . . . . . . 59 Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 2 Initiation à l’algorithmique répartie 4.3 Algorithme à base de jeton de Ricart et Agrawala 1983, et de Suzuki et Kasami, 1985 . . . . . 62 4.4 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5 Interblocage 65 5.1 Principaux modèles d’interblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.1.1 Modèle d’interblocage ET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.1.2 Modèle d’interblocage OU–ET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.2 Condition de déblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.3 Définition de l’interblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.4 Trois stratégies contre l’interblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.5 Prévention dans le modèle ET avec l’algorithme de Rosenkrantz, Stearns et Lewis, 1978 . . . . 73 5.5.1 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.6 Détection d’interblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.6.1 Coupure cohérente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.6.2 Algorithme centralisé de construction de coupure cohérente de Chandy et Lamport, 1985 77 5.6.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6 Détection de terminaison 79 6.1 Modèle OU de l’interblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.2 Configurations terminale et finale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.3 États actif et passif, et algorithme de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.4 Algorithmes de détection de terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.5 Détection par calcul du graphe d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.5.1 Algorithme de Dijkstra et Scholten, 1980 . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.5.2 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.6 Détection par vagues dans un anneau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.6.1 Algorithme de Safra, 1987 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.6.2 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Bibliographie 92 Index 93 Fin 95 Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 3 Initiation à l’algorithmique répartie ~~'~~ $ % # 2 Licence Ce document est une documentation libre, placée sous la Licence de Documentation Libre GNU (GNU Free Documentation License). Copyright (c) 2003-2020 Denis Conan Permission est accordée de copier, distribuer et/ou modifier ce document selon les termes de la Licence de Documentation Libre GNU (GNU Free Documentation License), version 1.2 ou toute version ultérieure publiée par la Free Software Foundation; avec les Sections Invariables qui sont ‘Licence’ ; avec les Textes de Première de Couverture qui sont ‘Initiation à l’algorithmique répartie’ et avec les Textes de Quatrième de Couverture qui sont ‘Fin’. Une copie de la présente Licence peut être trouvée à l’adresse suivante : http://www.gnu.org/copyleft/fdl.html. Remarque : La licence comporte notamment les sections suivantes : 2. COPIES VERBATIM, 3. COPIES EN QUANTITÉ, 4. MODIFICATIONS, 5. MÉLANGE DE DOCUMENTS, 6. RECUEILS DE DOCUMENTS, 7. AGRÉGATION AVEC DES TRAVAUX INDÉPENDANTS et 8. TRADUCTION. ~~&~~ Ce document est préparé avec des logiciels libres : L TEX : les textes sources sont écrits en L TEX (http://www.latex-project.org/, le site du Groupe francophone des Utilisateurs de TEX/L TEX est http://www.gutenberg.eu.org). Une nouvelle classe et une nouvelle feuille de style basées sur la classe seminar ont été tout spécialement dévéloppées: newslide et slideint (projet fusionforge slideint, https://fusionforge.int-evry.fr/www/slideint/); emacs: tous les textes sont édités avec l’éditeur GNU emacs (http://www.gnu.org/software/emacs); dvips: les versions PostScript (PostScript est une marque déposée de la société Adobe Systems Incorporated) des transparents et des polycopiés à destination des étudiants ou des enseignants sont obtenues à partir des fichiers DVI (« DeVice Independent ») générés à partir de LaTeX par l’utilitaire dvips (http://www.ctan.org/tex-archive/dviware/dvips); ps2pdf et dvipdfmx: les versions PDF (PDF est une marque déposée de la société Adobe Systems Incorporated) sont obtenues à partir des fichiers Postscript par l’utilitaire ps2pdf (ps2pdf étant un shell-script lançant Ghostscript, voyez le site de GNU Ghostscript http://www.gnu.org/software/ghostscript/) ou à partir des fichiers DVI par l’utilitaire dvipfmx; makeindex: les index et glossaire sont générés à l’aide de l’utilitaire Unix makeindex (http://www.ctan.org/tex-archive/indexing/makeindex); TeX4ht: les pages HTML sont générées à partir de LaTeX par TeX4ht (http://www.cis.ohio-state.edu/~gurari/TeX4ht/mn.html); Xfig: les figures sont dessinées dans l’utilitaire X11 de Fig xfig (http://www.xfig.org); fig2dev: les figures sont exportées dans les formats EPS (« Encapsulated PostScript ») et PNG (« Portable Network Graphics ») grâce à l’utilitaire fig2dev (http://www.xfig.org/userman/installation.html); convert: certaines figures sont converties d’un format vers un autre par l’utilitaire convert (http://www.imagemagick.org/www/utilities.html) de ImageMagick Studio; HTML TIDY: les sources HTML générés par TeX4ht sont « beautifiés » à l’aide de HTML TIDY (http://tidy.sourceforge.net) ; vous pouvez donc les lire dans le source. Nous espérons que vous regardez cette page avec un navigateur libre: Firefox par exemple. Comme l’indique le choix de la licence GNU/FDL, tous les éléments permettant d’obtenir ces supports sont libres. Ce cours a bénéficié des relectures attentives et constructives de François Meunier, Léon Lim. Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 4 Initiation à l’algorithmique répartie ~~'~~ $ % # 3 Utilisation du cours Apprentissage en formation en ligne ♦ Démarche conseillée : Pour chaque page du support de cours, étudiez la page du support de cours (diapositive + commentaires) Étude des exercices en présentiel Puis auto-évaluation des connaissances avec les QCM (une série par section) Les QCM ainsi que les corrigés des exercices sont fournis à part dans moodle ~~&~~ NB : Certaines pages du cours sont marquées par un astérisque (« - ») à la fin de leur titre. Ceci correspond à un contenu d’approfondissement. Ne l’étudiez pas en détail avant de maîtriser les autres points de la section. Ces diapositives doivent être étudiées avant de faire certaines questions (optionnelles) des exercices. Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 5 Initiation à l’algorithmique répartie ~~'~~ $ % # 4 Plan du document 1 Éléments introductifs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 2 Élection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3 Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Exclusion mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5 Interblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6 Détection de terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 ~~&~~ Une définition communément admise d’un système réparti est : « plusieurs ordinateurs inter-connectés par un ensemble de réseaux de communication effectuant un travail ensemble et communicant par échange de messages ». Cette définition suggère deux propriétés principales des systèmes répartis : la non-unicité de lieu (un utilisateur travaille en local ou à distance) et la non-unicité de temps (chaque ordinateur possède sa propre notion du temps à travers son horloge physique). Par ailleurs, cette définition diffère de celle d’un système parallèle (ou dit fortement couplé) dans lequel les communications peuvent s’effectuer via une mémoire partagée et dans lequel il y a unicité de lieu et de temps. Les systèmes répartis sont difficiles à concevoir et à comprendre parce qu’ils ne sont pas intuitifs. Peutêtre est-ce aussi parce que notre vie est, par bien des aspects, fondamentalement séquentielle ? Nous devons donc développer une intuition pour la répartition. Dans cette discipline, il existe une tension inévitable entre les partisans de la modélisation et de l’analyse, et ceux de l’observation expérimentale. Cette tension illustre la dichotomie classique entre la théorie et la pratique. Dans ce cours d’algorithmique répartie, nous nous placerons plus du côté pratique. Nous commençons par la présentation du modèle de système réparti dans la section introductive. Ensuite, les problèmes étudiés sont des problèmes fondamentaux basiques de l’algorithmique répartie à partir desquels sont construites des architectures de services répartis complexes. Le principe de l’ élection est de partir d’une configuration dans laquelle tous les processus sont dans le même état, pour arriver dans une configuration dans laquelle un seul processus est dans l’état « gagnant » et tous les autres dans l’état « perdant ». La diffusion est une primitive de communication permettant à un processus d’envoyer le même message à tous les autres processus en respectant des propriétés d’ordre (FIFO, causal, total) dans la transmission des messages. L’ exclusion mutuelle consiste à faire circuler un jeton entre des processus répartis sur le réseau pour n’autoriser qu’un seul d’entre eux à entrer en section critique. C’est l’expression répartie des sémaphores. L’ interblocage se produit lorsqu’un ensemble de processus est tel que chacun d’eux tient au moins une ressource, et pour poursuivre sa progression, est en attente d’une ressource tenue par l’un des autres. Des algorithmes sont proposés pour prévenir ou détecter les interblocages. La détection de terminaison autorise qu’un algorithme réparti se termine de façon implicite, c’est-à-dire sans que les processus atteignent leur état final (fin du processus par appel de la fonction exit), autrement dit, « parce qu’il n’y a plus de travail à faire » (tous les processus sont en attente d’un message et les canaux de communication sont vides). Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 6 Initiation à l’algorithmique répartie ~~'~~ $ % # 5 1 Éléments introductifs 1.1 Modèle de système réparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Conventions de codage des algorithmes répartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Relation « arrivé avant » aussi appelée précédence causale, Lamport 1978 . . . . . . . 11 1.4 Vague et traversée de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 ~~&~~ Cette section introductive est reprise des références suivantes : G. Tel, Chapter 2 : The Model , dans Introduction to Distributed Algorithms , Cambridge University Press, pp. 43–72, 1994. C. Fidge. Logical Time in Distributed Computing Systems , dans IEEE Computer , pages 28–33, August 1991. G. Tel, Chapter 6 : Wave and traversal algorithms , dans Introduction to Distributed Algorithms , Cambridge University Press, pp. 177–221, 1994. H. Attiya et J. Welch, Chapter 2 : Basic Algorithms in Message-Passing Systems , dans Distributed Computing : Fundamentals, simulation, and advanced topics , Wiley, pp. 9–30, 2004. J.H. Saltzer, M.F. Kaashoek, Principles of Computer System Design : An Introduction , Morgan Kaufmann, 2009. Le premier élément d’introduction est le modèle de système réparti. Ce modèle à base de messages est utilisé dans tout le reste du cours. Il est assez général pour être utile aussi bien lors de la conception que lors de la vérification (même si nous ne nous focalisons par sur les preuves des algorithmes étudiés). Puis, nous introduisons les conventions de codage utilisées dans ce cours : soit l’orientation contrôle soit l’orientation évènement. Ensuite, le dernier élément général introduit pour la suite du cours est la notion de dépendance causale qui permet de construire un ordre partiel des évènements d’une exécution répartie. Enfin, parmi les problèmes fondamentaux que nous étudions, beaucoup peuvent s’exprimer à l’aide de sous-tâches génériques comme les vagues. C’est par exemple le cas de la diffusion ou de la détection d’interblocage étudiée un peu plus loin dans ce cours. Nous présentons donc à la fin de cette section le principe des algorithmes de vagues et y ferons référence dans les autres sections. Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 7 Initiation à l’algorithmique répartie 1 Éléments introductifs $ % # 6 ~~'~~ 1.1 Modèle de système réparti 1.1.1 Modèle de transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Synchronisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Types de défaillances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 ~~&~~ Les paramètres du système réparti les plus discriminants sont les suivants : synchronisme (« performance » des nœuds et du réseau), type de fautes des nœuds et des communications (catégorie de fautes matérielles et logicielles ), topologie (forme du graphe du système de communication) et déterminismes des processus (comportement prévisible des algorithmes répartis). Ces hypothèses sont importantes car elles conditionnent les résultats d’impossibilité (comme l’atteinte d’un consensus) ainsi que les approches algorithmiques. Par exemple, il n’existe pas de solution déterministe à tous les problèmes dans tous les cas. Mais, avant de détailler ces éléments discriminants, nous présentons les éléments constitutifs du modèle, c’est-à-dire dans notre cas ceux du modèle de transitions. Ce cours se limite à l’étude des algorithmes répartis déterministes. Ainsi, nous ne présentons pas d’algorithme avec comportement aléatoire, par exemple ceux du type « Las Vegas » (avec une solution correcte mais une distribution probabiliste sur la durée d’exécution) ou ceux du type « Monte Carlo » (avec une probabilité sur la correction de la solution mais un bornage de cette probabilité). Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 8 1 Éléments introductifs 1.1 Modèle de système réparti $ % # 7 ~~'~~ 1.1.1 Modèle de transitions Algorithme : assigne des valeurs à des variables Processus : exécution d’un algorithme sur un nœud du système réparti Canal de communication : lien logique réseau entre deux processus Exécution = état initial puis succession d’actions sur les états État global ou configuration = juxtaposition d’états locaux, un par processus Histoire = séquence des actions d’un processus ♦ Histoire répartie = ensemble des histoires locales des processus Répartition = ⇒ actions internes, d’émission et de réception Toute propriété est ou se décompose en propriétés de : ♦ Correction (en anglais, safety ) : une assertion est vraie dans chaque configuration de l’algorithme ♦ Vivacité ou progression (en anglais, liveness ) : une assertion est vraie dans certaines configurations de chaque exécution ~~&~~ Tous les modèles de spécification pour les systèmes répartis sont basés sur la notion d’action atomique et de machine à états. Parmi les modèles les plus couramment choisis, citons le modèle des transitions, le modèle des actions temporelles logiques, et le modèle des automates (pouvant être temporisés). Dans ce cours, nous utilisons le modèle le plus simple, celui dit des transitions, que nous décrivons maintenant. Un algorithme assigne des valeurs à des variables . Un état est l’affectation de valeurs à des variables. Une action (encore appelée un évènement ) a représente la relation entre un ancien état s et un nouvel état t notée s a t . Les actions sont atomiques : l’action a provoque le changement « instantané » de l’état de s à t . Autrement dit, on n’observe pas l’état du système pendant l’exécution de a. Un algorithme séquentiel A est un objet syntaxique construit selon la grammaire d’un langage de programmation. Une exécution de l’algorithme séquentiel A dans un processus P débutant à l’instant t à partir de l’état initial s [0], est la succession d’un nombre infini d’actions sur des états notée a [0] s [0] a [1] s [1] a [2] s [2] a [3], etc. L’état s [0] est appelé l’ état initial . L’action initiale a [0] est fictive et correspond à la création du processus P . L’exécution d’un algorithme séquentiel produit donc une séquence d’actions. La séquence d’actions est appelée l’ histoire de l’algorithme séquentiel. De façon duale, lorsqu’il s’agit de formuler ou de démontrer une propriété, il est souvent très intéressant de modéliser une exécution comme étant une séquence d’états, une action étant la transition d’un état à un autre [1] [,] [2] . Un algorithme réparti A est composé d’algorithmes séquentiels exécutés dans des processus P 1 ...Pn qui communiquent par échange de messages. L’action d’ émission émettre( Pj, m ) d’un message m de Pi vers Pj ajoute m au canal cij . Pratiquement, m est transmis de Pi vers Pj par le réseau de communication et est gardé dans la mémoire du nœud où s’exécute Pj . L’action de réception recevoir( m ) d’un message m par Pj sur l’ensemble des canaux cij assigne à m le premier message arrivé par l’un des canaux. Si aucun message n’est arrivé alors Pj attend jusqu’à l’arrivée d’un message par l’un des canaux. Toute action autre qu’une action d’émission ou de réception d’un message est appelée une action interne . L’ état d’un canal cij à l’instant physique t est constitué de l’ensemble des messages émis et non encore reçus. L’ état global (encore appelé configuration ) s d’un système réparti à l’instant physique t est composé des états locaux de tous les processus du système réparti à l’instant t . L’exécution d’un algorithme réparti débutant à l’instant physique t à partir de la configuration s est constituée de la juxtaposition des exécutions des processus. Par déduction, l’histoire répartie d’un système réparti est constituée de la juxtaposition des histoires des processus. R.W. Floyd. Assigning meanings to programs. In J.T. Schwartz, editor, Proceedings of Symposia in Applied Mathema- tics, Mathematical Aspects of Computer Science , volume 19, pages 19–32, Providence, Rhode Island, USA, 1967. American Mathematical Society. C.A.R. Hoare. An Axiomatic Basis for Computer Programming. Communications of the ACM , 12(10):576–580, October 1969. Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 9 1 Éléments introductifs 1.1 Modèle de système réparti Le modèle que nous venons de définir est appelé le modèle de transitions sous l’hypothèse de communi- cation asynchrone : les opérations d’émission ne sont pas bloquantes alors que les opérations de réception le sont. Dans le cas des communications synchrones , les opérations d’émission sont elles-aussi bloquantes. Dans ce cas, clairement, dans toutes les configurations dans lesquelles tous les processus viennent d’exécuter une action interne, les canaux sont vides. L’exécution d’un algorithme réparti est classiquement représentée par un diagramme de séquences (à la UML) aussi appelé diagramme temporel ou chronogramme. La figure qui suit trace un tel diagramme pour un algorithme réparti composé de trois algorithmes séquentiels. Le déroulement du temps est décrit par une ligne continue (ligne qui est à tiret et s’appelle « ligne de vie » en UML) pour chaque algorithme séquentiel. Les actions sont symbolisées par des tirets sur les « lignes de vie ». Les messages sont matérialisés par des flèches connectant une action émettre à une action recevoir. P P P 0 3 1 3 2 3 3 3 a0 1 a1 1 a 3 a3 a2 1 a3 1 a4 1 5 1 6 1 a a4 3 a5 3 a a7 1 Temps Col1 Col2 a 2 a1 2 a2 2 a3 2 4 a 2 a5 2 a6 2 a7 2 a8 2 Col4 Enfin, dans un système réparti, il est important de faire la distinction entre les propriétés de sûreté ou correction (en anglais, safety property ) et de progression ou vivacité (en anglais, liveness property ). La propriété de sûreté d’un algorithme est de la forme « l’assertion est vraie dans chaque configuration de l’algorithme », ou encore de façon informelle « l’assertion est toujours vraie ». Pratiquement, la propriété de sûreté sert à exprimer que quelque chose de non désiré n’arrive pas. La technique de base pour montrer que l’assertion est toujours vraie est de démontrer que c’est un invariant : vrai dans l’état de départ de l’exécution, et si vrai dans la configuration atteignable s alors vrai dans toutes les configurations atteignables directement à partir de s . La propriété de vivacité d’un algorithme quant à elle stipule que « l’assertion est vraie dans certaines configurations de chaque exécution de l’algorithme », ou encore que « l’assertion est vraie à terme ou ultimement ». La technique de base pour montrer que l’assertion est vraie à terme est soit d’utiliser une autre propriété de vivacité (par exemple, le message est reçu à terme par un processus atteignable car tous les canaux de communication du système transmettent in fine tous les messages émis par l’émetteur du canal), soit par induction en utilisant une métrique qui progresse dans le temps jusqu’à atteindre un seuil auquel l’assertion est vraie (pour le même exemple, parmi chaque pas d’exécution considérant l’émission ou la réception d’un message, de temps en temps, il y a un message qui s’approche de récepteur en récepteur du destinataire final, la métrique utilisée étant le nombre de processus entre l’émetteur initial et le destinataire final). Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 10 1 Éléments introductifs 1.1 Modèle de système réparti ~~'~~ Synchrone : 1.1.2 Synchronisme $ % # 8 ∧ Durée de transmission d’un message d’un nœud à un autre bornée et borne connue ∧ Durée d’éxécution d’une action interne d’un processus bornée et borne connue Asynchrone : ∨ Pas de borne ou borne inconnue sur la transmission d’un message ∨ Pas de borne ou borne inconnue sur la dérive des horloges ∨ Pas de borne ou borne inconnue sur la durée d’un traitement a. Il est important de ne pas confondre synchronisme des communications et synchronisme du système. Ici, c’est le synchronisme du système qui est considéré. ~~&~~ Un système réparti est dit « synchrone » si et seulement si : la durée de transmission d’un message d’un nœud à un autre est bornée et la borne est connue ; et, la durée d’exécution d’une action interne d’un processus est bornée et la borne est connue. Dans un tel système réparti, un processus émettant un message peut faire l’hypothèse qu’il est reçu, voire traité, après une durée limite calculable (car les bornes sont connues). Un système réparti est dit « asynchrone » s’il n’existe pas de borne (connue ou non) sur la transmission d’un message, la dérive des horloges ou la durée d’exécution d’une action interne. Dans la pratique, construire un algorithme pour un système asynchrone signifie ne pas s’occuper des caractéristiques matérielles (qualité des nœuds ou des communications). En d’autres termes, dès que des aspects temporels sont introduits dans les algorithmes (hypothèse sur les durées d’exécution ou de transmission, test de fiabilité de transmission à l’aide de temporisation, etc.), le système considéré n’est plus « complètement asynchrone », mais dit « partiellement asynchrone ». L’acception « partiellement asynchrone » recouvre le modèle « synchrone » et trente-et-un autres modèles, tous entre « complètement asynchrone » et « synchrone » [1] . Nous ne détaillons pas ces nombreux modèles et n’abordons pas la tolérance aux fautes dans ce manuscrit. C’est l’objectif des études d’articles réalisées par groupe dans le cadre du module. D. Dolev, C. Dwork, and L. Stockmeyer, On the minimal synchronism needed for distributed consensus , Journal of the ACM, 34(1), January 1987. Télécom SudParis - Denis Conan - Avril 2020 - CSC4509 11 1 Éléments introductifs 1.1 Modèle de système réparti $ % # 9 ~~'~~ 1.1.3 Types de défaillances Hormis lorsque précisé, les algorithmes présentés ne tolérent pas les défaillances Dans tous les cas, les défaillances arbitraires sont exclues de l’étude ~~&~~ Un processus ou un nœud (dans le cas où l’on ne considère qu’un processus par nœud) est dit « défaillant » lors d’une exécution si son comportement diffère de la spécification de l’algorithme qu’il exécute. Sinon, il est dit « correct ». Il en est de même pour les canaux de communication entre processus. Un modèle de défailla...