Pourquoi le problème du consensus est-il si important en informatique distribuée?

19

En informatique distribuée, le problème du consensus semble être l'un des sujets centraux qui a attiré des recherches intensives. En particulier, le document "Impossibilité d'un consensus distribué avec un processus défectueux" a reçu le PODC Influential Paper Award 2001 .

Alors pourquoi le problème du consensus est-il si important? Que pouvons-nous réaliser avec un consensus à la fois en théorie et en pratique?

Toute référence ou exposition serait vraiment utile.

reference-request big-picture dc.distributed-comp hengxin
la source

Réponses:

18

Le document que vous mentionnez est important pour 2 raisons:

  1. Il montre qu'il n'y a pas d' algorithme de consensus déterministe asynchrone qui tolère même une seule panne de crash. Notez que dans le réglage synchrone , il existe un algorithme déterministe qui se termine par tours lorsque ≤ f processus se bloquent.f+1≤f
  2. Il introduit la bivalence et l' univalence des configurations (*), qui sont utilisées dans de nombreuses limites inférieures et preuves d'impossibilité plus tard.

Applications

Une application importante du problème du consensus est l'élection d'un coordinateur ou d'un leader dans un environnement tolérant aux pannes pour lancer une action mondiale. Un algorithme de consensus vous permet de le faire à la volée, sans fixer à l'avance un "supernode" (ce qui introduirait un seul point de défaillance).

Une autre application maintient la cohérence dans un réseau distribué: supposons que différents nœuds de capteurs surveillent le même environnement. Dans le cas où certains de ces nœuds de capteurs tombent en panne (ou même commencent à envoyer des données corrompues en raison d'une défaillance matérielle), un protocole de consensus garantit la robustesse contre de telles défaillances.

C1C10CCC

Peter
la source
2
@AJed En complément: J'ai jeté un coup d'œil à la synchronisation papier de Maurice Herlihy et je peux maintenant présenter une autre grande implication théorique du problème du consensus. En utilisant l'idée du nombre de consensus , on peut montrer qu'il existe une hiérarchie infinie de primitives de synchronisation, de sorte qu'aucune primitive à un niveau ne peut être utilisée pour une implémentation sans attente de primitives à des niveaux supérieurs. En termes simples, le problème du consensus se divise en une théorie unifiée sur la définition de la puissance relative des opérations de synchronisation primitive. C'est élégant.
hengxin
1
J'ai du mal à comprendre la preuve du résultat d'impossibilité FLP. Pourriez-vous me donner quelques indices? Veuillez vous référer à [FLP proof] ( stackoverflow.com/q/15131730/1833118 ). Merci.
hengxin
"où chaque processus a décidé" devrait peut-être être "où chaque processus correct a décidé"?
nbre
Vous devez expliquer qui est l'adversaire "peu importe ce que fait l'adversaire".
2018
"toutes les extensions possibles de C", que voulez-vous dire par "extension de C"? Qu'est-ce qu'une extension d'une configuration, en général?
nbro
7

Il montre qu'il n'y a pas d'algorithme déterministe tolérant aux pannes. Un résultat théorique assez fort, qui oblige les concepteurs à gérer différemment la tolérance aux pannes, dont la synchronisation et la randomisation.

Commentaire: À mon avis, la synchronisation est une hypothèse supplémentaire du système que l'on ne trouve guère dans les applications pratiques.

Pour les références, consultez le lien Wikipedia . Consultez également ce blog pour des applications pratiques

AJed
la source
1
Oui, je préfère la randomisation à la synchronisation. L'environnement dans lequel joue l'informatique distribuée est très pauvre au sens de l'asynchronisation, du retard illimité, de l'échec inattendu et trop non déterministe. Tant qu'il n'est pas parfait, pourquoi ne pas utiliser la randomisation, obtenir des garanties tout en évitant trop de complexité.
hengxin
1
En parlant de synchronisation, je n'aime tout simplement pas l'hypothèse en théorie . Cependant, dans l' industrie , la synchronisation ou la synchronisation partielle est fréquemment appliquée. Par exemple, Google's Spanner est une base de données répliquée de manière synchrone distribuée à l'échelle mondiale . Cela me rend moins décisif. Quel est ton opinion?
hengxin
Je suppose qu'il vaut mieux voir comment la synchronisation est mise en œuvre là-bas. Mais c'est une référence très intéressante. - ce que je veux dire, ce n'est pas une caractéristique naturelle du système. Il faut y ajouter.
AJed
En général, vous ne devez pas donner comme référence Wikipédia. Je viens de lire cet article Wikipedia: il est assez incomplet et non organisé; cela pourrait aussi prêter à confusion.
nbro
5

L'une des raisons pour lesquelles les problèmes de consensus sont importants est qu'ils sont très simples et qu'ils sont en quelque sorte des problèmes universels pour les systèmes informatiques distribués.

Si nous pouvons résoudre le consensus dans un système distribué asynchrone, nous pouvons l'utiliser pour linéariser les actions sur les objets partagés et obtenir la linéarisation des objets partagés.

Par souci de simplicité, combien de problèmes pouvez-vous penser qui sont plus simples que de s'entendre sur une valeur?

Le résultat de l'impossibilité d'un consensus dans les systèmes distribués asynchrones (purs) nous dit que nous ne pouvons pas résoudre les problèmes que nous voulons résoudre dans les systèmes distribués asynchrones (purs) sans quelques "trucs" supplémentaires. Cela conduit à des modèles asynchrones où nous pouvons résoudre un consensus, par exemple des algorithmes randomisés, des détecteurs de défauts, des modèles de synchronie partielle, etc.

C'est aussi la raison pour laquelle, dans la pratique, les algorithmes qui résolvent le consensus comme Paxos de Lamport, Chubby de Google, Apache ZooKeeper et plus récemment Raft sont au cœur des systèmes distribués où nous voulons souvent reproduire un état parmi les serveurs.

Kaveh
la source
0

J'ajouterais seulement que la nature du calcul est de plus en plus répartie sur la pile: de nombreux processeurs, de nombreux processus sur une machine, de nombreuses machines connectées par des réseaux locaux, de nombreux réseaux locaux connectés par des internets.

Cela rend le problème de l'état commun (distribué / global) primordial - chaque algorithme suppose un certain état et si le calcul doit être effectué à plusieurs endroits, alors l'état doit également être distribué.

Des articles influents ( Paxos et plus récemment Raft ) dans ce domaine ont été publiés après l'article que vous citez. Tous deux abordent les questions de consensus en présence de certains échecs.

Les erreurs byzantines peuvent être évitées dans les systèmes distribués en utilisant peu d'approches.

Jetez un oeil à l'entrée Wikipedia sur la tolérance aux pannes byzantine .

diginoise
la source
Le résultat d'impossibilité de FLP s'applique même dans le réglage de l'échec le plus basique (crash), donc je ne suis pas sûr de l'intérêt du paragraphe sur l'évitement des échecs byzantins. Notez que si nous n'avons pas d'échecs, le consensus est plutôt facile: un processus fixe diffuse sa valeur et chaque processus décide de cette valeur dès qu'elle est reçue.
Kaveh