Le modèle multi-thread et la question de l’universalité du consensus [BMP19b] 

Télécharger le fichier pdf d’un mémoire de fin d’études

Modèles de panne

Il convient de différencier les différentes hypothèses de pannes pour les pro-cessus.
Pannes franches : Les processus peuvent s’arrêter par panne franche : un processus défectueux s’exécute correctement jusqu’à ce qu’il tombe en panne ; à ce point, il cesse de fonctionner. Un processus qui ne tombe pas en panne pendant une exécution est appelé correct. Le nombre total de processus tombant en panne lors d’une exécution apporte des restrictions sur certains résultats de calculabilité. Des hypothèses sur les bornes sur le nombre total de processus pouvant tomber en pannes lors d’une exécution peuvent donc être faites. Dans [MR01] par exemple, l’hypothèse d’une borne f < n2 (où n est le nombre de processus dans le système) est nécessaire pour proposer une solution au problème du consensus (présenté dans la section 2.4.1.).
Adversaires : Certains processus peuvent se comporter différemment de leur spécification et envoyer des données erronées de manière volontaire, dans le but de faire échouer les tâches en cours, ou de violer certaines propriétés pour certains objets. Ces adversaires sont appelés adversaires byzantins d’après le problème des généraux byzantins introduit par Lamport [LSP82]. Des solutions peuvent exister dans un système où de tels adversaires sont présents, mais souvent plus restrictives, comme le montre [bracha1987asynchronous] pour le problème du consensus par exemple.

Modèles d’arrivées

Cette dernière décennie, d’abord avec les systèmes pair-à-pair, puis avec le modèle multi-threading, l’hypothèse d’un système fermé avec un nombre fixe n de processus et où chaque processus connaît les identifiants de tous les processus est devenue trop restrictive. D’où le modèle d’arrivée infinie introduit dans [MT03]. Nous pouvons distinguer trois types de modèles ouverts : le modèle d’arrivées bornées, le modèle d’arrivées finies, et le modèle d’arrivées infinies. Plus précisément, les modèles de calcul se différencient par rapport aux restric-tions du nombre d’arrivées de processus, comme présenté dans [GMT01]. Dans ces modèles, un certain nombre de processus peuvent tomber en panne (ou quitter, de la même manière que dans le modèle classique), mais de nouveaux processus peuvent également rejoindre le réseau lors d’une exécution. Lorsqu’un processus rejoint un tel système, il n’est pas connu des processus déjà en cours d’exécution. Quatre modèles sont distingués dans [Agu04] : le modèle classique (ou fermé), ainsi que trois nouveaux modèles ouverts.
Modèle classique : Le nombre n de processus est fixe et peut apparaître dans le code local du processus. Les processus peuvent toujours tomber en panne, mais aucun nouveau processus ne rejoindra le système au cours d’une exécution. C’est dans ce système que la plupart des résultats et preuves de possibilité ou d’impossibilité ont été démontrés.
Modèle d’arrivées bornées : Au plus N processus peuvent participer lors d’une exécution. La borne N n’est connue, par les processus, qu’au début de chaque exécution, mais peut varier d’une exécution à l’autre. Cela signifie que de nouveaux processus peuvent rejoindre l’exécution au cours du temps, mais le nombre total de participants ne dépassera jamais la borne N de cette exécution.
Modèle d’arrivées finies : Un nombre fini de processus participe à chaque exécution. Ce nombre étant non borné, il n’est pas connu des participants, mais il est garanti que les processus arrêteront de rejoindre le système à terme.
Modèle d’arrivées infinies : De nouveaux processus peuvent continuer d’ar-river pendant toute l’exécution. Notons qu’à tout moment, le nombre de processus qui ont déjà rejoint le système est fini, mais peut croître à l’infini. Ce système est, du point de vue des processus, similaire au modèle d’arrivées finies, mais le fait qu’à tout moment un processus nouveau (et inconnu) puisse se rajouter au système apporte certains problèmes de concurrence et rend la synchronisation plus compliquée.
Remarque 1. Un cinquième modèle, M4, appelé concurrence infinie, a été in-troduit dans [Agu04], où une infinité de processus peuvent être présents dans le système et un nombre infini d’opérations peuvent avoir lieu dans n’importe quel intervalle de temps fini. Nous choisissons délibérément d’ignorer ce modèle car il pose un problème pour définir la linéarisation. Par exemple, supposons que, pour chaque i ≥ 1, le processus pi écrit la valeur i dans la variable x pendant h i l’intervalle 1 − 21i ; 1 − 2i1+1 ; alors p0 commence à lire x au moment 1. Il n’y a pas de « dernière valeur écrite » avant la lecture, donc la valeur de retour n’est pas bien définie. Restreindre la concurrence infinie à un sous-ensemble d’opéra-tions non conflictuelles ( par exemple lectures ou opérations sur différents objets) rendrait une concurrence infinie et une arrivée infinie équivalentes en terme de puissance de calcul comme nous pourrions utiliser facilement les conflits d’opéra-tions concurrentes pour contrôler l’arrivée des processus.

Cohérence et progression

Intuitivement, une « bonne » implémentation d’un objet partagé doit satisfaire deux types de propriétés : un critère de cohérence et une condition de progression, tout en respectant la spécification de l’objet. Le critère de cohérence spécifie la propriété de sûreté qui est la signification des résultats retournés, et la condition de progression spécifie les garanties sur la vivacité des opérations.

Critères de cohérence

Un critère de cohérence définit comment la concurrence affecte le comporte-ment distribué d’un objet. Formellement, il identifie les histoires partagées qui sont admissibles pour une spécification séquentielle donnée. Il faut différencier la cohérence forte et la cohérence faible, pour laquelle nous autorisons certains passage incohérents dans une histoire.

Cohérence forte

Il s’agit de visualiser un objet partagé comme s’il s’agissait d’un seul objet physique partagé par tous les processus. Cela signifie que toutes les opérations sur l’objet, éventuellement simultanées ou entrelacées, semblent avoir été exécutées atomiquement et séquentiellement. Cependant, ces implémentations sont souvent coûteuses, voire impossibles : le théorème CAP [GL02] indique que cette propriété est irréalisable dans la plupart des systèmes, car il est impossible de combiner une cohérence, une disponibilité et une tolérance aux partition élevées dans les systèmes asynchrones (Consistency, Availability, Partition tolerance). Les critères de cohérence faible ont été introduits pour surmonter ce problème.
Cohérence séquentielle : La cohérence séquentielle ([Lam79]) est le premier critère de cohérence forte introduit. Elle est définie comme suit.
Définition 7 (Cohérence séquentielle). Une histoire partagée est Séquentielle-ment cohérente si :
— Il existe une histoire séquentielle contenant toutes les opérations présentes dans l’histoire partagée (aucune opération n’a du être enlevée pour at-teindre la cohérence).
— L’ordre de processus est respecté pour tous les processus.
— Cette histoire histoire séquentielle respecte la spécification de l’objet.
Une histoire peut donc être séquentiellement cohérente même si certaines opé-rations sont ordonnées avant d’autres alors qu’elles leur sont ultérieures.
Linéarisabilité : La linéarisabilité [HW90] garantit que toutes les opérations renvoient la même valeur que si elles s’étaient produites instantanément à un instant donné dans le temps, appelé le point de linéarisation, entre leur invocation et leur réponse, éventuellement après avoir supprimé certaines opérations non terminées. Il faut donc considérer une histoire contenant comme évènements les invocations d’opérations, ainsi que les évènements de retour de ces opérations. Le point important de la linéarisabilité est le respect du temps réel par rapport à la cohérence séquentielle.
Définition 8 (Linéarisabilité). Une telle histoire est linéarisable si :
— l’histoire séquentielle obtenue par la projection des points de linéarisation des opérations respecte la spécification séquentielle de l’objet
— L’ordre des opérations dans l’histoire séquentielle respecte l’ordre temporel global : si le retour d’une opération a précède l’invocation d’une opération b dans le temps, alors a doit être placée avant b.

Cohérence faible

Afin de palier la difficulté (voir l’impossibilité) d’implémenter la cohérence forte, la cohérence faible a été introduite. Elle se différencie de la cohérence forte par la possibilité de renvoyer des valeurs incohérentes entre les différents pro-cessus. Les deux critères qui nous intéressent dans cette thèse sont ceux de la convergence et de la cohérence d’écriture. Ces deux critères ont la particularité de converger vers un état unique cohérent après de potentielles périodes d’inco-hérence.
Convergence [Vog09] : Le critère de convergence implique qu’après l’arrêt des opérations de mise à jour, les différents réplicats convergeront, à terme, vers un état identique, nommé état de convergence 1.
Définition 9 (Convergence). Une histoire est convergente pour un objet O si, lorsque tous les processus cessent d’exécuter des opérations de mise à jour, ils finissent par converger vers un état commun. Formellement, une histoire H est convergente si elle se trouve dans l’un des deux cas suivants :
— Les processus n’arrêtent jamais d’effectuer des écritures, c’est-à-dire que H contient une infinité d’opérations de mise à jour.
— Il existe un état de convergence tel que toute opération effectuée après que cet état ait été atteint est équivalente à la même opération effectuée dans l’état de convergence.
Il est utilisé en pratique dans de nombreuses applications à grande échelle telles que Dynamo, la base de donnée clé-valeur hautement disponible d’Amazon [DeC+07]. Il a été largement étudié et de nombreux algorithmes ont été proposés pour implémenter des objets partagés convergents.
Cohérence d’écriture [PMJ15] : La cohérence d’écriture renforce la conver-gence en déclarant que l’état de convergence doit pouvoir être obtenu dans une exécution séquentiellement cohérente. En d’autres termes, il peut être obtenu par un ordre séquentiel des opérations d’écriture de l’objet.
Définition 10 (Cohérence d’écriture). Une histoire est cohérente en écriture (ou update cohérente) pour un objet O si, lorsque tous les processus cessent d’exécuter des opérations de mise à jour, ils finissent par converger vers un état résultant d’une linéarisation des opérations d’écriture. Formellement, une histoire H est cohérente en écriture si elle se trouve dans l’un des deux cas suivants :
— Les processus n’arrêtent jamais d’effectuer des écritures, c’est-à-dire que H contient une infinité d’opérations de mise à jour.
— Il est possible d’omettre un nombre fini d’opérations de requête de telle sorte que l’histoire en résultant ait une linéarisation dans la spécification séquentielle de O.
D’un point de vue calculabilité, et de manière similaire à la convergence, il est possible d’implémenter n’importe quel objet avec le critère de cohérence d’écriture [PMJ15 ; PMJ16].

Conditions de progression

L’utilisation de verrous dans l’implémentation peut provoquer un blocage dans un système où les processus peuvent tomber en panne, en effet un processus peut détenir un verrou et tomber en panne, ne libérant ainsi pas ledit verrou. D’autres processus étant en attente de ce verrou seraient donc bloqués indéfini-ment. Certaines conditions de progressions telles que la deadlock-freedom [RD87] et la starvation-freedom [HS08] sont appelées conditions bloquantes, c’est à dire qu’elles sont rendues caduques dans le cas où ne serait-ce qu’un seul processus tomberait en panne. A l’inverse, les conditions telles que la wait-freedom [Her91] la lock-freedom [HW90], et l’obstruction-freedom [HLM03] ne dépendent pas du nombre de pannes dans le système (à part si tous les processus tombent en panne, dans ce cas aucune progression n’est possible évidemment). Ces conditions de pro-gressions sont appelées non bloquantes.
Les conditions de progression sont globales ou locales : alors que la wait-freedom garantit que chaque opération se termine après un temps fini, la lock-freedom garantit que, si le calcul s’exécute assez longtemps, au moins un processus progresse (cela peut conduire à une situation de famine pour certains processus). La wait-freedom est donc plus forte que la lock-freedom [DW15] : alors que la lock-freedom est une condition à l’échelle du système (globale), la wait-freedom est une condition propre au processus (locale). De même, alors que la deadlock-freedom est une garantie à l’échelle du système, la starvation-freedom est une condition
Conditions de progression bloquantes
Dans le cas d’un système asynchrone, ces conditions spécifient les conditions de progression en cas d’absence de panne franche lors de l’exécution.
Starvation-freedom [HS08] : La Starvation-freedom stipule que s’il n’y a aucune panne lors d’une exécution, alors tous les processus progressent et ter-minent.
Deadlock-freedom [RD87] : La Deadlock-freedom stipule que s’il n’y a au-cune panne lors d’une exécution, alors au moins un processus dans le système progresse.
Conditions de progression non bloquantes
Dans un système asynchrone où des pannes franches peuvent survenir, il faut que les conditions de progression soient non bloquantes, et ne dépendent donc pas de la présence ou non de pannes.
Wait-freedom [Her91] : La Wait-freedom est la condition de progression la plus forte, elle signifie qu’aucun processus ne peut être bloqué pendant un temps infini, et garantit donc la terminaison de toute opération commencée. C’est généralement la condition de progression désirée pour l’implémentation d’un objet partagé. C’est une condition de progression locale.
Définition 11 (Wait-freedom). Un algorithme A est wait-free si, pour toute exécution α de A, aucune opération ne prend un nombre infini d’étapes dans α.
Lock-freedom [HW90] : La Lock-freedom signifie qu’il y a à tout instant un processus qui progresse. c’est une condition globale qui garantit que le sys-tème dans sa globalité progresse, même si certains processus peuvent être bloqués indéfiniment.
Définition 12 (Lock-freedom). Un algorithme A est lock-free si, pour toute exé-cution α de A, au moins un processus n’a aucune opération prennant un nombre infini d’étapes dans α

Universalité et constructions universelles

Obstruction-freedom : L’Obstruction-freedom signifie que si un processus s’exécute seul pendant assez longtemps (sans que les processus pouvant faire obs-truction à sa progression n’interfèrent) il est garanti de progresser. Cette condition est plus faible que la lock-freedom : en effet, même si elle garantit toujours une tolérance aux pannes, il n’est pas garanti que le système progresse en présence de concurrence.
La question de l’universalité a toujours été centrale dans tous les domaines scientifiques. Que peut-on faire avec un outil et un contexte donnés, et surtout qu’est ce qui ne peut pas être fait avec un tel outil. En informatique séquentielle, l’universalité est représentée par une machine de Turing qui peut calculer tout ce qui est calculable. Un problème central du calcul distribué est l’accord, résumé par le problème du consensus. Dans le contexte des systèmes distribués, nous savons depuis 1985 et le fameux résultat d’impossibilité FLP que le problème du consensus n’a pas de solution déterministe dans un système distribué où même un seul processus peut tomber en panne [FLP85]. Cette impossibilité n’est pas due à la puissance de calcul des processus individuels, mais plutôt à la difficulté de coordination entre les différents processus qui composent le système distribué. Les problèmes de coordination et d’accord sont donc au cœur de la calculabilité dans les systèmes distribués [HRR13].
On dit qu’un modèle de calcul distribué M est Wait-free universel (ou simple-ment universel) si n’importe quel objet avec une spécification séquentielle peut être implémenté de manière wait-free et linéarisable dans M. Par extension, un objet O est dit universel dans M si M[O] (le système M enrichi de l’objet O) est universel. Afin de classer les objets selon leur puissance de synchronisation, Herlihy a proposé un classement appelé Hiérarchie wait-free [Her91], qui trie les objets par numéro de consensus croissant.
Définition 13 (Numéro de consensus). Soit O un objet. On dit que O a le numéro de consensus n ∈ N si O est universel dans un système à n processus mais pas dans un système à n + 1 processus. O a un numéro de consensus infini (∞) s’il est universel pour tout n.

 Consensus

Définition 14 (consensus). Le problème du consensus vise à atteindre un ac-cord entre plusieurs processus proposant chacun une valeur, et décidant tous une unique valeur. Il vérifie trois propriétés :
Validité Toute valeur décidée fait partie des valeurs proposées.
Accord Deux processus ne peuvent pas décider deux valeurs différentes.
Terminaison Si un processus est correct, il finit par décider une valeur.
Maurice Herlihy a prouvé dans [Her88] que le consensus est universel dans les systèmes distribués classiques composés d’un ensemble de n processus. A savoir, tout objet ayant une spécification séquentielle a une implémentation wait-free et linéarisable utilisant uniquement des registres de lecture / écriture (emplace-ments de mémoire) et un certain nombre d’objets de type consensus. Cela fait du consensus un objet de numéro de consensus infini.
Une variante du consensus appelée consensus binaire (parfois appelée consen-sus booléen) propose un processus de décision parmi deux valeurs possibles. Le consensus « classique » est donc aussi appelé consensus multi-valué.
Définition 15 (Consensus binaire). Le problème du consensus binaire vise à atteindre un accord entre plusieurs processus proposant chacun une valeur parmi deux valeurs possibles, et décidant tous une unique valeur. Il vérifie les trois même propriétés que le consensus :
Validité Toute valeur décidée fait partie des valeurs proposées.
Accord Deux processus ne peuvent pas décider deux valeurs différentes.
Terminaison Si un processus est correct, il finit par décider une valeur.
Il est possible d’implémenter le consensus multi-valué à partir du consensus binaire comme démontré dans [MRT00], ce qui rend ces objets équivalents dans la hiérarchie de Herlihy.
Certaines instructions matérielles spécifiques atomiques permettent d’implé-menter intuitivement le consensus.
Définition 16 (Compare&swap). L’opération matérielle spécifique compare&swap
fonctionne de la manière suivante : l’appel de compare&swap sur X, X.compare&swap(attente, v), vérifie si la valeur contenue dans X est égale à la valeur attente, et si oui, rem-place la valeur contenue dans X par la valeur v et renvoie true. L’opération renvoie false sinon. Tout cela se déroule de manière atomique. Pour implémen-ter le consensus sur une variable X initialisée à ⊥ (valeur vide), il suffit d’ap-peler X.compare&swap(⊥, v), puis de lire la valeur de X. Une seule valeur sera écrite, et puisque l’opération est atomique, tous les autres processus obtenant false lors de leur invocation de compare&swap n’auront donc pas pu modifier la va-leur contenue dans X, et le consensus est ainsi atteint avec pour valeur décidée l’unique valeur écrite dans X.
Le consensus dans les systèmes ouverts Le consensus fut à la base étudié d’abord dans des systèmes synchrones ([PSL80]), puis dans les systèmes asyn-chrones ([FLP85]). Des solutions ont enfin été proposées dans le modèle d’arrivées infinies :
— Dans [ASS02], pour répondre au problème du consensus binaire, un sys-tème de votes et de poids permet aux processus de décider même en pré-sence d’adversaires. Plus un participant arrive tard dans le système, moins son vote a de poids dans la décision finale.
— Dans [CM05], une variante du protocole Paxos ([Lam+01]) est étendue à un nombre infini de processus pour résoudre le problème du consensus en mémoire partagée.
— Dans [MT03], le consensus pour une infinité de processus est atteint à l’aide de consensus pour un nombre fini de processus, et d’objets test&set. Pour cela un nombre d’objets test&set est utilisé pour permettre à un nombre t de processus de participer à un consensus pour t participants.
Définition 17 (Test&set). L’opération matérielle spécifique Test&set fonc-tionne de la manière suivante : l’appel de test sur un objet Test&set X (initialisé à false), X.test&set(), vérifie que la valeur contenue dans X est false, et si oui, remplace la valeur de X par true et renvoie true, et renvoie false sinon. Cette opération étant atomique, seul un processus peut obtenir le résultat true. Cette opération matérielle a pour numéro de consensus 2.

Objets au numéro de consensus infini dans la hié- rarchie de Herlihy

Dans la hiérarchie de Herlihy, tous les objets ayant un numéro de consensus infini ne sont pas distinguables au vu d’un système classique à n processus, mais sont-ils pour autant équivalents dans les modèles ouverts ?
Le consensus a été utilisé comme base de raisonnement sur la calculabilité dans ces modèles [AMW11], et déjà une séparation en terme de calculabilité entre les objets ayant un numéro de consensus infini est apparue : il existe un objet de numéro de consensus infini qui, bien qu’il soit capable de réaliser un consensus pour n’importe quel nombre de processus n (même si n est inconnu à l’avance), ne peut pas résoudre le consensus face à une concurrence illimitée. L’objet en question est l’Iterator Stack (ou IStack, son fonctionnement est montré dans la section 3.1), et il est démontré que l’Iterator Stack permet d’implémenter le consensus dans un modèle d’arrivées finies, mais pas dans le modèle d’arrivées infinies moins restrictif. Cela marque une séparation entre les modèles d’arrivées finies et infinies dans la classe des objets de numéro de consensus infini.

Constructions universelles

Pour prouver l’universalité du consensus, Herlihy a introduit la notion de construction universelle 2. Il s’agit d’un algorithme générique qui, étant donné une spécification séquentielle de tout objet dont les opérations sont totales 3, fournit une implémentation concurrente de cet objet.
Constructions universelles wait-free et linéarisable
Construction universelle wait-free, linéarisable, sur base d’objets LL/SC (Linked Load / Store Conditionnal, avec mécanisme d’entraide Pro-posée dans [Ray17], Cette construction universelle en mémoire partagée se base sur des objets LL/SC, et un objet Collect. L’objet LL/SC est composé de trois opérations : soit X un emplacement mémoire,
— X.LL renvoie la valeur de X.
2. Une petite visite guidée sur les constructions universelles se trouve dans [Ray17].
3. Cela signifie que toute opération sur l’objet peut être appelée et l’appel retourne quel que soit l’état de l’objet.
— si un processus p invoque X.SC(v), alors X est mis à v si aucun autre processus n’a modifié X depuis la dernière invocation de X.LL par p, et renvoie true, false sinon.
— si un processus p invoque X.LL, alors si aucun autre processus n’a pu invoquer X.SC(v) avec succès depuis le dernier appel de X.LL par p, cela renvoit true, false sinon.
Cet objet permet à un processus de modifier une valeur sans que celle ci ait été modifiée depuis sa dernière lecture, et ainsi d’éviter des incohérences dans les données : par exemple si deux processus essaient d’incrémenter un compteur concurremment, si les deux processus lisent une valeur x et essaient d’écrire x+1, alors le résultat final sera x + 1 au lieu de x + 2, l’utilisation d’un LL/SC évite ce problème.
L’objet Collect est un vecteur de valeurs dont les cases sont détenues par cha-cun des processus, qui leur permet de mettre à jour leur valeur, ou de « collecter » la totalité des valeurs du vecteur, de manière non atomique.
La construction universelle proposée dans [Ray17] fonctionne de la manière suivante :
1. lorsqu’un processus invoque une opération o, il l’insère d’abord dans un objet Collect
2. dans un second temps, le processus collecte toutes les valeurs de l’objet Collect (donc l’ensemble des opérations que les processus essaient d’invo-quer).
3. il essaie ensuite d’ajouter toutes les opérations collectées précédemment dans un objet LL/SC.
Ceci correspond à un mécanisme d’entraide formalisé dans [CPT15]. Ce mé-canisme nécessite que tout processus, avant de terminer son fonctionnement, aide les processus ayant des opérations en attente, ceci afin d’atteindre la wait-freedom.
D’autres constructions universelles basées sur un objet Collect et le même principe d’entraide, mais avec d’autres objets que le LL/SC, comme le consensus et l’instruction spécifique Compare&swap, sont présentées dans [Ray17].
Construction universelle wait-free, linéarisable, sur base d’opérations
Fetch&Cons, sans entraide Une opération fetch&cons sur une liste l, avec en argument une valeur v, exécute atomiquement les deux opérations suivantes :
1. Concaténation de v à la tête de la liste l.
2. Retour de l’entièreté de la liste l qui précède v (sans v).
Une construction universelle utilisant pour base cette opération est proposée dans [Her88]. Le fonctionnement est assez simple : un processus invoquant une opération o fait un appel à f etch&cons(v, l). Étant atomique, cette opération fetch&cons a un point de linéarisation (cela garantit la linéarisabilité : l’ordre total des opérations est l’ordre des points de linéarisation). Le processus exécute ensuite localement la liste des opérations retournée depuis l’état initial de l’objet, pour connaître l’état dans lequel évaluer son opération, puis exécute son opération.
Dans [CPT15], en supposant qu’une opération sur les liste fetch&cons soit dis-ponible et fonctionne sans mécanisme d’entraide 4, il est montré que la propriété d’absence d’entraide (help-free dans la littérature) reste vraie pour cette construc-tion universelle, étant donné qu’aucun mécanisme d’entraide supplémentaire n’est ajouté.
Constructions universelles wait-free et faiblement cohérentes
Les constructions universelles existent aussi en cohérence faible : [PMJ15] in-troduit une construction universelle update cohérente dans un système par passage de messages.
Construction universelle wait-free, update cohérente Cette construction universelle construit un ordre total sur les opérations de mises à jour sur lequel tous les participants sont d’accord a priori, puis réécrit l’historique a posteriori quand de nouveaux messages arrivent (Cet ordre est construit à partir d’une horloge de Lamport [Lam78]). Tous les processus atteignent donc finalement l’état correspondant à l’histoire séquentielle commune. Lorsqu’un processus appelle une opération, une mise à jour est émise localement, le processus l’horodate et informe tous les autres processus en diffusant un message pour tous les autres processus. Tous les processus seront donc éventuellement informés de toutes les mises à jour, ce qui assure la convergence des différents processus. Quand un processus veut effectuer une lecture sur l’objet, il rejoue localement toute la liste des événements de mises à jour dont il a conscience à partir de l’état initial, puis il exécute la requête sur l’état qu’il vient d’obtenir. Les messages arrivant « à terme », il ne peut exister qu’un nombre fini de lectures sur des états incohérents, ce qui garantit bien la cohérence d’écriture (si les processus n’arrêtent jamais d’invoquer des écritures, le critère de la cohérence d’écriture est respecté par définition).
Cette construction universelle update cohérente a pour avantage qu’un seul message est envoyé par opération de mise à jour de l’objet.

Sous-modèles

En gardant les mêmes hypothèses vis à vis de tous les critères d’un modèle mentionnés (communication, synchronie, pannes, arrivées), il est possible de res-treindre les algorithmes à certaines formes précises pour gagner en simplicité et en efficacité : Cela donne lieu à des sous-modèles. Le cas que nous allons aborder est celui du modèle opérationnel pour la cohérence faible en système par passage de message, introduit pour l’implémentation des CRDT.
Complexités Les critères de complexités que nous pouvons étudier sont les suivants :
— La complexité en mémoire locale (aussi appelée complexité spatiale), c’est à dire la quantité de données stockée par chaque processus au long d’une exécution. Cette complexité dépend généralement du nombre de processus présents lors d’une exécution, et/ou du nombre d’opérations effectuées dans ladite exécution.
— La complexité en nombre de messages envoyés par opération (aussi appelée complexité en communication). Cette complexité dépend généralement du nombre de processus présents lors d’une exécution.
— La complexité en taille des messages envoyés. Cette complexité dépend généralement du nombre de processus présents lors d’une exécution, et/ou du nombre d’opérations effectuées dans ladite exécution.
CRDT et modèle opérationnel Les types de données répliquées sans conflits (ou CRDT) [Sha+11] constituent une famille d’objets spécialement conçus pour répondre au critère de convergence. Ceux-ci sont basés sur un théorème énonçant l’équivalence entre deux types d’objets : les types de données répliquées commuta-tives (CmRDT), dans lesquelles toutes les opérations de mise à jour commutent, et les types de données répliquées convergentes (CvRDT), dont les états forment un treillis. Par exemple, le G-set (Grow-Only set, ensemble strictement croissant) fournit deux opérations différentes : une opération de mise à jour qui insère un élément et une opération de requête qui lit si un élément spécifique se trouve dans l’ensemble. Sur le point de vue CmRDT, insérer x et insérer y commutent. Du point de vue CvRDT, l’inclusion de l’ensemble est un ordre formé par le treillis sur les états de l’ensemble. Le modèle opérationnel a été proposé pour abstraire la mise en œuvre des CRDT. Dans le modèle opérationnel, chaque processus conserve un état local sur lequel les opérations sont effectuées. Une opération de mise à jour est divisée en deux facettes. Tout d’abord, l’opération de mise à jour est préparée localement par le processus d’où l’opération de mise à jour est émise, puis un message est diffusé pour informer tous les autres processus. Deuxième-ment, l’état local de chaque processus est mis à jour à la réception du message de mise à jour. Grâce à la commutativité, tous les réplicats convergent vers le même état lorsqu’aucune opération de mise à jour n’est en cours.
Comme un seul message est diffusé par opération de mise à jour, les algo-rithmes du modèle opérationnel sont, par conception, optimaux en termes de nombre de messages utilisés. La quantité de métadonnées qui doivent être sto-ckées par chaque processus pour garantir la convergence, ou la taille des messages à envoyer est plus problématique et a été largement étudiée pour plusieurs objets, notamment les ensembles (OR-set : O(n log(m)) en complexité spatiale, avec n le nombre de processus, et m le nombre d’opérations de mise à jour effectuées), les compteurs (O(n) en complexité spatiale) et les registres (O(m) en complexité spatiale) dans [Bur+14], les bases de données (borne inférieure sur la taille des messages en O(n log(m))) dans [AEM17] et les éditeurs collaboratifs (O(|l| + D) où l est la liste représentant l’éditeur collaboratif, et D le nombre de suppressions d’éléments de la liste) dans [Att+16]. Malgré le fait que les algorithmes du mo-dèle opérationnel soient naturellement tolérants aux partitions (En effet, dans ce modèle, l’état de l’objet dépend uniquement de l’ensemble des messages reçus. Si l’on dispose d’un mécanisme de diffusion fiable, les ensembles de messages reçus dans les différentes partitions convergent lorsque ces partitions sont résolues) et minimisent le nombre de messages nécessaires à leur mise en œuvre, le modèle opérationnel impose des limitations sur la forme de ses algorithmes admissibles. Il n’est par exemple pas autorisé d’accuser réception ou de retransmettre des messages, d’exécuter des étapes locales sans réception de message, ou de propa-ger des informations lors des opérations de lecture. Cela empêche les algorithmes d’utiliser des techniques plus avancées telles que les schémas de message utilisés par les algorithmes de checkpointing [Bal+95 ; RLT78] 5. De tels algorithmes sont généralement étudiés dans le modèle wait-free par passage de message ou plus sim-plement modèle wait-free, dans lequel les processus asynchrones communiquent en envoyant et en recevant des messages. N’importe quel nombre de processus peut tomber en panne, ce qui capture également la tolérance aux partitions car il est impossible pour un processus d’attendre un accusé de réception de tout autre processus car tous les autres processus peuvent être tombés en panne.
Le modèle opérationnel et les CRDT sont naturellement adaptés aux modèles ouverts, car la convergence est atteinte lorsque tous les messages sont reçus par l’ensemble des participants.

Table des matières

1 Introduction 
2 Etat de l’art 
2.1 Définitions préliminaires
2.2 Description d’un modèle
2.2.1 Modèles de communication
2.2.2 Modèles de synchronie
2.2.3 Modèles de panne
2.2.4 Modèles d’arrivées
2.3 Cohérence et progression
2.3.1 Critères de cohérence
2.3.2 Conditions de progression
2.4 Universalité et constructions universelles
2.4.1 Consensus
2.4.2 Objets au numéro de consensus infini dans la hiérarchie de Herlihy
2.4.3 Constructions universelles
2.5 Sous-modèles
3 Description des modèles utilisés 
3.1 Seconde partie : communication par mémoire partagée
3.2 Troisième partie : communication par passage de message
4 Le modèle multi-thread et la question de l’universalité du consensus [BMP19b] 
4.1 L’abstraction du journal faiblement cohérent
4.2 Une construction universelle
4.3 Du consensus au journal faiblement cohérent
4.4 Du compare&Swap au journal faiblement cohérent
4.5 Conclusion
5 Extension de la hiérachie des modèles wait-free aux modèles ouverts [PMB20] 59
5.1 L’allocation infinie de mémoire n’est pas nécessaire dans M1
5.2 Aucun object ne possède le numéro de consensus ∞1 1
5.3 Le consensus booléen a le numéro de consensus ∞3
1
5.4 Le registre fenêtré a le numéro de consensus ∞2 1
5.5 Objets ayant pour numéro de consensus ∞3 2
5.6 Conclusion
6 Constructions universelles faiblement cohérentes dans un système par passage de message : études des complexités spatiales
et de communication [BMP19a] 83
6.1 Une construction universelle dans le modèle opérationnel
6.2 Comparaison des modèles de calcul
6.3 Une solution pratique
6.4 Conclusion
7 Conclusion 105
7.1 Résumé
7.2 Perspectives futures
Bibliography 109

Télécharger le rapport complet