Würde dieser einfache Konsensus-Algorithmus funktionieren?

Question

Um sich davon zu überzeugen, dass die Komplikationen von Standard-Algorithmen wie Paxos und Raft notwendig sind, muss man verstehen, warum einfachere Lösungen nicht zufriedenstellend sind. Nehmen wir an, dass, um Konsens WRT einen Strom von Ereignissen in einem Cluster von N Maschinen zu erreichen (dh implementieren eine replizierte Zeit wachsenden log), der folgende Algorithmus vorgeschlagen:

1. Immer wenn eine Maschine will anhängen eine Nachricht an das Protokoll, es sendet das Tupel (msg, rnd, prev), wobei msg die Nachricht ist, rnd ist eine Zufallszahl und prev ist die ID der letzten Nachricht im Protokoll.

2. Wenn ein Computer ein Tupel empfängt, fügt er msg als untergeordnetes Element von prev ein und bildet einen Baum.

3. Wenn ein Knoten mehr als ein Kind hat, wird nur das mit dem höchsten rnd als gültig betrachtet; Der Pfad gültiger Nachrichten durch den Baum ist die Hauptkette.

4. Wenn eine Nachricht Teil der Hauptkette ist und alt genug ist, gilt sie als entschieden/endgültig.

5. Wenn eine Maschine eine Nachricht zu verfassen versucht und nach einiger Zeit ist es nicht auf der Hauptkette, das ein anderes Gerät eine Nachricht an ungefähr zur gleichen Zeit ausgestrahlt bedeutet, so dass Sie-Sendung wieder, bis es ist da.

Sieht einfach, effizient und widerstandsfähig gegen Abstürze. Würde dieser Algorithmus funktionieren?

Answer 1

Ich glaube, Sie haben ein Problem, wenn eine Maschine in Folge zwei Tupel senden und die ersten verloren geht (Paketverlust/Korruption oder was auch immer)

In diesem Fall kann sagen Maschine 1 elemtent-ID von 10 prev hat und sendet zwei weitere mit (msg, rnd, 10) = 11 und (msg, rnd, 11) = 12 an Maschine 2.

Maschine 2 empfängt nur (msg, rnd, 11) aber hat keine vorherige ID von 11 in seinem Baum. Maschine 3 empfängt beide und fügt sie in den Hauptbaum ein.

Zu diesem Zeitpunkt hätten Sie eine Desync zwischen den verteilten Bäumen.

Ich empfehle eine Bestätigung für die Pakete, nachdem sie in den Baum von Maschine x an den Absender eingefügt werden, mit ihm warten, bis es die nächste sendet.

Auf diese Weise muss der Absender die vorherige Nachricht an die Maschinen senden, die in einem bestimmten Zeitraum nicht bestätigt haben.