Benutzer:Andrioshe/Consensus (computer science)
Ein grundsätzliches Problem in der verteilten Computerwissenschaft ist, gesamte Systemzuverlässigkeit in Gegenwart von mehreren fehlerhaften Prozessen zu erreichen. Das verlangt häufig, dass sich Prozesse über einen Datenwert einigen, der während der Berechnung erforderlich ist. Beispiele von Anwendungen der Einigkeit schließen ein, ob man eine Transaktion zu einer Datenbank begeht, sich über die Identität eines Führers, Staatsmaschinenerwiderung und Atomsendungen einigend. //Grob übersetzt :D
Problembeschreibung
Das Einigkeitsproblem verlangt Abmachung unter mehreren Prozessen für einen einzelnen Datenwert. Einige der Prozesse können scheitern oder auf andere Weisen unzuverlässig sein, so müssen Einigkeitsprotokolle tolerante Schuld sein. Die Prozesse müssen irgendwie hervor ihre Kandidatenwerte legen, miteinander kommunizieren, und sich über einen einzelnen Einigkeitswert einigen.
Eine Annäherung an das Erzeugen der Einigkeit ist für alle Prozesse, um sich über einen Majoritätswert zu einigen. In diesem Zusammenhang verlangt eine Mehrheit mindestens einen mehr als Hälfte von verfügbaren Stimmen (wo jeder Prozess eine Stimme gegeben wird). Jedoch ein oder fehlerhaftere Prozesse kann das resultierende solches Ergebnis verdrehen, dass Einigkeit nicht erreicht oder falsch erreicht werden darf.
Protokolle, die Einigkeitsprobleme beheben, werden entworfen, um sich mit begrenzten Zahlen von fehlerhaften Prozessen zu befassen. Diese Protokolle müssen mehrere Voraussetzungen befriedigen, um nützlich zu sein. Zum Beispiel konnte ein triviales Protokoll die ganze Prozessproduktion binärer Wert 1 haben. Das ist nicht nützlich, und so wird die Voraussetzung solch modifiziert, dass die Produktion irgendwie vom Eingang abhängen muss. D. h. der Produktionswert eines Einigkeitsprotokolls muss der Eingangswert etwas Prozesses sein. Eine andere Voraussetzung ist, dass ein Prozess auf und Produktion entscheiden kann, ist ein Wert nur einmal und diese Entscheidung unwiderruflich. Ein Prozess wird richtig in einer Ausführung genannt, wenn er keinen Misserfolg erfährt. Ein Einigkeitsprotokoll duldende stockende Misserfolge muss die folgenden Eigenschaften befriedigen
Termination Jeder richtige Prozess entscheidet einen Wert.
""Validity"" Wenn alle Prozesse denselben Wert v vorschlagen, dann entscheiden alle richtigen Prozesse v.
""Integrity"" Jeder richtige Prozess entscheidet höchstens einen Wert, und wenn es entscheidet, dass ein Wert v dann v durch etwas Prozess vorgeschlagen worden sein muss.
""Agreement"" Jeder richtige Prozess muss sich über denselben Wert einigen.
Wie man sagt, ist ein Protokoll, das Einigkeit richtig versichern kann, unter deren n Prozessen am grössten Teil von t scheitern, t-resilient.
Im Auswerten der Leistung von Einigkeitsprotokollen sind zwei Faktoren von Interesse Laufzeit und Nachrichtenkompliziertheit. Laufzeit wird in der Großen O Notation in der Zahl von Runden des Nachrichtenaustausches als eine Funktion von einigen Eingangsrahmen (normalerweise die Zahl von Prozessen und/oder die Größe des Eingangsgebiets) gegeben. Nachrichtenkompliziertheit bezieht sich im Wert vom Nachrichtenverkehr, der durch das Protokoll erzeugt wird. Andere Faktoren können Speicherauslastung und die Größe von Nachrichten einschließen.
Modell zur Berechnung
Es gibt zwei Typen von Misserfolgen, die ein Prozess, ein Unfallmisserfolg oder ein byzantinischer Misserfolg erleben kann. Ein Unfallmisserfolg kommt vor, wenn ein Prozess plötzlich anhält und nicht die Tätigkeit wieder aufnimmt. Byzantinische Misserfolge sind Misserfolge, in denen gar keine Bedingungen auferlegt werden. Zum Beispiel können sie infolge der böswilligen Handlungen eines Gegners vorkommen. Ein Prozess, der einen byzantinischen Misserfolg erfährt, kann widersprechende oder widerstreitende Daten an andere Prozesse senden, oder er kann auch schlafen und dann Tätigkeit nach einer langen Verzögerung fortsetzen. Der zwei Typen von Misserfolgen sind byzantinische Misserfolge viel mehr störend. So muss ein Einigkeitsprotokoll, byzantinische Misserfolge duldend, zu jedem möglichen Fehler elastisch sein, der vorkommen kann.
Eine stärkere Version der Einigkeit, byzantinische Misserfolge duldend, wird unten gegeben
Unterschiedliche Modelle der Berechnung können ein Einigkeitsproblem definieren. Einige Modelle können sich mit völlig verbundenen Graphen befassen, während sich andere mit Ringen und Bäumen befassen können. Asynchron gegen gleichzeitige Modelle für den Nachrichtenübergang kann betrachtet werden. In einigen Modellen wird Nachrichtenbeglaubigung erlaubt, wohingegen in anderen Prozesse völlig anonym sind. Geteilte Speichermodelle, in denen Prozesse durch das Zugreifen auf Gegenstände im geteilten Gedächtnis kommunizieren, sind auch ein wichtiger Bereich der Forschung.
Ein Sonderfall des Einigkeitsproblems hat gerufen binäre Einigkeit schränkt den Eingang und folglich das Produktionsgebiet zu einer einzelnen binären Ziffer {0,1} ein. Wenn das Eingangsgebiet hinsichtlich der Zahl von Prozessen, zum Beispiel ein Eingangssatz aller natürlichen Zahlen groß ist, kann es gezeigt werden, dass Einigkeit in einer gleichzeitigen Nachricht vorübergehendes Modell unmöglich ist.
Während echte Weltkommunikationen häufig von Natur aus asynchron sind, ist es praktischer und nützlich, gleichzeitige Systeme zu modellieren. In einem völlig asynchronen Nachrichtenübergang hat System verteilt, in dem-Prozess einen stockenden Misserfolg haben kann, ist es bewiesen worden, dass Einigkeit unmöglich ist. Jedoch ist dieses Unmöglichkeitsergebnis auf einen größten anzunehmenden Unfall einer Prozessliste zurückzuführen, die hoch unwahrscheinlich ist. In Wirklichkeit hat Prozessterminplanung einen Grad der Zufälligkeit.
In einem asynchronen Modell können einige Formen von Misserfolgen durch ein gleichzeitiges Einigkeitsprotokoll behandelt werden. Zum Beispiel kann der Verlust einer Nachrichtenverbindung als ein Prozess modelliert werden, der einen byzantinischen Misserfolg ertragen hat. In gleichzeitigen Systemen wird es angenommen, dass alle Kommunikationen in Runden weitergehen. In einer Runde kann ein Prozess alle Nachrichten senden, die man verlangt, während man alle Nachrichten von anderen Prozessen erhält. Auf diese Weise kann keine Nachricht von einer Runde irgendwelche innerhalb derselben Runde gesandten Nachrichten beeinflussen.
Gleichwertigkeit von Abmachungsproblemen
Drei Abmachungsprobleme der Interesse sind wie folgt:
Terminating Reliable Broadcast Siehe auch: Terminating Reliable Broadcast
Eine Sammlung von N-Prozessen, die von 0 bis n - 1 numeriert sind, kommuniziert durch das Senden von Nachrichten einander. Prozess 0 muss einen Wert v allen solchen Prozessen dass übersenden:
- wenn Prozess 0 richtig ist, dann erhält jeder richtige Prozess v
- für irgendwelche zwei richtigen Prozesse erhält jeder Prozess denselben Wert.
Es ist auch bekannt als das Problem des Generals.
