Paxos-Führerwahl könnte nicht beendet werden

Question

Ich studiere das Paxos gemachtes einfaches Papier, und ich kämpfe mit der Tatsache, dass Paxos Fortschritt nicht garantiert, wenn sich 2 Antragsteller mit höheren Angebotsnummern gegenseitig rasen, und wie in der Zeitung vorgeschlagen, Um den Fortschritt zu garantieren, muss ein ausgezeichneter Antragsteller ausgewählt werden, der ihn zu einem Führer macht.

Aber hier kommt das Problem, wie Leute vorschlagen, Paxos zu verwenden, um den ausgezeichneten Antragsteller zu wählen, der wieder einen Führer erfordert, um Fortschritt zu garantieren.

Ich verstehe, dass das gegebene Szenario eine Implementierung spezifisch sein könnte, zum Beispiel, wenn die distinguished Mengen, die Prozesse zur Auswahl gegeben sind bestellt werden, ich meine P1 gesetzt < P2 gesetzt.

Aber ich möchte in tatsächlichen Implementierungen verstehen, wie wird das gehandhabt?

Answer 1

Der übliche Ansatz besteht darin, einfach randomisierte Timeouts zu verwenden, bei denen es wahrscheinlich zu einem niedrigen Leaderduell kommt. Wenn Sie im Papier nach "Timeout" suchen, wird dies erwähnt.

Wenn es im Durchschnitt X Sekunden dauert, bis ein stabiler Leader auftaucht und Fortschritte macht (was wir anhand der minimalen Anzahl von Nachrichtenumrundungen schätzen können), können wir jeden Knoten innerhalb eines Intervalls, das a ist, zufällig auslaufen lassen Vielfache von X. Durch die Verwendung einer neuen Zufallszahl bei jedem Versuch, ein Anführer zu werden, haben wir eine geringe Wahrscheinlichkeit für ein erweitertes Anführerduell.

Wenn wir ein größeres Vielfaches von X als obere Grenze des zufälligen Timeouts setzen, haben wir eine geringere Wahrscheinlichkeit eines erweiterten Leaderduells. Aber wir haben auch eine längere durchschnittliche Zeit bis ein Anführer auftaucht. Es ist also ein Kompromiss.

Wenn eine Implementierung einen sehr schnellen Failover erfordert, können wir ein zufälliges Intervall mit einem niedrigen Timeout verwenden, aber versuchen, einen Mechanismus zu implementieren, mit dem ein Leaderduell schnell aufgelöst wird. Sie können jeden beliebigen Mechanismus erfinden.

Ein einfacher Mechanismus, um sicherzustellen, dass ein Knoten den Vorteil hat, der Führer zu werden, ist wie folgt. Jeder Knoten hat eine eindeutige Nummer, um seine Stimmzettel zu bestellen. Während eines Leader-Duells kann jeder Knoten einen exponentiellen Back-Off verwenden, der durch seine eigene eindeutige Nummer skaliert wird. Zum Beispiel, wenn die Knotennummer N bei jedem gescheiterten Versuch ist, der Leader zu werden, können wir die obere Grenze seines Timeout-Fensters mit 1 + 1/N multiplizieren. Dies bedeutet, dass während eines Duells der Knoten mit dem höchsten N aggressiver wird, wenn er versucht, ein Anführer zu werden, da die anderen Knoten schneller zurückgehen.