Ces transactions qu'on distribue

Un problème insoluble peut il avoir une solution simple? 

Le parangon de l'informatique distribuée, voire son aporie, est la transaction distribuée: on veut modifier deux entités indépendantes de manière coordonnée et faire en sorte que les deux modifications aient lieu ou aucune, une modification à un site sans que l'autre ne le soit détruisant un principe global de manière inacceptable. Une telle chose peut elle être programmée de manière à considérer tous les cas d'erreurs, chacun d'entre eux pouvant se manifester ? Et bien NON.

Considérons Alice et Bernard, les deux entités à modifier. L'exemple est bien sur celui de deux comptes bancaires dont l'un, celui d'Alice, doit être débité, celui de Bernard devant être crédité.  

Les pannes sont multiples, et concernent les coupures réseau et aussi les blocages des machines, différentes, qui supportent Alice et Bernard. Ces pannes peuvent être provisoires ou de longue durée. Bref, l'horreur.

On commencera par le demandeur, Denis, de la transaction. Il enverra donc un message à un "éxecuteur" (Emile) et le chargera de s'occuper de tout, suspectant une complexité qu'il ne peut pas assumer. Emile va donc procéder et retourner un peu plus tard un acquittement ou un aveu d'échec. 

Le premier problème est donc celui du "un peu plus tard". Peut on borner cette durée et si oui comment ? Emile peut exploser en vol (certains clouds montent en l'air) et ne jamais répondre. C'est le premier problème fondamental de l'informatique à distance: le correspondant distant peut ne pas exister ou pire détruire votre commande sans rien dire. Il vous faut donc, et cela au delà de tout problème de communication, vous assurer que le premier contrat qu'Emile est censé supporter, la prise en compte de la commande, est bien respecté. Denis arme donc un chronomètre pour 10 secondes (ou un mois) et attend. Si aucune réponse n'est reçue avant l'échéance, on passe à autre chose. La chose a échouée, c'est sur, ou bien Alice ou Bernard ou les deux sont détruits, ruinés ou pire. L'horreur. Mais au moins, on peut alors décider d'aller se plaindre. On peut décider. C'est ça le critère, et la durée fixée, convenue à l'avance avec Emile est la base rationnelle de cette décision. 

En tout cas, un acquittement reçu d'Emile après cette durée (positif ou négatif) devra être ignoré. Du moins en principe, on pourrait s'arranger dans ces cas, non ? On verra après, forget it for now. 

Emile va d'abord stocker les détails de la transaction et y procéder. Comment faire ? Le bon cas est celui il peut vérifier que tout c'est bien passé. Dans ce cas, il se contente de renvoyer l'acquittement "c'est fait". Naturellement, il arme lui aussi un chronomètre, et si le traitement dure trop longtemps, doit s'assurer que tout est remis dans l'ordre de son coté avant de renvoyer un "désolé, il y a eu un problème, recommencez" à Denis, ou pas, parce que Denis dans ce cas, est supposé considérer que rien n'a été fait.  

La simple gestion de cette petite délicatesse a ses problèmes fondamentaux et nous introduit au problème, au gras horrible de l'insolubilité complète du problème. Disons que si les "c'est fait" de Alice et Bernard sont finalement collectés trop tard (au delà d'un certain temps, qui rend certain que Denis s'est impatienté et considère la transaction en échec), Emile doit faire face à un cas troublant: il a fait ce qu'on lui demandait, mais trop tard. Que va faire Denis ? Que doit faire Emile?  Deux cas: Emile s'estime content tout de même et ne dit rien et attend. Denis de son coté, ne voyant rien venir, recommence sa demande, en termes identiques. Il a cru que Emile avait échoué.  

Cette fois Emile, Alice et Bernard, en forme, performent tels des bêtes. La transaction est faite deux fois, Alice deux fois plus pauvre, et Bernard deux fois plus riche que prévu. Il ne faut pas faire ça: Denis ne doit pas recommencer, sauf à dire à Emile: "ne fait ça que si tu ne l'a pas déjà fait". Cette commande modalisée s'exprime par le header HTTP "IfNoneMatch" accompagné d'une valeur unique, tirée au hasard, et utilisée une autre fois dans le cas ou Denis tente de recommencer l'ordre si absence de réponse. Cette valeur identifie la commande et lui confère une existence au delà de son simple envoi. Un évènement a généré un objet stable dans le temps. 

Ce principe, central et simple doit et peut être utilisée systématiquement dans les protocoles applicatifs basés sur des échanges asynchrones soumis au temps. Le rejeu est systématiquement possible et permet de pallier les défaillances provisoires du réseau et les pertes de temps assumées par les systèmes distants. 

Il couvre des cas multiples, y compris l'échec total d'Emile détecté trop tard: Emile peut lui même recommencer et même une transaction incomplète. Imaginons Alice  en forme, répondant immédiatement et Bernard languissant, mettant Emile hors des clous. Denis, lassé, réitère sa demande avant qu'Emile ait abandonné. Emile peut alors réarmer ses horloges et tout en gardant le succès d'Alice au chaud, et recommencer Bernard... 

Car bien sur, Emile se comporte comme client pour Alice et Bernard. Il gère un objet global, la transaction composite et ses horloges. Tant qu'il a une transaction en cours, toute demande de rejeu ne lui fait que réarmer ses horloges, l'objectif étant de ne faire l'affaire globale qu'une fois. 

Emile pourrait il ainsi se la jouer "éternel" et rejouer telle la bête jusqu'à la fin du monde, comptant sur l'obstination de Denis pour se maintenir vivant ?  Cela ne se peut pas, il faut des limites, et Emile doit considérer l'échec, manifesté par un temps trop long passé sans réactivation de Denis, celui ci s'étant fixé un paramètre supplémentaire, un nombre de tentatives maximal. Emile doit alors abandonner, tout nettoyer et détruire le contexte de la demande de Denis. 

Cet échec doit être proprement nettoyé: Alice et Bernard ne doivent pas avoir été modifiés. Si avant que l'échec final ne soit décidé, Alice ou Bernard ont acquitté leur tâche, et bien un mécanisme de "défaisance" doit être appelé et Alice et Bernard remis dans leur état initial. 

Pour se faire, on peut supposer que Alice et Bernard  exposent bien un service d'annulation d'une commande ou bien la possibilité d'ajouter négativement. Dans ce cas, Emile peut s'assurer que les commandes en question ont bien été exécutées, quitte à les rejouer autant de fois que nécessaire. En cas d'échec à ce niveau, Alice par exemple ayant été détruit ou bien le réseau aussi, le système dans son ensemble est compromis et on doit se reporter à une procédure globale de récupération laissée en exercice à l'utilisateur, celle ci se devant tout de même d'être signalée nécessaire par une alarme. Ce cas doit être considéré, il n'est pas une erreur, mais un cas de destruction.

Il y a d'autre possible malheurs. 

Le cas de la destruction d'Emile par exemple: Alice peut avoir été laissée modifiée et pas Bernard. Rien ne pourra rattraper la chose et le système est fondamentalement fragile. Notons que si Emile était localisé "dans" Alice, pour plus d'efficacité et de fiabilité peut très bien modifier Bernard et se suicider pour produire une catastrophe équivalente.

La sécurisation du fameux "contexte" est donc à considérer. Notons qu'il est en la possession de Denis qui le crée littéralement. Il peut et doit en cas de non réponse l'envoyer à qui de droit afin de tenter de récupérer l'éventuel désastre.  Denis peut aussi être détruit lui même, ce qui garantit l'oubli de la chose... 

Bon, il faut donc dupliquer le contexte, et s'assurer de sa permanence avant toute chose. Un Emile bis doit être prévenu, armer lui même ses horloges, et attendre qu'Emile le prévienne pour détruire son contexte de sauvegarde; il doit se préparer à prendre la main et à intervenir, l'identifiant de commande lui permettant de rejouer auprès d'Alice et Bernard sans problèmes, la commande d'annulation devant accepter une modalité pour ne pas additionner négativement de manière excessive. 

On passera sur la sécurisation d'Emile bis, le cas des fautes "doubles" étant négligé, ou bien, la resécurisation d'Emile bis étant prévue, celui ci se devant de prendre la main en même temps qu'une activation de sa duplication à lui, opération elle même soumise aux erreurs signalées. 

Y a t il régression à l'infini et impossibilité de se garantir ? C'est ce qu'un théorème fameux prétend, il s'agit du théorème FLP : Fisher, Lynch, Patterson (1985) : "Il n'y a pas de consensus possible avec un processus en erreur".  https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

L'ai je démontré ?

Presque, car la preuve de FLP est bien basée sur une régression à l'infini, la sécurisation de la sécurisation n'étant pas dialectique.  En fait c'est bien sur plus compliqué que ça. On y va ? 

0) On modélise: il y a des agents qui peuvent être détruits, des messages qui s'échangent suivant des protocoles. Une configuration c'est un état global qui évolue suivant un protocole avec des messages dans des ordres variés et des agents qui disparaissent. "un" protocole: on va montrer que tous, absolument tous, même les plus astucieux, les plus hackés à mort, sont faux. Prenons en un au hasard. 

1) Il y a des configuration 'bivalentes', dont on ne peut savoir ce qu'elles vont décider du fait du protocole. 

2) Depuis une configuration bivalente, on peut toujours aboutir à une autre, tout aussi bivalente. (Ca pour le montrer, macache(1), je ne vous embêterais pas avec ça).

Donc, l'application du protocole peut indéfiniment passer d'une configuration non décidée à une autre... 

Une configuration bivalente semble mystérieuse. Elle se construit par une sorte de "triangulation".

Elle consiste donc en une configuration dont le résultat au bout d'un certain nombre de pas de protocole n'est pas fixé à l'avance mais dépend des évènement intermédiaires. Une telle chose existe ! En effet, supposons la valeur à décider étant 0 ou 1 et que TOUTES les configurations possible soient déterminées par leurs valeurs initiales. Toute configuration a de plus une valeur finale 0 ou 1. C'est ce qu'on suppose. 

On va les ranger l'une après l'autre, bernard après alice suivant que l'un des agents porte une valeur initiale différente dans les deux configurations. Si cet agent est détruit tout de suite, sa valeur ne peut être acquise et donc alice et bernard dans ce cas doivent avoir la même conclusion, car ils disposent de la même information, la seule chose qui les différenciait étant précisément la valeur portée par le fugace agent. 

Il existe deux configurations de valeur finales opposées qui sont rangées successivement dans l'ordre décrit. En effet, prenons deux configurations de résultats opposés et considérons les valeurs de leur agents initiaux qui sont des chaines de bits à 1 et 0 que l'on peut transformer un à un. Une chaine de valeurs initiales différente uniquement pour un seul agent les relie. Il y a donc forcément un de ces couples de "vecteurs" initiaux qui conduiront à des valeurs finales différentes. 

Cela n'est pas possible, car sinon, comme indiqué, la destruction immédiate de cet agent conduirait à des valeurs finales égales, ce qui est contradictoire... Il existe donc toujours des configurations dont la valeur finale dépend de l'état du monde changeant pendant l'exécution du protocole. Subtil et profond.

Comment prouver que mes arguties du début sont équivalentes à cet argument là ? 

 

(1) macache de l'arabe dialectal maghrébin makanch "rien"