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
.