Moin, also der Beweis zum Ausfallkonsens auf Seite 226 in:

http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0506/PNL/sec/pnl0506.pdf

ist mir noch nicht so ganz klar.

Ich weiss, wie der Ausfallkonsens-Algorithmus funktioniert und warum f+1 Runden notwendig sind.

Aber ich verstehe nicht so recht, warum folgendes schon den Beweis abschliesst:

Dieser fügt jedoch x bereits in einem Durchgang d <= f < f + 1 = ri in seine Menge ein. Dies steht im Widerspruch zu der Behauptung ri sei minimal.

Also was genau wird dadurch gezeigt, dass wir zu diesem Widerspruch gelangen???

Aber ich verstehe nicht so recht, warum folgendes schon den Beweis abschliesst:

Dieser fügt jedoch x bereits in einem Durchgang d <= f < f + 1 = ri in seine Menge ein. Dies steht im Widerspruch zu der Behauptung ri sei minimal.

Also was genau wird dadurch gezeigt, dass wir zu diesem Widerspruch gelangen???

An dieser Stelle soll der Fall ri=f+1 zum Widerspruch geführt
werden. Damit wäre also gezeigt, dass nur der Fall 1<=ri<=f
eintreten kann. Und für den wurde bereits gezeigt, dass x bei
pj ankommt.

Allerdings enthält der Beweis meiner Ansicht nach einen kleinen
Fehler: Dadurch, dass ein zuverlässiger Prozessor den Wert x
vor der Runde ri empfängt, entsteht noch kein Widerspruch zur
Minimalität von ri. (Dieser entstünde erst, wenn man zeigen
könnte, dass pi den Wert x vor der Runde ri erhält).
Trotzdem kann man den Beweis retten: Man streiche den letzten
Satz und ersetze ihn durch

"Da er außerdem zuverlässig ist, sendet er x in der Runde d+1
an alle Prozessoren, also auch an pj."

Damit ist dann auch für den Fall ri=f+1 gezeigt, dass pj
den Wert x empfängt.

——————————–
Man kann den Beweis auch noch so umformulieren, dass die
logische Struktur erhalten bleibt, dass man also für den Fall
f+1 einen Widerspruch erhält. Dazu könnte man z.B. statt
ri eine Zahl rx wählen als die erste Runde, in der
irgendein zuverlässiger Prozessor den Wert x erhält
(eine solche Runde existiert, denn spätestens pi erhält x ja
irgendwann). Im Fall 1<=rx<=f gibt es dann einen zuverlässigen
Prozessor, der insbesondere pj mit x beliefert und im Fall
rx=f+1 folgert man wie im Skript, dass es einen zuverlässigen
Prozessor geben muss, der x in einer Runde d<rx empfängt.
Nur gibt es dann tatsächlich einen Widerspruch, denn nach
Wahl von rx dürfte es dann ja gar keine Runde d<rx geben, in
der ein zuverlässiger Prozessor den Wert x empfängt.

Ist das klar geworden?

Ok, so wie du es geschrieben hast, ist das plötzlich viel einleuchtender.

Besonders mit dem letzten Satz, den du ersetzt hast, wird klar, dass damit schon vor Runde f+1 der Wert einmal an alle gesendet wurde und somit schon Konsens gefunden wäre.

Danke für die schöne Erklärung.

Besonders mit dem letzten Satz, den du ersetzt hast, wird klar, dass damit schon vor Runde f+1 der Wert einmal an alle gesendet wurde und somit schon Konsens gefunden wäre.

Vielleicht meintest du das, aber im Fall d=f empfängt
der angesprochene zuverlässige Prozessor erst in Runde
f den Wert x. Er wird ihn also erst in Runde f+1 an pi
und pj senden (d.h. nicht vor Runde f+1, aber eben im
Verlauf der Ausführung des Algorithmus).

Besonders mit dem letzten Satz, den du ersetzt hast, wird klar, dass damit schon vor Runde f+1 der Wert einmal an alle gesendet wurde und somit schon Konsens gefunden wäre.

Vielleicht meintest du das, aber im Fall d=f empfängt
der angesprochene zuverlässige Prozessor erst in Runde
f den Wert x. Er wird ihn also erst in Runde f+1 an pi
und pj senden (d.h. nicht vor Runde f+1, aber eben im
Verlauf der Ausführung des Algorithmus).

Ja klar, so sehe ich das auch, hatte mich vielleicht etwas unklar ausgedrückt. [img]http://www.fb18.de/gfx/17.gif[/img]

Also danke nochmal, hat mir sehr weitergeholfen. [img]http://www.fb18.de/gfx/14.gif[/img]