Ce rapport constitue une présentation de l'algorithme des Généraux Byzantins. Il se repose en grande partie sur l'article " The Byzantine Generals Problem " de Leslie LAMPORT, Robert SHOSTAK et Marshall PEASE [1]. Cet article a été publié en juillet 1982 dans la revue ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3. Nous ferons donc ici de nombreuses références à cet article.

Les systèmes informatiques fiables doivent être capables de gérer des composants défectueux qui donnent des informations conflictuelles aux différentes parties du système. Ces composants peuvent être soit des ordinateurs reliés entre eux par un réseau (c'est alors celui-ci que l'on considère comme système) ou bien des processeurs dont la redondance permet de garantir une certaine sécurité dans les systèmes critiques. La gestion de ces composants défectueux est aussi appelée gestion de pannes.

Le problème de composants défectueux dans un système informatique (ou ailleurs) peut être exprimé de façon abstraite en terme de généraux de l'armée Byzantine qui campent autour d'une cité ennemie. Ne communicant qu'à l'aide de messagers, ceux-ci doivent se mettre d'accord sur un plan de bataille commun, sinon la défaite est assurée. Mais il se peut que l'un ou plusieurs de ces généraux soient des traîtres, qui essayent de semer la confusion parmi les autres. Le problème est donc de trouver un algorithme pour s'assurer que les généraux loyaux arrivent tout de même a se mettre d'accord sur un plan de bataille.

Nous allons donc montrer que, en utilisant uniquement des messages oraux, ce problème peut être résolu, si, et seulement si plus des deux tiers des généraux sont loyaux ; ainsi un seul traître peut confondre deux généraux loyaux. Avec des messages écrits non modifiables, le problème peut être résolu pour nombre quelconque de traître. Tout au long de cette étude nous tenterons de voir les analogies avec les systèmes informatiques.

Imaginons que plusieurs divisions de l'armée Byzantine campent autour de la cité ennemie, chacune d'entre elle étant dirigée par son propre général. La seule façon de communiquer dont ils disposent est l'utilisation de messagers. Après avoir observer l'ennemi, ils doivent se mettre d'accord sur un plan d'action commun. Le problème est que certains de ces généraux peuvent être des traîtres, qui tentent d'empêcher les généraux loyaux de se mettre d'accord.

Les généraux doivent donc disposer d'un algorithme pour garantir que :

1. Tous les généraux loyaux se mettent d'accord sur le même plan d'action.

Les généraux loyaux feront tous ce que l'algorithme leur a dit de faire, mais les traîtres peuvent faire ce qu'ils veulent. L'algorithme doit donc garantir la condition A, et ce sans se préoccuper de ce que les traîtres choisissent de faire.

Les généraux loyaux ne doivent pas seulement trouver un accord, mais aussi trouver un plan raisonnable.

2. Un petit nombre de traître ne peut pas faire que les généraux loyaux choisissent un mauvais plan.

La condition B est difficile à formaliser étant donné qu'elle nécessite de définir ce qu'est un mauvais plan. Nous nous contenterons donc d'étudier la façon dont ils arrivent à se mettre d'accord.

Chaque général observe l'ennemi et communique ces observations aux autres. Soit v(i) l'information communiqué par le i^ème général. Chaque général doit donc utiliser une méthode pour combiner les valeurs v(1),..., v(n) en un plan d'action unique, avec n le nombre de généraux. La condition A peut être obtenue si tous les généraux utilisent la même méthode pour combiner les informations, et la condition B peut être obtenue en utilisant une méthode "robuste ". Par exemple, si la décision qui doit être prise est soit Attaque ou Retraite, alors v(i) peut être la décision du général i et la décision finale peut être basée sur la majorité des de ces décisions. Des traîtres peuvent modifier cette décision seulement si les généraux loyaux étaient divisés de manière égale quant à la décision à prendre, auquel cas aucune des décisions ne peut être considérée comme mauvaise.

Bien que cette approche puissent ne pas être la seule façon de satisfaire les conditions A et B, c'est la seule connue. Elle suppose qu'il existe une méthode qui permette aux généraux de communiquer leurs valeurs v(i) aux autres. Une méthode évidente est, pour le i^ème général, d ‘envoyer v(i) par messager aux autres généraux. Malheureusement, cela ne fonctionne pas car pour que la condition A soit satisfaite, il faut que tous les généraux obtiennent le même ensemble de messages v(1),..., v(n), et un traître peut très bien envoyer des messages différents à chacun des autres généraux. Pour que la condition A soit satisfaite, il faut que la condition suivante soit vraie :

1. Tous les généraux loyaux doivent obtenir les mêmes informations v(1),..., v(n).

Cette condition implique qu'un général loyal, ne va pas forcément utiliser la valeur v(i) reçue de i, puisque si le i^ème général est un traître, il a très bien pu envoyer des valeurs différentes à chacun. Cela signifie donc que, si l'on souhaite vérifier la condition 1 et qu'on ne fait pas attention, il est possible que les généraux utilisent une valeur de v(i) différente de celle envoyée par i – et ce même si le général i est loyal. Il ne faut pas permettre cela si nous souhaitons vérifier la condition B. Nous avons alors de plus la nécessité suivante :

2. Si le i^ème général est loyal, alors la valeur qu'il a envoyé doit être utilisée par tous les généraux loyaux comme étant v(i).

Nous pouvons alors réécrire la condition 1 comme ceci (que le i^ème général soit loyal ou pas) :

Les conditions 1' et 2 portent toutes deux sur une même valeur envoyée par le i^ème général. On peut alors restreindre notre étude du problème à : comment un seul des généraux envoie-t-il sa valeur aux autres ?

On formulera cela en terme de commandant qui envoie un ordre à ces lieutenants, ce qui nous amène au problème suivant.

Un Général commandant doit envoyer un ordre à ses n-1 lieutenants, de manière à ce que :

IC1 et IC2 sont connues comme les conditions de consistance interactive (Interactive Consistency conditions). Il faut remarquer que si le commandant est loyal, alors IC2 implique IC1. Mais bien sûr, le commandant peut très bien être un traître.

Ce problème, du point de vue informatique, peut être représenté de la façon suivante :

Soit un réseau de n processeurs qui peuvent communiquer les uns avec les autres seulement par le biais de messages, à travers des canaux de communications bidirectionnel, il faut s'assurer qu'un processeur envoie des données aux n-1 autres processus, de telle façon que :

IC1 : Les processeurs fiables reçoivent les mêmes données.

On voit bien que le problème de non-fiabilité que l'on cherche à résoudre peut alors provenir soit du processeur lui-même, soit de la liaison de donnée. Les deux cas n'ont donc pas à être différenciés. Si une liaison n'est pas fiable, alors le processeur sera considéré comme non fiable. Il faut de plus remarquer que dans le cadre de systèmes informatiques, il est plus probable que des données ne soient pas envoyées, plutôt que fausses.

Il s'agit donc plutôt d'erreurs par omissions, dues au crash d'un processeur par exemple.

Note : ici le mot processeur est employé dans sa définition globale, c'est à dire qu'il s'agit d'une entité effectuant un traitement sur des données, il peut très bien désigner un processeur, un processus, ou encore un ordinateur.

Considérons les deux cas suivants, avec 3 généraux :

Il est impossible pour le Lieutenant 1 de savoir qui est le traître, car dans les deux cas il reçoit les mêmes informations.

Dans le cas A, pour satisfaire IC1 le Lieutenant 1 doit attaquer.

Dans le cas B, si le Lieutenant 1 attaque, il viole IC2.

La preuve est en dehors du cadre de ce travail, mais les lecteurs intéressés pas celle ci peuvent se reporter à [1].

Observons maintenant des algorithmes permettant de résoudre ce problème. Dans la suite de ce document, n représentera le nombre total de généraux impliqués dans la communication, et m le nombre de traîtres parmi eux.

Il nous faut tout d'abord définir les suppositions suivantes sur les messages (les remarques entre parenthèses correspondent aux conséquences sur un système informatique) :

Les suppositions S1 et S2 permettent d'empêcher un traître d'interférer dans une communication entre deux autres généraux. S3 permet d'éviter qu'un traître ne sème la confusion en n'émettant pas de messages.

L'algorithme

Cet algorithme est appelé OM(m) (Oral Message), mais on le trouve aussi sous la forme UM(n, m) (Unsigned Message).

On suppose qu'une valeur par défaut vdef est définie pour le cas ou aucun message n'est envoyé par un traître.
On suppose aussi qu'une fonction majorité à été définie telle que : majorité(v₁, v₂,..., v_n-1) = v si la majorité des valeurs v_i = v.

Algorithme OM(0) #cas où il n'y a pas de traître

(1) Le commandant envoie v à chacun des n-1 lieutenants.
(2) Chaque lieutenant utilise la valeur reçue du commandant ou vdef si il n'a rien reçu.

Algorithme OM(m) #cas où il y a m traîtres

(1) Le commandant envoie v à chacun des n-1 lieutenants.

(2) Pour Chaque Lieutenant_i,
Soit v_i = valeur reçue du commandant ou vdef si aucune valeur n'a été reçue
Envoyer v_i aux n-2 lieutenants en utilisant OM(m-1)

(3) Pour chaque i & chaque j != i,
Soit v_j = valeur que Lieutenant_i a reçue du Lieutenant_j à l'étape (2) ou vdef si il n'a rien reçu.

Prenons le cas où n=4 et m=1 (OM(1)).

Premier cas : le Lieutenant 3 est un traître.

A la fin de l'étape (1) :

Lieutenant 1 : v₁ = v

Lieutenant 2 : v₂ = v

Lieutenant 3 : v₃ = v

A la fin de l'étape (3) :

Lieutenant 1 : v₁ = v, v₂ = v, v₃ = y

Lieutenant 2 : v₁ = v, v₂ = v, v₃ = x

Lieutenant 3 : v₁ = v, v₂ = v, v₃ = v

Note : il est possible que x = y, de même qu'il peut s'agir d'une absence de message.

A la fin de l'étape (3) chacun des lieutenants a reçu un ensemble de valeurs et arrive à la même décision (IC1) ;

La valeur envoyée par le commandant est bien la valeur majoritaire (IC2).

Le schéma suivant illustre bien les étapes (1) et (2) :

Second cas : le commandant est un traître.

A la fin de l'étape (1) :

Lieutenant 1 : v₁ = x

Lieutenant 2 : v₂ = y

Lieutenant 3 : v₃ = z

A la fin de l'étape (3) :

Lieutenant 1 : v₁ = x, v₂ = y, v₃ = z

Lieutenant 2 : v₁ = x, v₂ = y, v₃ = z

Lieutenant 3 : v₁ = x, v₂ = y, v₃ = z

A la fin de l'étape (3), les trois lieutenants loyaux ont reçu la même valeur majorité(x, y, z) et les contraintes IC1 et IC2 sont donc respectées.

Le schéma suivant illustre les étapes (1) et (2) :

Afin de prouver la validité de l'algorithme pour un m arbitraire, énonçons tout d'abord le lemme suivant :

Lemme

Pour tout m et k, l'algorithme OM(m) satisfait IC2 si il y a plus de 2k+m généraux et au plus k traîtres.

Preuve :

La preuve se fait par récurrence sur m. IC2 spécifie seulement ce qui doit se passer dans le cas où le commandant est loyal. Montrons que le lemme est vérifié pour m=0 :

De S1 il ressort que OM(0) fonctionne si le commandant est loyal, c'est à dire que OM(0) satisfait bien IC2.
Supposons maintenant que OM(m-1) satisfait IC1 pour m>0 et prouvons que c'est vrai pour m.
A l'étape (1), le commandant loyal envoie une valeur v aux n-1 lieutenants. A l'étape (2) chaque lieutenant loyal applique OM(m-1).
Par hypothèse nous avons : n>2k+1 ou n-1>2k+(m-1).
Par récurrence, chaque lieutenant loyal obtient v_j = v de chaque lieutenant loyal j.
Comme il y a au plus k traîtres et que n-1>2k+(m-1)>=2k c'est à dire que k<(n-1)/2, la majorité des n-1 lieutenants sont loyaux. Ainsi chaque lieutenant loyal a v_i = v comme majorité des n-1 valeurs pour i, il obtient majorité(v₁,...,v_n-1) = v à l'étape (3), ce qui vérifie IC2. []

Ce qui nous amène au théorème suivant :

Théorème

Pour tout m, l'algorithme OM(m) satisfait les conditions IC1 et IC2 si il y a plus de 3m généraux et au plus m traîtres.

Preuve :

Encore une fois la preuve se fait en raisonnant par récurrence sur m.

Si il n'y a pas de traîtres, il est alors facile de démontrer que OM(0) satisfait IC1 et IC2. Nous supposons alors que le théorème est vrai pour OM(m-1) et prouvons qu'il est vérifié pour OM(m), m>0.
Considérons tout d'abord le cas où le commandant est loyal. En prenant k = m dans le Lemme précédent, nous pouvons voir que OM(m) satisfait IC2. IC1 est impliqué par IC2 puisque le lieutenant est loyal, donc nous n'avons en fait qu'à considérer le cas où le commandant est un traître.
Il y a au plus m traîtres et le commandant est l'un d'entre eux, donc au plus m-1 lieutenant sont des traîtres. Puisqu'il y a plus de 3m généraux, il y a plus de 3m-1 lieutenants, et 3m-1>3(m-1). Nous pouvons alors appliquer l'hypothèse de récurrence pour déduire que OM(m-1) satisfait IC1 et IC2. Ainsi pour chaque j, chaque groupe de deux lieutenants obtient la même valeur pour v_j à l'étape (3) (cela se déduit par IC2 si l'un des deux lieutenants est le lieutenant j, et par IC1 dans les autres cas). Ainsi, chaque groupe de deux lieutenants obtient le même vecteur de valeurs v₁,..., v_n-1 et obtient donc la même valeur majorité(v₁,..., v_n-1) à l'étape (3), ce qui prouve IC1. []

Complexité

La mise en oeuvre de l'algorithme OM(m) cause tout d'abord l'émission de n-1 messages. Chacun de ces messages invoque OM(m-1) causant l'émission de n-2 nouveau messages etc.

[1] : (n-1) messages
[2] : (n-1)(n-2) messages
...
[m+1] : (n-1)(n-2)...(n-(m+1)) messages
_______________________________________________

Nombre total de messages : O(n^m+1). (voir [2])

Note : Les m+1 étapes d'échange de messages sont une caractéristique fondamentale des algorithmes qui arrivent à un consensus en la présence de m éventuels processus déficients.

Conclusion

La difficulté à résoudre le problème des 3 généraux se trouvent dans la capacité d'un lieutenant traître de mentir à propos de l'ordre reçu du commandant, ainsi, si nous pouvons restreindre cette capacité en ajoutant les suppositions suivantes aux trois précédentes (S1, S2 et S3), le problème des trois généraux est alors solvable pour un nombre quelconque de traîtres.

Cela s'applique facilement à des systèmes informatiques par l'utilisation de signatures numériques (souvent associées aux algorithmes de cryptographie moderne). Ce type de solution va donc nous intéresser tout particulièrement.

Maintenant que nous avons introduit les messages signés, l'argument précédent qui faisait que nous avions besoin de quatre généraux pour pouvoir tolérer la présence d'un traître n'a plus de raison d'être. Nous donnons maintenant un algorithme capable ce gérer m traîtres avec un nombre quelconques de généraux (le problème étant cela dit sans intérêts si il y a moins de m+2 généraux).

L'algorithme

Dans cet algorithme, le commandant envoie un message signé à chacun de ces lieutenants. Chaque lieutenant appose ensuite sa signature sur cet ordre et l'envoi aux autres, qui font alors de même, etc. Cela signifie qu'un lieutenant doit recevoir un message, en faire des copies, les signer, puis les envoyer. Peu importe comment les copies sont effectuées.

L'algorithme suivant suppose que l'on définisse une fonction choix qui s'applique à un ensemble d'ordre afin d'en obtenir un seul. Les seuls conditions pour cette fonction sont :

1. Si l'ensemble V contient un unique élément v, alors choix(V) = v.
2. choix({}) = vdef.

Notation : v:j:i représente la valeur v signé par j, puis la valeur v:j signé par i.

On considère que le général₀ est le commandant.
Chaque lieutenant conserve un ensemble V_i d'ordres signés corrects qu'il a reçu jusqu'alors (avec un commandant loyal, cet ensemble ne doit pas contenir plus d'un seul élément).

Algorithme SM(m)

Initialement V_i = {} .
(1) Le commandant envoie sa valeur signée à chacun des lieutenants.
(2) Pour chaque i :

1. Si le lieutenant i reçoit un message v:0 et qu'il n'a pas encore reçu d'autres ordres, alors :
1. il fixe V_i à {v}
2. il envoie v:0:i à chacun des autres lieutenants.
2. Si le lieutenant i reçoit un message de la forme v:₀:j₁:...:j_k et v n'est pas dans l'ensemble V_i alors
1. V_i = V_i + {v}
2. Si k<m alors envoyer le message v:0:j₁:...:j_k:i à chacun des lieutenant autres que j₁,...,j_k.

(3) Pour chaque i :
Quand il n'y a plus de messages, le lieutenant i obéit à l'ordre choix(V_i).

Le commandant est un traître.

Note : avec des messages signés, les lieutenants peuvent détecter que le commandant est un traître du fait que sa signature apparaît sur deux ordres différents, et d'après S4 il est le seul à avoir pu les signer.

Théorème

Pour chaque m, l'algorithme SM(m) résout le Problème des Généraux Byzantins si il y a au plus m traîtres.

Preuve :

Prouvons tout d'abord IC2. Si le commandant est loyal, alors il envoie son ordre signé v:0 à chacun des lieutenants à l'étape (1). Chaque lieutenant va alors recevoir l'ordre v à l'étape (2)(A). De plus, puisqu'aucun traître ne peut imiter un ordre de la forme v':0, un lieutenant loyal ne peut pas recevoir d'autre ordre à l'étape (2)(B). Ainsi, pour chaque lieutenant loyal i, l'ensemble V_i obtenu à l'étape (2) consiste en un unique ordre v, auquel il obéira à l'étape (3), du fait de la 1^ère propriété de la fonction choix. Cela prouve IC2.

Puisque IC1 découle de IC2 lorsque le commandant est loyal, nous n'avons plus qu'à considérer le cas où le commandant est un traître. Deux lieutenants loyaux i et j obéissent au même ordre à l'étape (3) si les ensembles V_i et V_j obtenus à l'étape (2) sont les même. Donc, pour prouver IC1 il suffit de prouver que, si i place un ordre v dans V_i à l'étape (2), alors j doit placer le même ordre v dans V_j à l'étape (2). Pour cela, il nous faut montrer que j reçoit un message correctement signé contenant cet ordre. Si i reçoit l'ordre v à l'étape (2)(A), alors il l'envoie à j à l'étape (2)(A)(ii) ; donc j le reçoit (du fait de S1). Si i ajoute l'ordre v à V_i dans l'étape (2)(B), alors il doit recevoir un premier message v:0:j₁:...:j_k. Si j est l'un des j_r, alors, du fait de S4, il a déjà dû recevoir l'ordre v. Si ce n'est pas le cas, il faut considérer 2 cas :

1. k<m. Dans ce cas, i envoie le message v:0:j₁:...:j_k:i à j ; donc j doit recevoir l'ordre v.
2. k=m. Puisque le commandant est un traître, au plus m-1 des lieutenants sont des traîtres. Ainsi, au moins l'un des lieutenants j₁,...,j_m est loyal. Ce lieutenant loyal doit avoir envoyer à j la valeur v quand il l'a reçue pour la première fois, donc j doit avoir reçu cette valeur.

Cela complète la preuve. []

Complexité

Le nombre de messages nécessaires est toujours en O(n^m+1).
Le nombre d'étapes nécessaires est lui aussi toujours de m+1. (voir [2])

Le lecteur attentif aura très certainement remarqué que les algorithmes précédemment énoncés considéraient qu'il existe un chemin direct entre chaque général (ou processeur). Or, dans la pratique, il est peu probable que de telles conditions soient présentes. Nous allons donc voir comment ces algorithmes peuvent être modifiés afin de pouvoir être appliqués à des graphes de connectivité plus réduite.

Nous considérons donc les généraux comme les noeuds d'un graphe G simple (c'est à dire qu'il n'y a au plus un arc entre deux noeuds), fini et non orienté, où un arc entre deux noeuds indique que ceux-ci peuvent s'envoyer des messages directement. Nous allons maintenant étendre les algorithmes OM(m) et SM(m), qui supposaient que G était complètement connecté, afin de les appliquer à des graphes plus généraux.

Afin d'étendre l'algorithme utilisant les messages oraux OM(m), nous avons besoin de la définition suivante, où deux généraux sont dits voisins s'ils sont reliés par un arc.

Définition

Nous étendons maintenant OM(m) en un algorithme qui résout le Problème des Généraux Byzantins en la présence de m traîtres si le graphe G de généraux est 3m-régulier. (Il faut noter qu'un graphe 3m-régulier contient au moins 3m+1 noeuds) Pour tout entier positif m et p, nous définissons l'algorithme OM(m, p) comme suit, quand le graphe G de généraux est p-régulier. La définition utilise une récursivité sur m.

Algorithme OM(m, p)

Il faut remarquer que si l'on supprime un seul noeud d'un graphe p-régulier, il devient un graphe (p-1)-régulier. Ainsi on peut appliquer l'algorithme OM(m-1, p-1) à l'étape (2)(B).

Lemme

Pour tout m>0 et pour tout p > 2k+m, l'algorithme OM(m, p) satisfait IC2 et il y a au plus k traîtres.

Théorème

Pour tout tout m>0 et tout p > 3m, l'algorithme OM(m, p) résout le Problème des Généraux Byzantins si il y a au plus m traîtres.

Le lecteur intéressé par les preuves de ces deux énoncés se reportera à [1].

Cette extension de l'algorithme OM(m) nécessite que le graphe G soit 3m-régulier, ce qui est une hypothèse de forte connectivité. En fait si il y a seulement 3m+1 généraux (c'est à dire le minimum requis), alors la 3m-régularité du graphe correspond à un connectivité complète, et OM(m, 3m) se réduit à OM(m).

Par contre, l'algorithme SM(m) est facilement étendu afin de permettre la plus faible connectivité possible. Il nous faut tout d'abord établir quelle connectivité est nécessaire pour que le Problème des Généraux Byzantins soit solvable. IC2 requiert qu'un lieutenant loyal obéisse à un commandant loyal. Cela est clairement impossible si le commandant ne peut pas communiquer avec le lieutenant. En particulier si le message du commandant au lieutenant doit être relayé par des traîtres, alors il n'est pas possible de garantir que le lieutenant obtiendra le message du commandant. De même, IC2 ne peut être garantie si deux lieutenants ne peuvent communiquer que par l'intermédiaire d'un traître.

L'hypothèse de connectivité la plus faible pour laquelle le problème est solvable est que le sous-graphe formé par les généraux loyaux soit connecté. Nous pouvons montrer que sous cette hypothèse, l'algorithme SM(n-2) est une solution, où n est le nombre de généraux – indépendamment du nombre de traîtres. Bien sûr, il est nécessaire de modifier l'algorithme afin de n‘envoyer des messages que là où ils peuvent l'être. Plus précisément, à l'étape (1), le commandant n'envoie on ordre signé qu'à ces voisins ; et à l'étape (2)(B), le lieutenant i n'envoie le message qu'à ses voisins qui n'apparaissent pas dans la signature.

Définition

Le diamètre d d'un graphe est le plus petit nombre tel que deux noeuds quelconques sont reliés par un chemin d'au plus d arcs.

Théorème

Pour tout m et d, si il y a au plus m traîtres et que le sous-graphe de généraux loyaux a un diamètre égal à d, alors SM(m+d-1) (avec les modifications évoquées plus haut) résout le Problème des Généraux Byzantins.

Corollaire

Si le graphe des généraux loyaux est connecté, alors SM(n-2) résout le problème des Généraux Byzantins pour n généraux.

Les lecteurs intéressés par les preuves de ces deux énoncés se reporteront une fois encore à [1].

Maintenant que nous savons qu'il est possible de résoudre le Problème des Généraux Byzantins dans les conditions précédemment énoncées, étudions les applications possibles aux systèmes informatiques.

Nous avons déjà énoncé les conditions IC1 et IC2 modifiées afin de s'appliquer à des systèmes informatiques, ainsi que les correspondances avec les suppositions S1, S2, S3 et S4. Nous avons aussi tenté de montrer à chaque fois le parallèle qui pouvait être fait avec de tels systèmes. Etudions maintenant les domaines d'applications.

L'intérêt d'un tel algorithme dans le domaine informatique est de pouvoir multiplier des processeurs (ou ordinateurs) afin de garantir une certaine sécurité dans les système critiques. Par exemple, un système de surveillance d'une centrale nucléaire va nécessiter que les mêmes données soient traitées par plusieurs processeurs différents. Cela dans le but de garantir que si l'un des processeurs venait à souffrir d'un dysfonctionnement, les valeurs qu'il envoie ne soient pas traitées par le système de surveillance.

Prenons l'exemple suivant (issu de [4]) :

On dispose de trois ordinateurs (A, B et C), chacun reliés à un capteur, relevant une même donnée. Les ordinateurs doivent alors se mettre d'accord sur la valeur à utiliser. Pour cela ils utiliserons la fonction choix=moyenne. Puisque nous sommes en présence de trois machines, et d'un possible traître, l'algorithme à utiliser est bien évidemment SM(1).

Si dans un premier temps, C envoie la valeur 9 à A, puis la valeur 12 à B, alors les ordinateurs ne seront pas d'accord sur la valeur qui doit être considérée comme valide.

En effet V_A = {9, 10, 11} et la valeur moyenne = 10

Mais pour B, V_B = {10, 11, 12} et moyenne = 11.

En appliquant l'algorithme SM(1), ils auraient pu s'apercevoir que C n'avait pas envoyé la même valeur aux deux ordinateurs, et donc auraient pu ignorer celle-ci de par l'implémentation de la fonction moyenne (qui, rappelons-le, joue ici le rôle de la fonction choix).

On voit donc que ce genre d'algorithme a une importance capitale dans le cadre de la mise en oeuvre de systèmes informatiques fiables, ou critiques.

On peut remarquer que en informatique, un processeur peut très bien générer de manière aléatoire des données, et donc la signature numérique d'un autre processeur. Bien évidemment, cela est fort peu probable et peut être négligé, surtout si on choisit une taille de signature suffisamment conséquente. Une autre remarque est que si les problèmes de dysfonctionnement sont dus à des actions externes comme un humain essayant de corrompre le système, les signatures numériques peuvent alors être remplacées par des systèmes de cryptographie.

Il existe une version simplifiée du problème (Weak Byzantine General Problem) qui peut être utilisée dans le cadre des bases de données distribuées. Les lecteurs intéressés peuvent se reporter à [5].

Ces algorithmes proposent bien une solution au Problème des Généraux Byzantins, néanmoins, quelques problèmes restent posés, principalement dans le cadre de leur mise en oeuvre dans les systèmes informatiques existants.

La première remarque à faire est le nombre important de messages générés par de tels algorithmes. Mais cela est dû à la complexité du problème et ne peut malheureusement pas être réduit.

Il est bien sûr possible de faire quelques suppositions supplémentaire telles que, en informatique, il est plus probable qu'un composant tombe en panne, plutôt que se mette à envoyer des données corrompues. Mais si l'on cherche à mettre en oeuvre des systèmes réellement fiable, alors de telles suppositions n'ont pas lieu d'être.

Une autre remarque est que, si l'on souhaite mettre en oeuvre ce système sur un réseau d'ordinateurs, il est rare que ceux-ci ait une topologie p-régulière [3].

En conclusion, ces solutions ne sont applicables que dans des systèmes spécifiquement prévus à cet effet (du fait de la topologie), mais aussi où la performance a moins d'importance que la fiabilité. En effet ces algorithmes sont excessivement consommateurs de ressources (processeur et réseau).

[1] " The Byzantine Generals Problem ", Leslie LAMPORT, Robert SHOSTAK, Marshall Pease.

[2] " The Byzantine Generals Problem (consensus in the presence of uncertainties) ", Kramer, Magee.

[3] " The Byzantine Generals Problem, notes ", Xun Wilson Huang.

[4] " Fault Tolerance in distibuted system ", Johan Karlsson.

[5] " Byzantine Generals and Transaction Commit Protocols ", Leslie LAMPORT, Michael Fischer.

[6] " Les problèmes de diffusion et de consensus dans les systèmes répartis ", G. Florin.