Was ist das richtige Verhalten für einen Paxos-Agenten in diesem Szenario?

Question

Ich untersuche Paxos und bin verwirrt darüber, wie sich der Algorithmus in diesem erfundenen Beispiel verhalten soll. Ich hoffe, das folgende Diagramm erklärt das Szenario.

Einige Punkte:

• Jeder Agent agiert als Vorschlag/Akzeptor/Lerner
• Nachrichten haben Form (instance, proposal_num)
Bereiten
• Nachrichten Form (instance, proposal_num, proposal_val)
• Server1 vorschlagen haben und Server2 entscheiden beide, den Angebotsprozess gleichzeitig zu starten
• In den Anfängen Nachrichten M1, M2 und M3 gleichzeitig auftreten

Es scheint hier, dass, obwohl das Protokoll ‚richtigen‘, dh nur ein Wert S2 gewählt wird, Server1 und Server2 ist der Meinung, dass es wegen der unterschiedlichen gewählt wurde Angebotsnummern.

Wird der Paxos-Algorithmus nur beendet, wenn die Nachricht Decide(...) an die Lernenden gesendet wird? Ich muss falsch verstanden werden Paxos Made Simple aber ich dachte, die Wahl wurde in dem Moment getroffen, in dem die Antragsteller Quorum für ihre Propose(...) Nachrichten erreicht haben.

Wenn die Wahl erst getroffen wird, nachdem die Decide(...) Nachricht an die Agenten gesendet wurde, sollte Server2 das Senden von Decide(1, 5, S2) beenden, wenn es sich erholt, weil es eine spätere Prepare(1, 7) sah?

Answer 1

nur gonna neu definieren die Begriffe (lassen Sie sich auch die 1 werfen, weil wir nur eine Paxos Iteration Prüfung):

1) vorschlagen (n) == vorschlagen (n) Nachricht von einem Antragsteller mit Strom Identität n

2) AcceptPrepare (n, v) == ack (n, v), Nachricht an den Antragsteller gesendet n. v ist leer, wenn dieser Knoten noch keinen Wert akzeptiert hat, z. v ist gleich dem akzeptierten Wert

3) CreateDecide (n, v) == akzeptieren! (x, v), die Knoten bitten, diesen Wert vom Antragsteller mit der Identität x zu akzeptieren. Knoten werden die Nachricht ablehnen, wenn sie eine prepare (n) -Nachricht bestätigt haben, wobei n> x

Sobald das Quorum für prepare (n) erreicht ist - das heißt, eine Mehrheit hat die Nachricht bestätigt - dann sendet der Antragsteller mit der Identität n einen Befehl accept! (n, v) aus. Wenn ein prepare (n + x), x> 0, von einem Antragsteller mit der Identität n + x - und es wird von einer Mehrheit bestätigt - zwischen den ack (n, v) Nachrichten und dem accept! (n, v), dann hat eine Mehrheit versprochen, keine mit einem Zeitstempel vorgeschlagenen Werte zu akzeptieren < n + x, x> 0 (AKA die Knoten lehnen die Annahme ab! (n, v))

sobald eine Mehrheit eine "accept!" - (n, v) -Nachricht erhält, die sie nicht zu ignorieren versprochen haben.

Wenn also server2 wieder online geht und sendet sie an! (5, S2), wird sie ignoriert werden, da 5 < 7.

Answer 2

einen Kontrapunkt zur akzeptierte Antwort zu geben, der Algorithmus selbst nie wirklich braucht zu beenden in jedem schrecklich klar definierten Sinne.Es ist sinnvoller, über jeden Knoten zu sprechen, der seine Teilnahme an dem implementierungsdefinierten Algorithmus individuell beendet. Dann könnte man vielleicht sagen, dass der Algorithmus selbst beendet ist, wenn alle teilnehmenden Knoten ausgefallen sind, wenn das eine nützliche Sache wäre, die man wissen möchte.

Der Algorithmus hat effektiv konvergiert, sobald eine Mehrheit von Akzeptoren ihre AcceptPropose Nachrichten für die gleiche Abstimmung geschickt hat (in dem Sinne, dass einmal, dass es passiert ist, ist keine Option, über das, was Wert letztlich entschieden werden kann), aber das Dies ist kein Sachverhalt, der in der Praxis beobachtet werden kann: Wenn das Netzwerk beispielsweise unmittelbar vor dem Senden dieser Nachrichten AcceptPropose Nachrichten senden würde, könnte kein Knoten erfahren, dass der Algorithmus konvergiert ist, bis die Konnektivität wiederhergestellt wurde.

Sobald jedoch ein Knoten weiß, dass der Algorithmus (indem er empfangene AcceptPropose Nachrichten von einer Mehrheit) konvergiert hat es ist sicher für den gewählten Wert über herkömmliche Mittel zu teilen, z.B. durch Senden einer Decide Nachricht durch Broadcast oder Klatsch und für andere Knoten, um es weiterzuleiten, bis jeder Knoten weiß, dass die Konvergenz erreicht wurde.

Jeder Knoten kann seine Teilnahme an dem Algorithmus beenden, sobald er den Wert kennt, zu dem der Algorithmus konvergiert ist, obwohl er es vorziehen würde, abhängig von den Implementierungsbeschränkungen länger beizutreten.

Sie müssen ein wenig über die Fehlertoleranz nachdenken, um sich davon zu überzeugen, dass das Beenden bei der Entscheidung Lebendigkeit bewahrt: Wenn alle Knoten, die wissen, welcher Wert entschieden wurde, sterben sollten, bevor sie es teilen könnten, wäre Fortschritt möglich ? Die Antwort ist, glücklicherweise, ja: Solange eine Mehrheit von Knoten am Leben bleibt, wenn einer von ihnen den entschiedenen Wert kennt, kann er ihn mit den anderen teilen, und wenn nicht, dann gibt es eine Mehrheit von teilnehmenden Knoten, die nur auswählen müssen eine höhere Wahlnummer und eine weitere Runde.

---

Eine Sache vorsichtig zu sein in der akzeptierte Antwort ist dieser Satz:

Die Wahl so schnell gemacht wird als eine Mehrheit eine akzeptieren erhält (n, v) Meldung, die sie nicht haben! versprach zu ignorieren.

Erstens gibt es nichts in dem Protokoll über vielversprechendeAcceptPropose Nachrichten zu ignorieren. Versprechen, zu denen Propose Messages ignoriert/abgelehnt werden sollten. Eine Mehrheit von AcceptPropose Nachrichten kann immer verwendet werden, um den gewählten Wert zu lernen, unabhängig von der Wahlnummer.

Zweitens ist die Wahl effektiv gemacht, sobald eine Mehrheit AcceptPropose Nachrichten sendet. Sie können dies nicht direkt beobachten, also müssen Sie warten, bis mindestens ein Knoten AcceptPropose Nachrichten von einer Mehrheit erhalten hat, bevor Sie wissen, dass die Wahl getroffen wurde. Sobald das passiert ist, können Sie den ausgewählten Wert über weitere AcceptPropose Nachrichten oder über einen Broadcast/Klatsch von Decided Nachrichten teilen, je nachdem, welche Ihrer Implementierungsbeschränkungen besser sind.