In der bekannten Veröffentlichung Unmöglichkeit des verteilten Konsenses mit einem fehlerhaften Prozess (JACM85) , FLP ( Fisher, Lynch und Paterson) bewiesen das überraschende Ergebnis, dass kein völlig asynchrones Konsensusprotokoll selbst einen unangemeldeten Prozeßtod tolerieren kann.
Nachdem in Lemma 3 gezeigt wurde, dass $ D $ sowohl 0-wertige als auch 1-wertige Konfigurationen enthält, heißt es:
Rufen Sie zwei Konfigurationen Nachbarn auf, wenn das eine Ergebnis vom anderen in einem einzigen Schritt resultiert. Durch eine einfache Induktion existieren die Nachbarn $ C_0, C_1 \ in C $, so dass $ D_i = e (C_i) $ i-wertig ist, $ i = 0, 1 $.
Ich kann dem ganzen Beweis folgen, außer:
Meine Frage: Obwohl es als einfach gilt, kann ich die Existenz von $ C_0, C_1 $ nicht beweisen. Könntest du mir bitte ein paar Hinweise geben?
Danke.
D (die Menge der möglichen Konfigurationen nach dem Anwenden von e auf Elemente von C ) enthält sowohl 0-wertige als auch 1-wertige Konfigurationen (und es wird angenommen, dass sie keine bivalenten Konfigurationen enthalten).
Das ist - e ordnet jedes Element in C entweder einer 0-wertigen oder einer 1-wertigen Konfiguration zu. Nach Definition von C muss ein Wurzelelement vorhanden sein, das durch eine Reihe von "Nachbar" -Beziehungen mit allen anderen Elementen verbunden ist. Daher muss ein Grenzpunkt sein, an dem ein Element in C steht. das führt zu einer 0-wertigen Konfiguration, nachdem e Nachbarn mit einem Element in C ist, was nach e zu einer 1-wertigen Konfiguration führt.
definieren eine Abbildung f (), die: f (C) = 0, wenn e (C) 0-wertig ist. Ansonsten ist f (C) = 1, wenn e (C) 1-wertig ist.
Da e (C) nicht bivalent sein kann, wenn angenommen wird, dass D keine bivalente Konfiguration hat, könnte f (C) nur entweder 0 oder 1 sein.
Ordnen Sie zugängliche Konfigurationen aus der ursprünglichen bivalenten Konfiguration in einer Kette zu, es müssen zwei Nachbarn C0, C1 in der Kette sein, die f (C0)! = f (C1) ist. Wenn nicht, sind alle f (C) gleich, was bedeutet, dass D entweder nur alle 0-wertigen Konfigurationen oder alle 1-wertigen Konfigurationen hat.
Ich bin einmal den Weg gegangen, all diese Papiere zu lesen, nur um festzustellen, dass es eine totale Zeitverschwendung ist.
Das Ergebnis ist überhaupt nicht überraschend.
Das von Ihnen erwähnte Papier "[Unmöglichkeit des verteilten Konsenses mit einem Fehler Prozess] " 1
ist eine lange Liste komplexer mathematischer Beweise, die einfach gleichgesetzt werden mit:
1) Konsens ist ein deterministischer Zustand
2) ein (oder mehrere) fehlerhafte Systeme in einer Umgebung ist eine nicht deterministische Umgebung
3) In einer nichtdeterministischen Umgebung kann niemals ein deterministischer Zustand, eine Handlung oder ein Ergebnis erreicht werden.
Das Ende. Kein weiterer Gedanke ist erforderlich.
So funktioniert es in der realen Welt außerhalb von Acadamia.
Wenn Sie möchten, dass Agenten einen Konsens erreichen, müssen synchrone (Timing-Modell) Approximationskonstrukte hinzugefügt werden, um die Umgebung innerhalb einer gegebenen Menge von Bedingungen deterministisch zu machen. Zum Beispiel einfache Konstrukte wie Timeouts, Ack / Nack, Handshake, Witness oder viel komplexere Konstrukte.
Je näher Sie zu einem synchronen deterministischen Modell kommen möchten, desto komplexer werden die Konstrukte. Ein hypothetisches synchrones Modell hätte unendlich komplexe Konstrukte. Außerdem ist zu berücksichtigen, dass ein vollständig deterministisches synchrones Modell niemals in einem nicht trivialen verteilten System erreicht werden kann. Dies liegt daran, dass in jedem nicht-trivialen dynamischen System mit mehreren Variablen mit einem variablen Anfangszustand eine unendliche Anzahl von möglichen Zuständen, Aktionen und Ergebnissen zu jedem Zeitpunkt existiert. Chaostheorie
Betrachten Sie die Komplexität eines Konstrukts zum Erkennen von verlorenen TCP-Paketen aufgrund von Pufferüberlauffehlern in einem Router mit der Sprungnummer 21. Und die Komplexität der Erkennung des gleichen Pufferüberlauffehlers lässt das Erkennungssignal vom Konstrukt selbst fallen.
>Tags und Links distributed-computing consensus