Soutenance mémoire
État de l’art
Le problème du consensus et les comportements byzantins ont été introduits par Lamport, Shostacket et Pease en 1982 [9, 10]. Ce sont dans ces mêmes articles qu’il a été prouvé qu’il est nécessaire et suffisant d’avoir n > 3t (où n est le nombre total de processus et t le nombre maximal de processus fautifs) pour résoudre le problème du consensus byzantin dans un environnement ne contenant que des liens synchrones. Ce résultat implique trivialement l’impossibilité du consensus byzantin pour n ≤ 3t avec des hypothèses de synchronie quelconques (système asynchrone, présence ou non de bi-sources, etc. ).
Il a cependant été démontré que dans un système dans lequel tous les liens sont asynchrones, le problème du consensus ne peut être résolu. Ce résultat, qui est sûrement l’un des plus importants de l’algorithmique réparti, a été démontré par Fisher, Linsh et Paterson. Il est donc connu sous le nom de FLP.
La première approche pour affaiblir les hypothèses de synchronie est de considérer des liens partiellement synchrones, c’est-à-dire des liens qui ne seront synchrones non pas depuis le début, mais seulement à partir d’un certain temps non connu a priori. La notion de lien partiellement synchrone a été introduite par Dwork, Lynch et Stockmeyer dans [5].
Une autre approche a été de limiter le nombre de liens partiellement synchrones. Aguilera, Delporte-Gallet, Fauconnier et Toueg ont tout d’abords montré qu’il était suffisant, dans le cas du consensus avec crashs, d’avoir un processus correct p dont tous les liens sont partiellement synchrones en sortie [1] (c’està- dire que pour tout processus q, le lien p → q est synchrone). On appelle un tel processus une ⋄source. Ces mêmes auteurs ont ensuite démontré que, dans le cas du consensus byzantin, [3], il était suffisant d’avoir un unique processus p (que l’on qualifiera de ⋄bi-source) possédant tous ses liens partiellement synchrones (cette fois ci pour tout processus q, les liens p → q et q → p sont partiellement synchrones). Les autres liens entre les autres processus pouvant être asynchrones.
Enfin les derniers résultats ont démontré qu’il n’était pas nécessaire que l’unique bi-source ne possède que des liens synchrones. En particulier, dans le cas du consensus avec crashs, la ⋄source doit seulement posséder t liens partiellement synchrones en sortie [2]. Dans la cas du consensus byzantin avec signatures, Hamouma, Mostefaoui et Trédan ont montré qu’une ⋄[t+1]bi-source (un processus correct possédant t + 1 liens partiellement synchrones avec d’autres processus corrects) était suffisante [7]. De plus, ces mêmes auteurs ont montré (dans un papier inédit) que dans le cas du consensus byzantin sans signatures, une ⋄[2t + 1]bi-source suffisait.
Si la présence de liens synchrones permet de résoudre le problème du consensus, cela est surtout dû au fait qu’ils permettent aux processus corrects de détecter les crashs. En effet si un lien entre deux processus p et q est synchrone, alors si p envoie un message à q à l’instant T, q recevra le message à l’instant T + δ et p recevra la réponse à l’instant T + 2δ ; si p n’a pas reçu la réponse, alors p sait que q a crashé.
C’est pourquoi une nouvelle approche a été introduite pour définir la limite permettant de résoudre le problème du consensus. Elle consiste à modéliser l’information que chaque processus possède sur le système par un oracle. Cette notion a été introduite par Chandra, Hadzilacos et Toueg en 1996 [4] dans les cas des systèmes avec crashs. Elle a été ensuite généralisée pour les systèmes byzantins par Kihlstrom, Moser et Melliar-Smith en 2003
Étude d’un protocole de consensus byzantin avec signatures
Dans le cas du consensus byzantin avec signatures (les processus signent leur messages grâce à de la cryptographie asymétrique) il a été démontré, comme nous l’avions indiqué précédemment, dans [7] qu’une ⋄[t + 1]bi-source suffisait pour résoudre le problème du consensus. Ce papier propose en effet un algorithme qui, s’il est intéressant en théorie, n’est pas vraiment conçu pour un usage pratique. En particulier 6 étapes au moins sont nécessaires avant que les processus décident. Dans la suite de cette partie, nous détaillerons ce protocole et nous proposerons deux améliorations pour terminer plus rapidement dans le meilleur des cas.
Le protocole
Principes généraux
La structure de ce protocole est relativement classique. Elle consiste en une suite de rondes. Chaque ronde étant dirigée par un coordinateur. Au début de la ronde ρ, le processus coordinateur p propose une valeur qui sera décidée par tous les processus si p est une [t + 1]bi-source. Si par contre p n’est pas une bi-source, il se peut que les processus ne décident pas pendant cette ronde ; dans ce cas une nouvelle ronde ρ + 1 commence avec un autre coordinateur.
Signatures et authentification des messages
Généralement, un protocole réparti se résume en une série d’étapes, chaque étapes se déroulant en deux temps. Tout d’abord chaque processus envoie un message à tous les autres processus ; ensuite chaque processus attend pour recevoir un maximum de messages. En pratique, dès qu’un processus a reçu n−t messages, il passe à l’étape suivante. En effet, étant donné qu’il y a t processus fautifs, il se peut qu’ils n’aient pas envoyé leur message lors de cette étape.
Donc, attendre plus de n−t messages peut bloquer l’exécution d’un processus. Afin d’empêcher les processus byzantins d’avoir un comportement non conforme au protocole, chaque processus doit prouver que le message qu’il envoie à l’étape ei+1 est compatible avec les messages qu’il a reçus lors de l’étape précédente ei. Pour cela à chaque fois qu’un processus pi envoie un message mi à l’ensemble des processus, il envoie le message signé avec sa clé privée hmii et il y joint les n − t messages reçus à l’étape précédente. Ces n − t messages étant signés par leur expéditeur d’origine, un processus byzantin ne peut pas les modifier.
Déroulement du protocole
Pendant l’exécution du protocole, le processus pi utilise la variable esti pour stocker la valeur qu’il pense décider. Ainsi, au commencement du protocole, chaque processus correct aura sa variable esti initialisée à la valeur qu’il propose ; à la fin de l’exécution du protocole, la variable esti correspondra à la valeur décidée.
Le protocole consiste en trois threads qui tournent en parallèle, le premier thread, le principal, correspond à la succession des rondes. Le second, appelé thread de coordination, est le thread dans lequel les processus coordinateurs vont tenter de forcer le consensus en proposant une valeur. Enfin le dernier thread est celui qui va faire terminer un processus lorsqu’un message DEC est reçu.
On note alors Vi l’ensemble des valeurs auxj reçues à cette étape par le processus pi (ligne 15). S’il existe une valeur v telle que Vi = {v}, le processus pi dans ce cas exécute auxi ← v, sinon, pi a découvert que le processus coordinateur n’était pas une bi-source (au moins pendant cette ronde) et va tenter d’empêcher la décision lors de cette ronde en mettant auxi à ⊥. Second filtrage Cette ronde, comme les deux précédentes, commence par l’envoi des variables auxi. Lors de cette étape, nous sommes sûrs que l’ensemble des valeurs auxi envoyées est de la forme {v, ⊥} ou {v}. En effet, pour envoyer une valeur auxi = v lors de cette étape, un processus doit l’authentifier par n−t signatures, dont n − 2t provenant de processus corrects. Or deux ensembles de taille au moins n−2t possèdent au moins un processus correct en commun (car n > 3t), processus qui n’a pas pu signer pour deux valeurs distinctes.
Si un processus pi reçoit un ensemble Vi de la forme {v}, alors il considère qu’il peut décider. Sinon, l’ensemble des valeurs reçues étant de la forme {v, ⊥}, chaque processus (correct ou non) qui ne décide pas doit mettre esti à v, et dans ce cas v sera la seule valeur qui pourra être décidée lors de la suite du protocole.
Pour une démonstration plus détaillée des propriétés de terminaison, de validité et de correction, le lecteur pourra se référer à l’article original [7].
Terminaison rapide dans le meilleur des cas
Le protocole décrit dans la partie précédente termine dans le meilleur des cas relativement lentement. Il est en effet constitué d’une étape d’initialisation et de rondes de 4 étapes. Ainsi, dans le meilleur des cas, le protocole termine en 6 étapes (en comptant l’envoi des messages dec), ce qui est assez important.
Nous présentons dans cette partie deux améliorations (en terme de nombre d’étapes) de ce protocole . Pour rappel ce protocole est correct avec l’hypothèse n > 3t (où n est le nombre total de processus et t le nombre maximal de processus fautifs) et l’existence d’une ⋄[t + 1]bi-source.
La première amélioration que nous proposons permet de terminer rapidement si tous les processus sont corrects et si le premier coordinateur est une [n]bisource en seulement deux étapes. Il est cependant nécessaire pour cela que tous les processus proposent initialement la même valeur. De même si lors d’une ronde, tous les processus se comportent de manière correcte et que le processus coordinateur est une [n]bi-source, alors la décision ce fera lors de la deuxième (au lieu de la quatrième) étape de cette ronde. Si le meilleur cas n’est pas atteint, ce protocole se comporte comme l’original et tout comme ce dernier, nécessite pour être correct une ⋄[t + 1]bi-source et n > 3t.
Il est cependant possible de proposer une autre amélioration qui termine rapidement même en présence de fautes byzantines. Cette fois ci, la terminaison rapide nécessite que le premier processus coordinateur soit une [n − t]bi-source et que tous les processus corrects proposent la même valeur (on remarquera que l’on autorise les comportements byzantins pour les processus fautifs). De même, si lors d’une ronde le processus coordinateur est une [n−t]bi-source, la décision se fera lors de la deuxième (au lieu de quatrième) étape de cette ronde. Le prix à payer pour autoriser les comportements byzantins même dans les cas favorables est que le protocole nécessite dorénavant pour être corrects n > 5t.
Terminaison rapide pour n>3t
Cette partie présente un protocole qui termine dans tous les cas avec n > 3t et une ⋄[t + 1]bi-source. Dans le meilleurs des cas, seules deux étapes sont nécessaires pour atteindre le consensus. Le meilleur des cas étant défini par les trois conditions suivantes :
– tous les processus sont corrects ;
– le coordinateur est une [n]bi-source ;
– tous les processus corrects proposent la même valeur.
De même si lors d’une ronde, ces trois conditions sont vérifiées, alors la décision se fera prématurément avant la fin de la ronde (2 étapes au lieu de 4).
Les variables supectedi, byzantini, asynchi sont initialisées à ∅, la variable leaderi est initialisée à p0. Au commencement, chaque processus considère donc que tous les processus sont corrects, choisit p0 comme leader et considère que le système ne contient que des liens synchrones.
Il suffit alors pour les processus de partager l’information à leur disposition.
La présence de signatures permet d’empêcher les processus byzantins de donner des informations non prouvées.
– À chaque fois qu’un processus reçoit un message, il le fait suivre à tous.
– À chaque fois qu’un processus p remarque qu’un lien p → q est asynchrone, il envoie un message asynchrone(p, q) à tous les processus.
– À chaque fois qu’un processus p remarque qu’un processus q a commis une faute de commission (par exemple si un processus a envoyé deux messages distincts lors d’une même étape, ou si un processus envoie un message incompatible avec les messages qu’il a précédemment reçus), il envoie byzantin(q) et la preuve (c’est-à-dire les messages signés par q qui prouvent la faute de commission) à tous les processus.
Il suffit alors pour les processus de mettre à jour l’ensemble byzantini à chaque fois qu’ils reçoivent un message de la forme byzantin(∗) et l’ensemble asynch à chaque fois qu’ils reçoivent un message de la forme asynchrone(∗). On remarque qu’à partir d’un certain moment, que nous noterons τ , les ensembles byzantini et asynchi ne changeront plus et seront communs à tous les processus corrects. Or l’ensemble asynchi permet de partitionner l’ensemble Π des processus en composantes connexes. Cette décomposition sera donc la même pour tous les processus corrects à partir de τ . Le graphe ainsi défini ne peut pas être (t, S)-ambigu par hypothèse. Donc il existe une composante connexe C tel que l’on ait soit |C| ≥ t+1, soit Π \ C ne vérifie pas les hypothèses S. Dans les deux il existe forcément un processus correct dans ce cluster que nous noterons pcorrect.
Notons pC le processus du cluster C avec le plus petit indice, il suffit alors pour chaque processus d’exécuter leaderi ← pC. Il est aisé de voir qu’ainsi, à partir du temps τ , tous les processus auront élu le même leader. Il suffit alors de montrer que ce leader est correct.
Supposons que cela ne soit pas le cas, alors cela veut dire que ce processus commet soit une faute d’omission, soit une faute de commission (si ce n’est pas le cas, cela signifie qu’il se comporte comme un processus correct). Si pC commet une faute d’omission, alors il n’envoie pas un message qu’il est censé envoyer à tous les processus. Mais s’il n’envoie pas ce message, cela veut dire que pcorrect découvrira que le lien pcorrect → pC est asynchrone, et donc modifiera la variable asynchi. Absurde car par définition de τ , les variables ne sont plus modifiées.
Si par contre pC commet une faute de commission, alors tous les processus s’en rendront compte (car à chaque fois qu’un processus correct reçoit un message, il le transmet à tous les autres processus corrects), et les variables byzantini seront modifiées. Absurde par définition de τ .
Cas particulier des systèmes avec b[x]bi-sources
Il a été démontré qu’une [t + 1]bi-source suffisait à résoudre le problème du consensus. Et en effet cela correspond à un cas particulier du théorème 4.1 démontré dans la partie précédente. La question que l’on peut alors légitimement se poser est de savoir si le problème du consensus byzantin avec signatures peut être résolu en l’absence de [t + 1]bi-sources. Par exemple est-ce qu’une [t]bisource suffit ? Est-ce que si tous les processus corrects sont des [t]bi-sources, le problème possède une solution ?
Nous étudierons dans cette sous-partie les propriétés de synchronie de la forme « le système possède un nombre b de [x]bi-sources », et nous montrerons qu’en considérons uniquement cette classe de propriétés, la présence d’une [t + 1]bisource est nécessaire et suffisante pour résoudre le problème du consensus. Nous montrerons en particulier le théorème suivant.
Synchronie et relation d’équivalence
Dans cette partie nous allons montrer que l’on peut transformer un système quelconque en un système dans lequel la relation entre processus corrects « être synchrone » est une relation d’équivalence. On rappelle que l’on considère que pour tout couple de processus (p, q) si le lien p → q est synchrone, alors le lien q → p l’est aussi.
Définition 4.5 On dit qu’un système est δ-synchrone si ∀p, q, si le lien entre p et q est synchrone, alors tout message envoyé par p à la date t sera reçu par q à la date t + δ.
À chaque fois qu’un processus reçoit un message pour la première fois, il le fait suivre à tout le monde. On démontre aisément que le fait de faire suivre les messages permet de transformer un système δ-synchrone en un système Δ- synchrone avec Δ = (n−t)δ dans lequel la relation être synchrone est transitive entre processus correct.
Possibilité du consensus si n − t < kx et b > (k − 1)t
On suppose que la relation être synchrone est transitive entre processus corrects (si ce n’est pas la cas il suffit d’appliquer la transformation décrite dans la partie 4.3.4). Ainsi si on considère l’ensemble Πc des processus corrects, alors on peut partitionner Πc avec la relation d’équivalence « être synchrone ». On appelle clusters les sous-ensembles correspondant à la partition, et on note Cp le cluster qui contient p. Ainsi si p est une [x]bi-source mais pas une [x + 1]bisource, p appartient forcément à un cluster Cp de taille x qui est asynchrone avec le reste du système.
On considère alors l’ensemble des clusters Cb contenant les [x]bi-sources, c’est-à-dire l’ensemble des clusters de taille supérieur à x. On constate tout d’abord que quelque soit la valeur de b, nous n’avons pas suffisamment de bisources pour les répartir dans k clusters de taille supérieure à x (car le nombre total de processus corrects, n − t, est strictement inférieur à kx) et donc en notant |Cb| le cardinal de Cb, on a |Cb| ≤ (k−1). Enfin comme il y a strictement plus de (k−1)t bi-sources et qu’il y a moins de (k−1) clusters distincts, un des clusters est constitué de strictement plus de t processus, et donc possède une [t + 1]bi-source.
Étant donné que l’on sait résoudre le consensus byzantin en présence de [t + 1]bi-sources, on sait alors le résoudre pour n − t < kx et b > (k − 1)t.
Hypothèses minimales de synchronie pour le consensus byzantin sans signatures
Nous allons dans cette partie commencer le même travail que celui fait dans la partie précédente. C’est-à-dire que nous définirons une certaine classe de graphes, les graphes (t, S)bi-ambigus, qui permettent de montrer que le consensus ne possède pas de solution avec les hypothèses S et un nombre t de processus fautifs. Contrairement à la partie précédente, nous ne montrerons pas que l’absence de tels graphes est suffisante pour résoudre le consensus.
Une variante de FLP
Nous allons dans cette partie montrer que l’existence d’un graphe (t, S)biambigu permet de montrer que le consensus ne possède pas de solution avec les hypothèses S et un nombre t de processus fautifs.
Le résultat étant relativement proche de celui de la partie précédente, la démonstration sera « relativement » semblable (bien que cela ne soit pas visible a priori). Plus précisément, la première démonstration consistait à se ramener à FLP, mais en ce qui concerne la seconde démonstration décrite ci-après, le résultat ne correspondant pas tout à fait, la preuve consiste en une modification légère de FLP.
Pour plus de détail sur la démonstration le lecteur est invité à lire initialement la démonstration de Fisher, Linch et Paterson [6] qui est sensiblement la même mais en légèrement plus simple (en particulier seule la démonstration du lemme 5.2 est changée).
Démonstration
Le principe de la démonstration est relativement simple et repose sur cette notion de valence. On suppose qu’il existe un protocole A qui résout le consensus binaire (qui est un cas particulier de consensus). On montre tout d’abord qu’il existe un état bi-valent, puis par récurrence on construit une exécution infinie ne comportant que des états bi-valents et cette exécution ne décide donc jamais. Le protocole A ne vérifiant pas alors la propriété de terminaison, cela nous permet de conclure qu’un tel protocole ne peut pas exister.
Lemme 5.1 Il existe un état initial bi-valent
Démonstration : Supposons que cela ne soit pas le cas. On considère le tableau T = [v0, . . . , vn] des valeurs proposées. La valence de l’état initial dépendant uniquement de T, on associe donc à chaque état initial le tableau correspondant.
On sait de plus qu’il existe une configuration initiale 0-valente (si tous les processus corrects proposent 0) et une configuration 1-valente (idem). On dit que deux configurations initiales sont adjacentes si les tableaux correspondants ne diffèrent que d’une valeur.
Il est aisé de constater que deux états initiaux peuvent être reliés par une chaîne d’états initiaux adjacent deux à deux. Ainsi en considérant une chaîne qui va de l’état 0-valent à l’état 1-valent, il existe deux états adjacents dont l’un est 0-valent et l’autre est 1-valent. On note alors p le processus à l’origine de la valeur qui diffère entre les deux processus.
Si p crash avant même le début de l’exécution, les processus ne peuvent faire la différence entre l’exécution partant de l’état initial 0-valent, et celle partant de l’état 1-valent, et donc les processus corrects autre que p décident la même valeur dans les deux cas, ce qui est absurde.
Conclusion
Le but de ce stage était avant tout d’améliorer et de compléter le résultat d’Ashour Mostefaoui, de Moumen Hamouma et de Gilles Trédan qui affirmait qu’une ⋄[t+1]bi-source était suffisante pour résoudre le problème du consensus. Nous avons pour cela tout d’abord amélioré le protocole de consensus proposé afin qu’il puisse avoir des performances correctes (en particulier qu’il termine rapidement dans le meilleur des cas) et donc qu’il soit utilisable en pratique.
Il serait intéressant par la suite d’implémenter ce protocole afin de comparer les performances de ce dernier avec d’autres protocoles de consensus nécessitant des hypothèses plus fortes sur les liens synchrones.
Nous avons ensuite exhibé une condition nécessaire et suffisante sur les liens synchrones pour résoudre le problème du consensus byzantin avec signatures.
La notion de graphe ambigu et la nouvelle définition de bi-source (qui ne prend plus en compte les liens avec les processus byzantins) ont permis de répondre à une question qui était posée depuis bientôt trois ans. Cependant, si nous avons montré que, dans le cas des hypothèses de la forme « il y a b [x]bi-sources dans le système », la présence d’une [t+1]bi-source était nécessaire et suffisante, il serait intéressant soit de démontrer ce résultat dans le cas général, soit de trouver un graphe ambigu dans lequel il n’y a pas de [t + 1]bi-source. Enfin, nous avons commencé à étudier le problème du consensus byzantin dans un système sans signatures. Alors que nous savions déjà qu’une [2t+1]bisource était suffisante, nous avons montré que la présence d’une [2t]bi-source ne
l’était pas, ce qui à notre connaissance n’avait jamais été démontré auparavant. Pour cela nous avons introduit la notion de graphe bi-ambigu. Si l’existence d’un graphe bi-ambigu implique l’impossibilité de résoudre le problème du consensus byzantin sans signatures, il reste à montrer que l’absence d’un tel graphe suffit à résoudre le consensus.
Nous avons utilisé un modèle dans lequel les liens pouvaient être soit asynchrones, soit synchrones dans les deux sens (c’est-à-dire que si le lien p → q est synchrone alors le lien q → p l’est aussi). Cependant, il existe dans la littérature d’autres modèles plus fins, que ce soit les liens partiellement synchrones ou les IO-processus. Bien évidemment, les résultats d’impossibilités s’appliquent malgré tous dans ces modèles, car ces derniers généralisent le nôtre (que nous avons appelé « propriété de synchronie »), par contre, il serait intéressant de regarder si l’absence de graphe ambigu suffit à résoudre le problème du consensus avec ces nouvelles hypothèses de synchronie.
|
Table des matières
Introduction
1 État de l’art
2 Modèles et définitions
2.1 Modèle de système
2.2 Modèle de fautes
2.3 Synchronie
2.4 Oracles et détection de fautes
2.4.1 Synchronie et détection de fautes
2.4.2 Oracles
2.5 Le problème du consensus
2.5.1 Définition classique
2.5.2 Variantes byzantines et remarques
3 Étude d’un protocole de consensus byzantin avec signatures
3.1 Le protocole
3.1.1 Principes généraux
3.1.2 Signatures et authentification des messages
3.1.3 Déroulement du protocole
3.2 Terminaison rapide dans le meilleur des cas
3.2.1 Terminaison rapide pour n>3t
3.2.2 Terminaison rapide pour n>5t
4 Hypothèses minimales de synchronie pour le consensus byzantin avec signatures
4.1 Définitions
4.2 Une généralisation de FLP
4.3 Cas particulier des systèmes avec b[x]bi-sources
4.3.1 Existence d’une solution pour x > t
4.3.2 Impossibilité du consensus avec b ≤ (k − 1)t et x ≤ t
4.3.3 Impossibilité du consensus si n − t ≥ kx et b > (k − 1)t
4.3.4 Synchronie et relation d’équivalence
4.3.5 Possibilité du consensus si n − t < kx et b > (k − 1)t
5 Hypothèses minimales de synchronie pour le consensus byzantin sans signatures
5.1 Définitions
5.2 Une variante de FLP
5.2.1 Définitions
5.2.2 Démonstration
5.3 Cas particulier des systèmes avec b[x]bi-sources
5.3.1 Impossibilité du consensus pour n ≥ 4x et b ≤ (k − 1)2t
5.3.2 Impossibilité du consensus pour n ≥ 4x, b > (k − 1)2t et n − t ≥ k · 2x
Conclusion
Références
Télécharger le rapport complet
