Konsensproblem verteilter Systeme

Ich habe gerade zum ersten Mal über verteilte Systeme gelesen. Es gibt einen ziemlich guten Beweis für die Unmöglichkeit eines Konsenses in einem asynchronen Modell unter Verwendung einer kombinatorischen Topologie. Andererseits gibt es in praktischen Systemen mehrere Konsensprotokolle, die verteilte Zustandsmaschinen wie Paxos und Raft synchronisieren. Der Schlüssel zu diesem wahrgenommenen Widerspruch scheint die sogenannte Fehlererkennung zu sein.

Meine Frage lautet wie folgt: Was geben Protokolle wie Paxos und Raft auf, dh wie widersprechen sie nicht dem Theorem? Wie passt die Fehlererkennung hierher?

Gibt es Papiere, die diese Beziehungen diskutieren und einen Blick wert sind?

Das FLP-Theorem [1] sagt das

Es ist für eine Reihe von Prozessoren in einem asynchron verteilten System unmöglich , sich auf einen Binärwert zu einigen , selbst wenn nur ein einzelner Prozessor einem unangekündigten Absturz ausgesetzt ist .

Laut Jennifer Welch gibt es mehrere Möglichkeiten, diese Unmöglichkeitsergebnisse zu umgehen . Ich empfehle Ihnen, die verlinkte Webseite zu lesen

1. Ändern der Systemannahmen

   • Angenommen, ein synchrones System wie im Problem "Byzantinische Generäle" [2]
   • Angenommen, ein partielles synchrones System, in dem Fehlerdetektoren [3] verwendet werden

2. oder Ändern der Problemstellung

   • Keine Garantie für Kündigung (Fortschritt) wie Paxos [4]
   • Randomisiertes Protokoll [5]
   • Es ist nicht erforderlich, sich auf einen einzelnen Wert zu einigen, wie z. B. beim Problem der Satz-Vereinbarung$k$
   • Es ist nicht erforderlich, genaue Werte in ungefährer Übereinstimmung zu vereinbaren

[1] Unmöglichkeit eines verteilten Konsenses mit einem fehlerhaften Prozess ) JACM, 1985.

[2] Einigung über das Vorliegen von Fehlern JACM, 1980.

[3] Unzuverlässige Fehlerdetektoren für zuverlässige verteilte Systeme JACM, 1996.

[4] Paxos leicht gemacht TR. Von Lamport

[5] Ein weiterer Vorteil der freien Wahl (Extended Abstract): Vollständig asynchrone Abkommensprotokolle PODC, 1983. Es wurde gerade mit dem Edsger W. Dijkstra-Preis 2015 ausgezeichnet .