Hallo,

ich weiß, dass es mehrere Postings zu dem Thema gibt, die mir aber leider nicht die Erleuchtung bringen, denn ich verstehe den Algorithmus trotzdem nicht (stehe gerade echt auf dem Schlauch)…

Es geht um den Algorithmus 8.12 im FGI2/PNL-Skript zur Lösung des Konsensproblems.

- Kann bitte jemand noch mal in einfachen Worten beschreiben, wie (genauer warum) in f+1 Runden alle zuv. Proz. den gleichen Wert haben. Wie wird verhindert, dass z.B. in Runde f+1 ein unzuv. Proz. einen für die anderen kleinsten Wert an *nicht alle* zuv. Proz. sendet?

- Der Alg. deutet an, dass in jeder Runde alle Proz. ihre Menge V an alle senden, in den Grundannahmen steht allerdings, dass immer nur ein zuv. Proz. + max. 1 unzuv. Proz. V senden. Was stimmt davon?

Bin für jeden Hinweis dankbar! [5]

Hallo,

Es geht um den Algorithmus 8.12 im FGI2/PNL-Skript zur Lösung des Konsensproblems.

- Kann bitte jemand noch mal in einfachen Worten beschreiben, wie (genauer warum) in f+1 Runden alle zuv. Proz. den gleichen Wert haben. Wie wird verhindert, dass z.B. in Runde f+1 ein unzuv. Proz. einen für die anderen kleinsten Wert an *nicht alle* zuv. Proz. sendet?

In jeder Runde sendet jeder zuverlässige Prozessor seinen Minimalwert an alle. Der schlimmste Fall ist folgender:
Am Anfang landet der kleinste Wert bei einem unzuverlässigem Prozessor, der ihn nur an einen einzigen anderen Prozessor weitergibt, bevor er ausfällt. (Ausfallen ohne Weitergeben gibts nicht.)
dieser Fall kann sich jetzt immer weiter fortpflanzen - es wird also immer nur an einen anderen Prozessor gesendet und der sendende Prozessor fällt dann aus.

Da aber nur f Prozessoren ausfallen können, muss der letzte zuverlässig sein und den Wert an alle schicken. Somit haben alle Prozessoren den Wert nach der f+1. Runde.

Wie wird verhindert, dass z.B. in Runde f+1 ein unzuv. Proz. einen für die anderen kleinsten Wert an *nicht alle* zuv. Proz. sendet?

Wenn in Runde f+1 noch ein unzuverlässiger Prozessor am Leben ist und den kleinsten Wert hat, dann muss er den Wert entweder vorher schonmal zuverlässig gebroadcastet haben, oder, wenn er ihn gerade erst bekommen hat, in der Runde davor ein Prozessor diesen Wert an alle geschickt haben (denn es können nur f-mal Prozessoren sterben, danach gibt es keine sterblichen mehr). In Runde f+1 ist der kleinste Wert also schon einem zuverlässigen Prozessor bekannt und wird deshalb auch zuverlässig an alle verteilt.

Das schlimmste, was beim Ausfallkonsens passieren kann, ist ja, dass der kleinste Eingabewert bei einem unzuverlässigen Prozessor A ist und dieser ihn in der ersten Runde nur an einen anderen Prozessor B weiterschickt und gleich abraucht. Um weiter beim schlimmsten Fall zu bleiben, sei B nun auch ein unzuverlässiger Prozessor, der es in der nächsten Runde nur noch schafft, den Wert an Prozessor C zu senden, der wiederum unzuverlässig ist usw. Wenn das immer so weiter geht, sind nach f Runden alle unzuverlässigen Prozessoren kaputt und der Wert befindet sich bei einem zuverlässigen Prozessor (es sei denn, irgendeiner der unzuverlässigen Prozessoren hat es nicht mal mehr geschafft, eine einzige Nachricht abzusenden, aber das ist ja dann auch okay). In der f+1. Runde wird der Wert dann zuverlässig verteilt.

- Der Alg. deutet an, dass in jeder Runde alle Proz. ihre Menge V an alle senden, in den Grundannahmen steht allerdings, dass immer nur ein zuv. Proz. + max. 1 unzuv. Proz. V senden. Was stimmt davon?

Nichts. In jeder Runde versuchen alle Prozessoren, ihre Nachrichten an alle anderen zu senden. Unzuverlässige Prozessoren können unterwegs kaputt gehen.

/edit: Arne war schneller. Aber dann will ich da nochmal meckern:

Ausfallen ohne Weitergeben gibts nicht.

Woher hast Du das? Ich denke schon, dass das möglich ist - es wäre ja auch nicht weiter problematisch für den Ausfallkonsens.

Vielen Dank, ich glaube nun hab ichs verstanden… Ist ja eigentlich auch gar nicht so schwer [28].

Ich habe mich einfach von den Grundannahmen verwirren lassen:

Jede Runde enthält genau einen Rechenschritt eines zuverlässigen Prozessors.

Daraus habe ich geschlossen, dass auch nur ein zuv. Proz. pro Runde sendet. Scheint ja nicht so zu sein…

Eine Motivation für den Ausfallkonsens kommt ja aus dem Datenbankbereich: alle an einer Transaktion beteiligten Prozessoren müssen sich auf ein Element der Menge {abort, commit} einigen (mit abort < commit).

Angenommen, es gibt ein Netzwerk mit vier Prozessoren. f sei 1. Alle vier Prozessoren sind bereit zu commiten, also V = {commit}. Einer der vier Prozessoren fällt aus, nachdem er mindestens einem anderen Prozessor mitgeteilt hat, dass er bereit ist.

Die drei übrigen Prozessoren einigen sich nach 2 Runden auf commit. Das bedeutet doch, dass die Transaktion durchgeführt wird. Wie kann man das aber sinnvoll realisieren, wenn einer der vier an der Transaktion beteiligten Prozessoren ausgefallen ist??

Die Abbildung 8.27 auf Seite 345 des FGI-2 Skripts (Illustration zum Beweis von Lemma 8.39) hat einen Haken:

In Runde 2 schickt pi2 x an pi3. pi3 ist zuverlässig und schickt x daher in Runde 3 an ALLE Prozessoren (also auch pi5!). Warum ist dann noch der Pfeil von pi4 an pi5 in Runde 4 eingezeichnet? pi5 kennt x doch bereits, weil pi3 es ihm in Runde 3 mitgeteilt hat.

Auch die Argumentation, ri sei deswegen nicht minimal, kann ich nicht nachvollziehen. Es ist doch durchaus vorstellbar, dass in den ersten f Runden x von unzuverlässigen Prozessoren weitergesendet wird, welche nach dem Senden von x an einen Prozessor ausfallen. In Runde f+1 könnte dann doch ein zuverlässiger Prozessor x an zwei andere zuverlässige Prozessoren pi und pj schicken, so dass ri = rj = f+1 gilt.

Wo ist mein Denkfehler?

Das bedeutet doch, dass die Transaktion durchgeführt wird. Wie kann man das aber sinnvoll realisieren, wenn einer der vier an der Transaktion beteiligten Prozessoren ausgefallen ist??

"In diesem Kapitel betrachten wir den Fall, dass in einem verteilten System versandte Nachrichten nicht zuverlässig beim adressierten Empfänger ankommen". Das bedeutet also, ein ausgefallener Prozessor kann nicht mehr mit anderen Prozessoren kommunizieren, 'funktioniert' ansonsten aber noch reibungslos?

Auch das ist mit dem Datenbankbeispiel nicht vereinbar. Nehmen wir ein Netzwerk aus z.B. 10 Prozessoren an. Wenn V1 = {commit} ist und V2 = {abort} und p1 nach dem Senden von commit ausfällt, dann erreicht ihn die Information, dass p2 die Transaktion abbrechen will, nicht. Nach f+1 Runden ist V1 = {commit} und V2 = {abort, commit}, was für die verteilte Datenbank katastrophal wäre.

Kann mir also irgendjemand bestätigen, dass das Datenbankbeispiel einfach schlecht gewählt ist und mit Ausfallkonsens überhaupt nichts zu tun hat?

Kann mir also irgendjemand bestätigen, dass das Datenbankbeispiel einfach schlecht gewählt ist und mit Ausfallkonsens überhaupt nichts zu tun hat?

Gerne. Das Datenbankbeispiel ist einfach schlecht gewählt und hat mit dem Ausfallkonsens überhaupt nichts zu tun.

Bei Deinem Beispiel mit x_1 = commit und x_2 = abort ist die Vorraussetzung "Alle Prozessoren haben den gleichen Eingabewert" nicht erfüllt (ich beziehe mich auf S. 344, Gültigkeit) , damit ist es auch völlig egal, wofür sie sich entscheiden - der Algorithmus kann auch beide Prozessoren sich für y_i = saufen entscheiden lassen. Hauptsache, sie entscheiden sich für das gleiche (Einigung).