Warum ist das Konsensproblem beim verteilten Computing so wichtig?

Im Bereich des verteilten Rechnens scheint das Konsensproblem eines der zentralen Themen zu sein, das intensiv erforscht wurde. Insbesondere die Arbeit "Impossibility of Distributed Consensus with One Faulty Process" wurde 2001 mit dem PODC Influential Paper Award ausgezeichnet .

Warum ist das Konsensproblem so wichtig? Was können wir mit Konsens sowohl in der Theorie als auch in der Praxis erreichen?

Hinweise oder Ausstellungen wären sehr hilfreich.

Das von Ihnen erwähnte Papier ist aus zwei Gründen wichtig:

1. Es zeigt, dass es keinen asynchronen deterministischen Konsensalgorithmus gibt, der auch nur einen einzigen Absturzfehler toleriert. Beachten Sie, dass es in der synchronen Einstellung einen deterministischen Algorithmus gibt, der in Runden endet, wenn Absturz verarbeitet.≤ $f+1$$\le f$
2. Es führt die Bivalenz und Univalenz von Konfigurationen (*) ein, die später in vielen Untergrenzen und Unmöglichkeitsbeweisen verwendet werden.

Anwendungen

Eine wichtige Anwendung des Konsensproblems ist die Wahl eines Koordinators oder Leiters in einem fehlertoleranten Umfeld, um globale Maßnahmen einzuleiten. Ein Konsensalgorithmus ermöglicht es Ihnen, dies im laufenden Betrieb zu tun, ohne zuvor einen "Supernode" zu reparieren (was einen einzigen Fehlerpunkt zur Folge hätte).

Eine andere Anwendung gewährleistet die Konsistenz in einem verteilten Netzwerk: Angenommen, Sie haben verschiedene Sensorknoten, die dieselbe Umgebung überwachen. Für den Fall, dass einige dieser Sensorknoten abstürzen (oder aufgrund eines Hardwarefehlers sogar fehlerhafte Daten senden), stellt ein Konsensprotokoll die Robustheit gegen solche Fehler sicher.

(*) Ein Lauf eines verteilten Algorithmus ist eine Folge von Konfigurationen. Eine Konfiguration ist ein Vektor der lokalen Zustände der Prozesse. Jeder Prozess führt eine deterministische Zustandsmaschine aus. Jeder korrekte Konsensalgorithmus muss schließlich eine Konfiguration erreichen, in der jeder Prozess (unwiderruflich) denselben Eingabewert festgelegt hat. Eine Konfiguration ist - wertig, wenn alle möglichen Erweiterungen von zu einem Entscheidungswert von führen , egal was der Gegner tut . Analog können wir - Valenz definieren . Eine Konfiguration ist zweiwertig, wenn beide Entscheidungen von aus erreichbar sind1 C 1 0 C C $C$$1$$C$$1$$0$$C$$C$(Welcher der beiden erreicht wird, hängt vom Gegner ab). In einer zweiwertigen Konfiguration kann sich eindeutig kein Prozess entschieden haben , da wir sonst einen Widerspruch zur Übereinstimmung bekommen! Wenn wir also eine unendliche Folge solcher zweiwertigen Konfigurationen konstruieren können, haben wir gezeigt, dass es in dieser Einstellung keinen Konsensalgorithmus gibt.$C$

Es zeigt, dass es keinen fehlertoleranten deterministischen Algorithmus gibt. Ein ziemlich starkes theoretisches Ergebnis, das Designer dazu zwingt, anders mit Fehlertoleranz umzugehen. Einige davon sind Synchronisation und Randomisierung.

Kommentar: Nach meiner Meinung ist die Synchronisation eine zusätzliche Voraussetzung für das System, die in der Praxis kaum anzutreffen ist.

Referenzen finden Sie unter dem Wikipedia-Link . Überprüfen Sie auch diesen Blog für praktische Anwendungen

Ein Grund, warum Konsensprobleme wichtig sind, ist, dass sie sehr einfach sind und eine Art universelles Problem für verteilte Computersysteme darstellen.

Wenn wir einen Konsens in einem asynchronen verteilten System lösen können, können wir damit Aktionen auf gemeinsam genutzten Objekten linearisieren und Linearisierbarkeit für gemeinsam genutzte Objekte erzielen.

Wie viele Probleme sind Ihrer Meinung nach der Einfachheit halber einfacher, als sich auf einen Wert zu einigen?

Das Ergebnis der Unmöglichkeit eines Konsenses in (reinen) asynchronen verteilten Systemen zeigt, dass wir Probleme, die wir in (reinen) asynchronen verteilten Systemen lösen wollen, nicht ohne zusätzliche "Dinge" lösen können. Dies führt zu asynchronen Modellen, in denen wir einen Konsens lösen können, z. B. randomisierte Algorithmen, Fehlerdetektoren, Teilsynchronisationsmodelle usw.

Dies ist auch der Grund, warum in der Praxis konsenslösende Algorithmen wie Lamports Paxos, Googles Chubby, Apache ZooKeeper und in jüngerer Zeit Raft im Mittelpunkt verteilter Systeme stehen, bei denen wir häufig einen Status zwischen Servern replizieren möchten.

Ich möchte nur hinzufügen, dass die Art der Berechnung immer mehr auf den Stapel verteilt wird: viele CPUs, viele Prozesse auf einer Maschine, viele Maschinen, die über LANs verbunden sind, viele LANs, die über Internets verbunden sind.

Dies macht das Problem des gemeinsamen (verteilten / globalen) Zustands zum vorrangigen Problem - jeder Algorithmus nimmt einen bestimmten Zustand an, und wenn die Berechnung an mehr als einem Ort durchgeführt werden soll, muss der Zustand ebenfalls verteilt werden.

Einflussreiche Artikel ( Paxos und kürzlich Raft ) in diesem Bereich wurden nach dem von Ihnen zitierten Artikel veröffentlicht. Beide befassen sich mit den Konsensfragen, wenn einige Fehler vorliegen.

Byzantinische Fehler können in verteilten Systemen mit wenigen Ansätzen vermieden werden.

Werfen Sie einen Blick auf den Wikipedia-Eintrag zu Byzantinischer Fehlertoleranz .