Bref – consensus réparti

Ce qui suit décrit très brièvement des questions propres au consensus dans les systèmes répartis. Le consensus est un problème très large, qui touche à la coordination des processus concurrents, à la question de l'action concertée, de la prise de décision et même à celle du temps. Toutes ces considérations délimitent ce qui peut être dit ou connu d'un système réparti par l'un de ses éléments constitutifs.

Tous ces sujets sont profonds, et ne sont que survolés par la présente. N'hésitez pas à pousser plus loin votre étude.

Horloges réparties

Bien que Leslie Lamport ait contribué à délimiter nos espoirs quant à l'idée d'un temps commun dans un système réparti, avec son texte Time, Clocks, and the Ordering of Events in a Distributed System, les mécanismes de synchronisation d'horloges entre plusieurs ordinateurs existent en pratique (dans les limites de ce qui leur est possible de faire) et permettent aux humains, à leur échelle, de rester à peu près synchronisés pour l'essentiel de leurs tâches courantes.

Deux grands modèles de synchronisation d'horloges réparties sont possibles. Le premier est ce qu'on nomme la synchronisation externe, et consiste en ceci :

• l'idée est de garder les horloges internes de divers ordinateurs « en accord » avec un temps commun partagé, tel que défini par une autorité (aujourd'hui, on parle généralement d'un Time Server dans Internet)
• les divers ordinateurs reçoivent périodiquement un signal d'une telle autorité
• l'autorité calcule le délai entre l'envoi d'un signal donné et le retour d'une confirmation de réception
• l'autorité estime le délai de transfert, généralement sur la base d'une dizaine d'allers/retours, ce qui permet de réduire l'impact de bruit sur la ligne
• l'autorité envoie ensuite un temps au client. Ce temps tient compte des délais de transport estimés par l'autorité (environ la moitié du temps d'aller/ retour estimé, en pratique). Ceci n'élimine pas l'erreur mais tend à la garder à l'intérieur d'un intervalle « décent »

Cette approche suffit pour qu'un ordinateur donné tende à ne pas trop s'éloigner du temps physique de l'autorité, qu'on estime précis. C'est habituellement tout à fait convenable à l'échelle humaine. Pour plus de détails, voir le protocole NNTP.

Le second est ce qu'on qualifie de synchronisation interne :

• on cherche alors à en arriver à un accord sur un ordonnancement du temps commun à plusieurs processus ou à plusieurs threads sur un même ordinateur
• il existe une horloge physique commune, soit celle de l'ordinateur que partagent ces processus et ces threads
• cette horloge physique dérive en pratique si on la compare avec le temps physique connu des autorités, au sens entendu pour la synchronisation externe (plus haut)
• le problème en devient un d'ordonnancement des événements entre les processus et les threads participants

Horloges vectorielles (Vector Clocks)

Si l'on résume le problème que nous a exposé Lamport, il n'est pas correct pour un processus de présumer que constater l'événement $e$ avant l'événement $e^{\prime}$ signifie que $e$ a précédé $e^{\prime}$ sur le plan systémique. Les horloges vectorielles permettent de compenser cette situation en propageant la perception qu'ont les divers processus de l'ordonnancement des événements.

L'approche va comme suit :

• supposons un vecteur $V$ dans chaque processus. Ce vecteur comprend un élément par processus impliqué. On représentera l'état du processus $P_i$ tel que connu par le processus $P_j$ sous la forme $V_j[i]$ , mais on omettra l'indice sur $V$ indiquant le processus qui en est propriétaire lorsque cela s'y prête dans le but d'alléger l'écriture
• l'état $V[i]$ représente le nombre d'événements estampillés par le processus $P_i$
• initialement, $\forall i : V[i]=0$
• tout juste avant d'estampiller l'occurrence d'un événement, $V_i[i] \leftarrow V_i[i]+1$
• dans chaque message qu'il envoie, $P_i$ inclut $t=V_i$ (oui, on parle du vecteur entier)
• chaque fois que $P_i$ reçoit un message contenant un vecteur de temps $t$ , $P_i$ fait $\forall j : V_i[j] \leftarrow max(V_i[j],t[j])$

Ceci donne à $P_i$ une perspective sur l'évolution du temps pour les autres processus du système, mais exige un système « fermé », au sens où le nombre maximal de participants est connu a priori, et ajoute une surcharge à chaque message. Pour plus de détails, voir http://en.wikipedia.org/wiki/Vector_clock

États globaux

Existe-t-il des états globaux reconnaissables comme tels dans un système réparti? Supposons la ligne du temps (hypothétique) suivante :

$P_0$ ------ $e_0$ ----- $e_1$ ----- $e_2$ --------- $e_3$ ---->

$P_1$ ------------------ $e_0$ ---- $e_1$ ---- $e_2$ ------->

Imaginons qu'un message $m_0$ aille de $P_0:e_1$ à $P_1:e_0$ . Imaginons aussi qu'un message $m_1$ aille de $P_1:e_2$ à $P_0:e_3$ .

Il est parfois possible d'insérer des coupures dans un tel système. Une coupure sépare le « temps » perçu par les deux en un « avant » et un « après » communs. Dans une coupure, on s'intéresse au «avant ».

Une coupure est conséquente (les anglophones parlent de Consistent Cut) si elle préserve la causalité du système. Ici, couper après $P_1:e_2$ et avant $P_0:e_3$ est conséquent.

À l'inverse, une coupure n'est pas conséquente (Inconsistent Cut) si elle ne préserve pas la causalité du système. Ici, couper entre $P_0:e_0$ et $P_0:e_1$ de même qu'entre $P_1:e_0$ et $P_1:e_1$ ne serait pas conséquent.

L'histoire d'un processus est une séquence d'événements. On considère ici l'envoi et la réception de messages comme étant des événements. Ainsi, une coupure est conséquente si tous les événements y sont précédés de ceux qui les ont logiquement précédés au sens de la relation Happens Before : si un événement $e$ s'est produit avant $e^{\prime}$ et si $e^{\prime}$ est dans une coupure, alors $e$ y est aussi.

Un état systémique global conséquent correspond à une coupure conséquente. Il est à noter qu'un état global conséquent n'a peut-être jamais existé en pratique, mais il s'agit tout de même d'un état possible, sans contradiction avec aucune des histoires du système.

Une exécution d'un système peut être caractérisée par une séquence d'états systémiques globaux conséquents (il n'est toutefois pas nécessaire de déterminer une telle séquence pour que le système demeure conséquent). L'histoire globale d'un système est l'union ensembliste des histoires de tous les processus qui y participent. Une exécution d'un système est un ordonnancement total des événements de l'histoire globale, dans la mesure où cet ordonnancement demeure conséquent avec les histoires locales de chaque processus participant au système.

Une linéarisation d'un système est une exécution de ce système décrivant une suite de transitions entre des états globaux conséquents de ce système.

Un état global $S^{\prime}$ est atteignable d'un autre état global $S$ s'il existe une linéarisation passant de $S$ à $S^{\prime}$ . Il peut toutefois exister plusieurs linéarisations possibles pour une même histoire (on n'a qu'à penser aux événements concurrents).

Sachant cela, il est possible de définir des prédicats sur les états globaux d'un système. Un tel prédicat est stable si, une fois qu'il s'avère, nous savons qu'il demeurera vrai. Quelques exemples de prédicats systémiques stables :

• le système se trouve en Deadlock
• l'exécution du système est terminée
• un objet n'est plus atteignable par quelque autre objet que ce soit et peut être réclamé par un moteur de collecte d'ordures

Plusieurs prédicats systémiques ne sont pas stables, évidemment.

Consensus réparti

La question du consensus dans un système réparti est un problème important. Pris dans son acception générale, on parle de consensus quand plusieurs processus doivent s'entendre sur une même position face à un problème donné. Ce problème peut être de décider d'une action à prendre, par exemple, ou de déterminer l'ordre dans lequel les actions seront prises.

Pour qu'on puisse considérer un algorithme comme résolvant le problème du consensus, certains critères doivent être rencontrés :

• le critère de terminaison : il faut que tous les participants en viennent à prendre une décision
• le critère d'accord : il faut que la décision de tous les processus corrects soit identique (il existe des variantes se limitant à exiger un vote majoritaire et la reconnaissance de ce constat)
• le critère d'intégrité : si les processus corrects proposent tous la même valeur, c'est qu'ils l'ont choisie

Une erreur byzantine est une erreur d'apparence arbitraire se produisant dans un système réparti. Ceci inclut les omissions (plantage, message non envoyé, message non reçu) et ce que les anglophones nomment les commissions (corruption, message incohérent, traitement incorrect). On rencontre des erreurs byzantines partout, mais il s'agit d'un problème récurrent et particulièrement pernicieux dans les systèmes répartis ou complexes.

Généraux byzantins

Un cas particulier et bien étudié du problème du consensus est celui des généraux byzantins. Ce problème se présente comme suit :

• trois généraux (ou plus) se questionnent à savoir s'ils doivent attaquer ou battre en retraite
• l'un d'eux, le commandant, donne un ordre aux deux autres
• les autres, les lieutenants, doivent décider si leur escadre attaque ou bat en retraite

Ce problème décrit bien le problème du consensus réparti lorsque surviennent des pannes ou lorsque des tiers hostiles participent au processus. En effet :

• l'un des généraux peut être un traître (ou être défectueux)
• un commandant traître dira à un lieutenant d'attaquer et à l'autre de battre en retraite
• un lieutenant traître dira à un pair sur deux que le général lui a dit d'attaquer, et à l'autre qu'il lui a dit de battre en retraite

La tolérance aux pannes byzantines est atteignable dans la mesure où les généraux loyaux (non-défectueux) sont unanimement d'accord sur une stratégie. Si le général donnant l'ordre à l'origine est correct (non-défectueux), tous les généraux loyaux doivent être en accord avec sa décision; si le général donnant l'ordre est défectueux, le choix de stratégie des lieutenants n'a pas d'importance.

Il est donc possible de réduire le problème à celui d'un cas où le commandant est un traître, puisque si le commandant envoie ATTAQUE à l'un des lieutenants et RETRAITE à l'autre, puis les deux s'échangent le message du général, il est impossible à chacun de savoir si le message reçu vient d'un lieutenant malhonnête ou d'un général malhonnête.

Approche synchrone

Ce problème a-t-il une solution avec $n=3$ processus? A-t-elle une solution à $n>3$ processus? À quelles conditions?

En fait, ce problème est insoluble si $n \le 3f$ où $f$ et le nombre de traîtres. Il admet donc une solution avec $n=4;f=1$ . Quand il existe une solution, on l'obtient par vote majoritaire.

Ceci suppose plusieurs a priori :

• des canaux de communication fiables
• une pleine connectivité
• le récepteur de chaque message sait en tout temps qui a envoyé ce message (on peut s'aider avec des signatures cryptographiques pour empêcher les gens de se faire passer pour nous)
• tout récepteur peut détecter l'absence d'un message (pour éviter un joueur de tours – un snorro – qui refuserait de communiquer

Lamport a proposé une solution au problème des généraux. Sa technique est de supposer que le problème des généraux (Albanais, dans son acception) est soluble avec et d'utiliser cela pour construire une solution à $n=3;f=1$ qui est un cas particulier dont l'impossibilité a été démontrée.

En général, la solution de Lamport et cie est coûteuse, mais Miguel Castro et Barbara L iskov ont, en 1999, mis de l'avant dans le texte Practical Byzantine Fault Tolerance une solution pas trop chère (environ 3% de perte de performance au total). Cette solution fonctionne si $f \le \lfloor \frac{n-1}{3}\rfloor$ (avec $f$ pour nombre de processus défectueux – failures – et $n$ répliques, pour compenser les pannes) et est asynchrone.

Dans leur approche, $n=3f+1$ est le nombre minimal de répliques requis pour compenser $f$ pannes. Si $n>3f+1$ , leur approche fonctionne encore mais le système est moins performant et n'est pas plus résilient. Cette approche suppose que les processus sont des automates; elle réplique les automates, incluant les services, leurs états et leurs opérations.

Ces automates doivent être déterministes et tous débuter dans le même état. Un journal des messages est conservé sur chaque unité (chaque ordinateur) mais est tronqué lorsque cela semble sécuritaire. Chaque unité conserve périodiquement des Checkpoints instables. De plus, des Checkpoints stables (et prouvés comme tels; ceci permet de se défaire régulièrement des Checkpoints instables résiduels) périodiques sont générés sur chaque unité.

Dans leur approche, les messages sont signés mais asynchrones; ils évitent un résultat d'impossibilité bien connu si les messages qui ne se rendent pas à destination sont émis à nouveau, sans cesse.

Approche asynchrone

Dans un texte de 1985 nommé Impossibility of Distributed Consensus woth One Faulty Process, Michael J. Fischer et ses collègues Nancy A. Lynch et Michael Patterson ont démontré que si les échanges sont asynchrones, alors le problème du consensus n'a pas de solution avec $f \ge 1$ , $f$ étant le nombre de processus en panne ou défectueux). Dans leurs mots :

Leur approche suppose des canaux fiables (tous les messages sont livrés correctement et une seule fois), et ne suppose pas d'erreurs byzantines. Malgré tout, il s'agit d'un résultat d'impossibilité.

C'est une approche pleinement asynchrone : elle ne suppose rien quant à la vitesse de traitement des processus et sur le temps de livraison d'un message. Elle ne suppose pas non plus d'horloge synchronisée.

Ce qu'elle suppose toutefois est que l'arrêt (la mort) d'un processus est impossible à distinguer d'un traitement très long de la part de ce processus.

Chaque processus est supposé capable d'actions atomiques complexes, y compris une diffusion atomique de message à tous les participants (un Atomic Broadcast). Les processus sont supposés minimalistes, pour que la démonstration demeure simple (un bit en entrée, un bit en sortie, comportement déterministe). Les messages transmis sont de la forme ${dest,msg}$ . Les primitives de communication y sont $send(P,m)$ et $m \leftarrow recv(P)$ (le message $m$ peut être nul).

L'article définit une configuration pour un processus, puis une séquence admissible, puis une séquence décisive, et montre que s'il y a au moins une panne, il est possible de ne jamais atteindre de séquence décisive.