Vous trouverez dans ce billet des précisions sur des sujets importants passés sous silence ou éludés dans mes vidéos afin de les rendre plus compréhensibles. Nous allons parlé des ordinateurs malicieux, de la causalité entre messages et de quelques notions essentielles concernant le consensus.
Bonne lecture!
Ordinateurs incohérents ou « byzantins »
Toutes les vidéos de cette série prennent l’hypothèse que les systèmes distribués ne sont constitués que d’ordinateurs « sains », c’est à dire dont le comportement est cohérent et honnête.
Or, dans le monde réel des grands réseaux distribués, il n’est par rare d’être confrontés à des serveurs malicieux. Il en existe deux sortes : ceux qui, du fait de défauts de programmation, émettent de façon aléatoire des messages incohérents et imprévisibles, et ceux qui, contaminés par des virus, émettent des messages volontairement malveillants.
Dans les deux cas, le comportement de ces serveurs déstabilisent le fonctionnement du système puisqu’ils transgressent les principes de fonctionnement de l’informatique distribuée. Ils peuvent, par exemple, broadcaster ou retransmettre des messages modifiés ou déclarer des pannes fictives et j’en passe.
Du fait de leur caractère aléatoire ou malveillant, la prise en compte de ces machines incohérentes n’est pas simple :
– Dans le cas de la fiabilité de la diffusion des informations, la solution consiste simplement à augmenter le « quorum » de la moitié au deux tiers des machines. Cela alourdit la procédure, mais ne remet pas en cause la méthode.
– Par contre, dans le cas de la détection de pannes, la solution n’est pas aussi simple. Si le serveur P1 déclare la panne du serveur P0, comment savoir si P0 est vraiment en panne ou si P1 est malveillant ? Comment savoir donc s’il faut « sortir » P0 ou P1 ?« Causal Broadcast »
« Causal Broadcast »
Toutes les vidéos de cette série font également l’hypothèse que les messages échangés par les serveurs sont indépendants de sorte que leur contenu à minima prévu par le protocole TCP/IP (adresse IP de l’émetteur, numéro du message et corps du message) est suffisant.
Mais dans le cas assez fréquent de messages présentant une relation de dépendance, cela ne l’est plus.
Pour illustrer cette notion, prenons l’exemple d’un message M1 émis par l’ordinateur P1 signalant la mise en ligne d’un post par pHdS sur Facebook et d’un message M2 émis par P2 signalant la mise en ligne d’un commentaire sur le post en question.
Le timing d’arrivée des messages à l’ordinateur P3 étant incertain, il est important que celui-ci ait l’information sur la dépendance entre les 2 messages sans quoi, il ne saura pas les traiter correctement.
Pour faire circuler cette information de causalité, il faut ajouter du contenu à notre message M2 ce qui peut se faire de deux façons : soit on inclut dans M2 le contenu de tous les messages reçus par P2 avant son émission soit on y inclut seulement un vecteur indiquant le nombre de messages reçus par P2 de la part de chaque autre serveur.
Dans un cas comme dans l’autre, P3 pourra reconstruire l’ordre chronologique avant de délivrer les informations à ses clients.
Cette question, dite de causalité, est essentielle dans de très nombreuses applications et si, comme nous venons de le voir, sa résolution théorique est relativement simple, sa mise en œuvre se révèle en pratique complexe de sorte qu’elle fait, aujourd’hui encore l’objet de nombreuses recherches et publication.
Consensus
En informatique distribuée, on appelle « consensus » une abstraction qui permet aux ordinateurs de se mettre d’accord sur l’ordre des opérations à exécuter. Cette abstraction contient deux fonctions : une fonction « propose » qui permet à chaque ordinateur du système de proposer des valeurs ( des instruction à exécuter) et une fonction « return » qui en retour choisit une de ces propositions et l’impose à tous les ordinateurs.
Elle obéit aux principes suivants :
– la valeur retournée est toujours la même pour tout le monde
– la valeur retournée est toujours une valeur proposée
– le consensus se termine toujours, c’est à dire qu’il retourne toujours une valeur
Sur un plan théorique, cette abstraction est simple à comprendre mais sa mise en œuvre pratique est très complexe. Il a d’ailleurs été démontré qu’elle est en fait impossible dans un environnement totalement asynchrone dans lequel les ordinateurs peuvent tomber en panne. Il est donc nécessaire de trouver des solutions qui « trichent un peu » avec l’asynchronisme général en prenant des hypothèses de synchronisme partiel.
Par exemple, dans le cas du « group membership » on peut par exemple – l’implanter sur un ordinateur spécifique, plus ou moins indépendant du reste du réseau… en espérant qu’il ne tombe jamais en panne. – ou partager la fonction entre tout ou partie des ordinateurs du réseau… avec la lourdeur d’échange massif de messages qui l’accompagne. – ou encore tout autre solution rendue possible par les spécificités du réseau sur lequel on souhaite l’implémenter.