Definition

Algorithme de consensus

Un algorithme de consensus est un processus qui permet de trouver un accord sur une valeur unique de données entre des processus ou des systèmes distribués. Ces algorithmes sont conçus pour assurer la fiabilité d'un réseau impliquant plusieurs noeuds peu fiables. La question du consensus est essentielle sur des systèmes multi-agents et distribués.

Les algorithmes de consensus partent du principe que certains processus et systèmes seront indisponibles et que des communications seront perdues. Ils doivent donc être tolérants aux pannes. Selon cette hypothèse, seule une partie des noeuds répondra, et parmi ceux-là un minimum de réponses est exigé, par exemple 51 %.

Voici quelques applications des algorithmes de consensus :

  • Décider de la validation d'une transaction distribuée
  • Désigner un noeud dirigeant pour une tâche distribuée
  • Synchroniser des états de machine pour assurer leur cohérence

Les algorithmes de consensus sont présents dans de nombreux systèmes : le PageRank de Google, l'équilibrage de charge, les réseaux intelligents, la synchronisation d'horloge et même le contrôle de drone.

La blockchain, et son registre distribué, repose également sur des algorithmes de consensus pour trouver un accord entre les noeuds. Une blockchain fonctionne comme une base de données décentralisée gérée par des ordinateurs distribués sur un réseau de pair à pair (P2P). Chaque ordinateur du réseau conserve une copie du registre de manière à empêcher les points de défaillance uniques. Les mises à jour et les validations sont répercutées simultanément sur toutes les copies.

Le Bitcoin utilise l'algorithme de preuve de travail (Proof-of-Work, PoW) pour assurer la sécurité sur un réseau non fiable. Sur les ordinateurs des mineurs, les logiciels utilisent leur capacité de traitement pour résoudre un problème mathématique lié aux transactions. Le bloc enregistre cette preuve de travail créée au cours d'un processus coûteux en calcul. En théorie, tous les participants - y compris malicieux - peuvent soumettre des blocs, mais le volume de ressources de calcul nécessaire pour duper le consensus est trop important pour qu'un participant malhonnête s'y risque.

Il existe d'autres algorithmes de consensus courants : Practical Byzantine Fault Tolerance (PBFT, ou tolérance des fautes arbitraires ou byzantines), Proof-of-Stake (PoS, ou preuve d'enjeu) et Delegated Proof-of-Stake (DPoS, ou preuve d'enjeu déléguée).

Cette définition a été mise à jour en mai 2018

Pour approfondir sur Base de données

Close