David Madore's WebLog: Le théorème d'insynchronisabilité

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #0772 [older|newer] / Entrée #0772 [précédente|suivante]:

(lundi)

Le théorème d'insynchronisabilité

Voici un petit résultat mathématique (je suppose qu'on devrait dire que ce n'est ni des mathématiques, ni de l'informatique, mais de la cybernétique) qui est totalement évident, mais qui me plaît beaucoup. C'est le théorème que j'appelle d'insynchronisabilité. De façon approximative (car il est plus difficile à formaliser qu'à démontrer) il stipule qu'il est impossible d'établir une communication fiable face à un canal qui peut être rompu (fiable au sens que si la communication n'est pas passée, les deux parties en communication sont d'accord sur ce fait — on ne va évidemment pas demander que des données puissent être transmises à coup sûr alors que le canal peut être rompu !). Imaginez par exemple un téléphone qui permettrait d'envoyer un SMS et qui préciserait soit SMS envoyé soit SMS non envoyé (échec) de sorte que le premier est affiché lorsque le central a bien reçu le message, et le second lorsque le central ne l'a pas reçu : cela n'est tout simplement pas possible (sauf trivialement en n'essayant jamais d'envoyer le SMS et en indiquant toujours un échec).

Le formalisme précis est le suivant : les deux agents possèdent chacun un état (pris dans un certain ensemble fini, disons) et possèdent un programme qui, en fonction de leur état antérieur et des messages reçus (ainsi que de l'initiation et de la terminaison du temps, qui est discret), leur permet d'envoyer des messages sur le canal et de changer d'état. Le canal est sans erreurs (si un message est reçu, c'est bien ce message-là qui a été envoyé par l'autre agent) mais avec pertes possibles (éventuellement limitées à la coupure subite du canal), et le canal ne donne pas de preuve de bonne réception du message de l'autre côté (sans quoi le problème serait trivialement résolu). Le but est d'arriver, en partant d'un état donné commun aux deux agents, d'établir un protocole (donc un programme pour chacun des agents) qui permet de se synchroniser sur un état commun, qui, si toutes les communications passent (resp. aucune communication ne passe) doit être différent de l'état initial (resp. identique à celui-ci), et qui doit être commun aux deux agents.

Une fois convenu le formalisme, la démonstration de l'affirmation est tout à fait évidente : il suffit de considérer, pour les deux agents et pour tout message reçu, quel sera l'état final de l'agent si ce message-là est le dernier message reçu : appelons-ça l'état asymptotique associé à cette réception de message. Par hypothèse de non trivialité, en présence de bonne communication, un certain message reçu provoque un changement de l'état asymptotique de l'agent qui le reçoit. Par hypothèse de synchronisation, l'agent qui a envoyé ce message devait avoir le même état asymptotique au moment de l'envoi. Par conséquent, si on supprime ce message (et tous les messages qui suivent), l'agent émetteur passe asymptotiquement dans l'état en question, alors que l'autre agent a un état asymptotiquement différent puisque justement il ne reçoit pas le message.

En clair, cette démonstration ne fait que rendre rigoureuse l'idée de l'accumulation des accusés de réception : si l'émetteur envoie un message, le récepteur devrait l'accuser pour s'assurer que l'émetteur ne va pas penser à tort (si on compare à un système sans accusés de réception) que le message a bien été reçu, et cet accusé de réception devrait lui-même faire l'objet d'un accusé de réception, et ainsi de suite, et le changement d'état ne serait possible que si une infinité d'accusés de réception arrivent bien.

Évidemment, le théorème d'insynchronisabilité cesse de s'appliquer si on permet aux agents de finir dans un état je ne sais pas si la communication a bien fonctionné, entendu que cet état ne doit pas être atteint en cas de communication parfaite (ou d'incommunication parfaite). Reste que c'est un résultat qui fait peur si on l'applique, par exemple, à un automate distributeur d'argent : si la rupture de communication entre lui et la banque (qui tient le compte de celui qui retire l'argent) est possible (ne serait-ce que parce que l'automate peut subitement tomber en pane complète, griller totalement, ou que sais-je encore) alors il y a nécessairement un scénario dans lequel soit on se retrouve avec des billets non débités sur le compte (et on peut se douter que les banques rendent ça impossible) soit on se retrouve avec un débit mais sans billets (et c'est ça qui fait peur).

Dans le même esprit, je devrais mentionner le théorème de Horvai, qui affirme que si, dans un programme ou système informatique quelconque, deux variables (deux informations quelconques) sont censées être maintenues synchronisées (donc elles sont redondantes), il y aura forcément un scénario qui les désynchronisera. Il s'agit là d'une loi empirique (le terme théorème est abusif) mais admirablement vérifiée dans la pratique.

Mise à jour () : On me signale deux articles (que je n'ai pas encore eu le temps de lire, j'ai seulement survolé les math reviews) ayant rapport avec ce théorème :

  • Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, Impossibility of distributed consensus with one faulty process, J. Assoc. Comput. Mach. 32 (1985) nº2 374–382.
  • Maurice Herliy & Nir Shavit, The topological structure of asynchronous computability, J. Assoc. Comput. Mach. 46 (1999) nº6 858–923.

Je devrais aussi, dans le même ordre d'idées, me renseigner sur le problème dit des généraux byzantins.

↑Entry #0772 [older|newer] / ↑Entrée #0772 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées