Modèle Byzantine Altruistic Rational

BAR-B est un système coopératif de sauvegarde dans lequel les nœuds d'un système distribué contribuent de manière égale au stockage[3].

L'architecture contient 3 niveaux :

1. Le premier niveau concerne les primitives;
2. Le second niveau concerne la régulation du travail;
3. Le troisième niveau concerne l'application en elle-même.

Le premier niveau, les primitives de bases, fournissent les fonctions clés afin de construire un système distribué fiable. Il repose sur le protocole IC-BFT.

Le second niveau, la régulation du travail, permet de construire un système qui ne donnera le travail déterminé qu’à un nœud au lieu de le faire exécuté par un ensemble de nœuds. La régulation du travail est effectuée grâce à un protocole dit Garantee Response protocole, qui permet de vérifier la correspondance requête-réponse.

Le troisième niveau, le niveau applicatif, implémente le service désiré en utilisant les couches de plus bas niveau.

Un des principaux problèmes est donc le fait qu’un nœud puisse agir contre l'intérêt des autres. Mais s'il est possible d’identifier le nœud et de mesurer ce qu’il effectue, ceux-ci seront plus enclin à agir de manière rationnelle[4].

BAR-B est un système coopératif de sauvegarde dans lequel les nœuds d'un système distribué contribuent de manière égale au stockage. Dans des circonstances normales, les nœuds interagissent avec BAR-B à travers trois opérations: stocker, récupérer et auditer.

Pour stocker un fichier de sauvegarde, le propriétaire le comprime et le divise en petits morceaux qui sont ensuite chiffrés. Ensuite il les envoie aux différents nœuds pour le stockage sur le système. Ces différents nœuds envoient un accusé de réception signé (Le nœud est donc identifié). Le propriétaire conserve les accusés et les nœuds gardent les infos de stockage (morceaux stockés).

Lorsque le propriétaire a besoin de récupérer un fichier, il envoie une demande de récupération à chaque nœud détenant un morceau. La demande contient l'accusé, de sorte que le nœud a trois options:

1. Envoyer le morceau;
2. Dire que la bail de stockage pour le morceau a expiré;
3. Dire qu'il a des informations de stockage plus récentes en ce qui concerne le morceau.

S'il y a une autre réponse, cela veut dire que le nœud a abandonné prématurément les données qui lui ont été confiées et ce nœud doit être puni. Les accusés sont des documents permettant un audit. Les nœuds échangent de manière périodique les accusés afin de vérifier qu'un nœud ne dépasse pas son quota de stockage[3].

Un autre exemple reprend le problème de retransmettre en direct sur internet un évènement où les membres de l'audience nommé clients, contribuent dans la diffusion des paquets de la transmission[5].

Ces clients peuvent être byzantins, altruiste ou rationnel.

Chaque client rationnel a pour stratégie la maximisation de son utilité. Un tel client dérivera du protocole que si cela augmente son utilité.

Les clients altruistes suivent le protocole peu importe le coût. Dans cet exemple, le coût est l'envoi et la réception de paquets.

Les clients byzantins fonctionnent arbitrairement ou selon des procédures non déterminées.

Les clients non-byzantins maintiennent un système d'horloge entre eux qui est synchronisé en secondes. Ils communiquent en point à point de manière synchrone et en utilisant des connexions non fiable UDP et TCP. Si un nœud ne reçoit pas un paquet attendu, il considère que le lien n'est plus valide.

Il est supposé que les clients doivent souscrire au direct avant son début et qu'un client non-byzantin reste pendant toute la diffusion[5].

C. Li propose un protocole pour réaliser ce projet : BAR Gossip. Ce protocole fait mention d'un broadcaster altruiste qui diffuse l'évènement en direct à tout un ensemble de clients. Cette diffusion en direct demande que deux propriétés soient garanties :

1. Les clients non-byzantins ne fournissent que des paquets authentiques, CAD, que des paquets générés par le broadcaster;
2. Chaque client altruiste reçoit une grande partie de tous les paquets de diffusion en un certain temps.

La première condition peut être garantie quelle que soit la situation. Par contre, la deuxième n'est certaine que dans de bonnes conditions et avec un nombre limité de clients byzantins[6].

Avant de commencer la diffusion, tous les clients doivent générer une clé privée et une clé publique. Ensuite ils s'inscrivent à l'évènement en donnant les deux clés au broadcaster. Ce dernier peut ainsi vérifier les clés et accepter l'inscription. Après collecte des clés, le broadcaster met à disposition des clients une liste avec l'identité de chaque client, son adresse et sa clé publique. Les clients vont chiffrer les messages du protocole à l'aide de leur clé privée. Ce système permet que chaque message soit authentifié, intègre et que son contenu ne puisse pas être répudié par son envoyeur[6].

Pendant le direct, le broadcaster est chargé de diviser les données en morceaux de taille fixe.

Le protocole fonctionne selon un système de tour d'une durée T + ${\displaystyle \delta }$ pendant lequel le broadcaster envoie les morceaux et que ces morceaux sont échangés entre les clients. T est un laps de temps pour l'échange de message requis par le protocole.

Le premier tour commence quand le direct commence. Chaque morceau expire à la fin du tour dans lequel le broadcaster l'a envoyé. Quand un morceau expire, tous les clients qui le possède, doivent le fournir aux lecteurs média.

À chaque tour, le broadcaster choisit un sous-ensemble de clients. Ces clients sont choisis de manière aléatoire. Ils reçoivent les morceaux, les signent et les distribuent aux autres clients. Le nombre de clients choisi aléatoirement doit être assez grand pour garantir qu'au moins un destinataire soit un client non-byzantin[6].

Un client ne recevra pas tous les morceaux directement du broadcaster. Il va devoir faire des échanges avec les autres clients. Pour cela, il utilise deux systèmes d'échange :

• Échange équilibré;
• Don optimiste.

L'échange équilibré demande que le même nombre de morceaux soient échangés entre deux clients. Ainsi, si un client c1 donne trois morceaux à un client c2, c2 en donnera lui aussi trois à c1. Dans un autre cas de figure, c1 pourrait proposer de donner cinq morceaux à c2 à alors que c2 ne sait en donner que quatre. Dans ce cas-là, c1 et c2 échangeront quatre morceaux. Un client rationnel va suivre ce protocole car s'il essaye de dévier du protocole, cela n'augmentera pas son utilité. Cependant si un client a des soucis pour obtenir ses morceaux (par exemple, à la suite de problèmes de réseaux), il aura moins à offrir et va accumuler du retard. C'est pour cela qu'il y a l'autre système d'échange : don optimiste. C'est un système optimiste car un client va distribuer les morceaux à un autre client qui en demande, sans être certain d'un retour de faveur. Ce cas permet d'effectuer un échange non équilibré[6].

• (en) Leslie Lamport, Robert Shostak et Marshall Pease, « The Byzantine Generals Problem », ACM Transactions on Programming Languages and Systems,‎ juillet 1982, p. 382-401 (DOI 10.1145/357172.357176)
• (en) Amitanand S. Aiyer, Lorenzo Alvisi, Mike Dahlin, Allen Clement, Jean-Philippe Martin et Carl Porth, « BAR fault tolerance for cooperative service », Proceedings of the twentieth ACM symposium on Operating systems principles,‎ décembre 2005, p. 45-68 (ISBN 1-59593-079-5)
• (en) Harry C. Li, Allen Clement, Edmund L. Wong, Jeff Napper, Indrajit Roy, Lorenzo Alvisi et Michael Dahlin, « BAR gossip », Proceedings of the 7th symposium on Operating systems design and implementation,‎ 2006 (ISBN 1-931971-47-1)

• (en) Zhao Wenbing et F.E. Villaseca, « Byzantine Fault Tolerance for Electric Power Grid Monitoring and Control », International Conferesnce on Embedded Software and System,‎ juillet 2008, p. 129-135 (ISBN 978-0-7695-3287-5)
• (en) Zhao Wenbing, « Byzantine Fault Tolerance for Nondeterministic Applications », Third IEEE International Symposium on Dependable, Autonomic and Secure Computing,‎ septembre 2007, p. 108-115 (ISBN 978-0-7695-2985-1)
• (en) J. Nakamura, T. Araragi et S. Masuyama, « Acceleration of Byzantine Fault Tolerance by Parallelizing Consensuses », International Conference on Parallel and Distributed Computing, Applications and Technologies,‎ décembre 2009, p. 80-87 (ISBN 978-0-7695-3914-0)
• (en) Xiu-Qun Wang, Yue-Ting Zhuang et Hong-Lun Hou, « Byzantine Fault Tolerance in MDS of Grid System », International Conference on Machine Learning and Cybernetics,‎ augustus 2006, p. 2782-2787 (ISBN 1-4244-0061-9)
• (en) Zhao Wenbing et Zhang Honglei, « Byzantine Fault Tolerant Coordination for Web Services Business Activities », International Conference on Services Computing,‎ juillet 2008, p. 407-414 (ISBN 978-0-7695-3283-7)