Wie funktioniert der polynomielle Algorithmus 7.2 auf S. 230 ?

Das Problem besteht in Zeile 7-9; da steht ja, daß jeder Prozessor die Meinung des Schlichters übernimmt, falls die Größe der Mehrheit, die er kennt (als pref), kleiner ist als die für eine sichere Mehrheit benötigten Stimmen (Z. 7). Wenn aber nun ein unzuverlässiger Prozessor Schlichter ist, könnte dieser doch den andernen seinen "Willen" aufdrängen, da sie ja die Meinung des Schlichters übernehmen und ihre alte vergessen (Z. 9).

Lt. Beschreibung liegt ja der Trick irgendwie dadrin, daß irgendwann ein zuverlässiger Prozessor Schlichter ist, aber was hilft das, wenn vorher alle Prozessoren von einem "Verräter" umgestimmt worden sind ?

sieh auch Beispiel 7.11, unten:
Angenommen, p0 würde jetzt allen als Schlichterspruch c sagen. Was dann ? Oder kann das nicht passieren ? Und warum ??

Die Prozessoren nehmen die MEinung des Schlichters nur dann an,
wenn die Bedingung mit der Majorität < n/2 +f nicht erfüllt ist.

Richtig, aber das hilft hier leider nicht weiter.

Um mein Beispiel mal auszufüllen:
5 Prozessoren, davon 4 zuverlässige, 2 davon sagen a, 2 b. Der Schlichter ist in der ersten Runde der unzuverlässige, sein Meinung ist c, der er aber an alle verschickt. Dann haben alle folgendes prefs-Array:caabb. Damit kommt keiner mit seiner Mehrheit (die es ja nicht gibt) über die Grenze von n/2 +f, nimmt also den Schlichterspruch an. Da der Schichterunzuverlässig ist, sagt er allen jetzt nicht bottom, sondern c. Alle übernehmen c als Meinung. Dann läuft der Alg. noch ne Runde, jetzt kann gerne ein zuverlässiger Proz. Schlichter sein, aber alle haben ja die Meinung c, da ja letzte Runde die Meinung des Königs auf pref gespeichert wurde.

Hat denn keiner hier den Algorithmus soweit verstanden/angeguckt ?

so, mal nachgeschaut:

niemand verbietet doch, dass c als Lösung rauskommt,
diese erfüllt ja auch Termination, Einigung und Gültigkeit,

bisschen in die Irre führend so ein ganz neuer Buchstabe,
und dass ein fehlerhafter Prozessor so einen großen Einfluss haben kann
hätte man im Skript ruhig auch erwähnen können,
aber Algorithmus korrekt!



interessant ist dazu Seite 232 Aufgabe 7.15 Gültigkeit II:

wenn der Wertebereich für xi und yi nur 2 Elemente enthält,
dann ist die Entscheidung yi jedes zuverlässigen Prozessors pi = Eingabewert xj für einen beliebigen Prozessor pj

das impliziert ja, dass bei mehr als 2 Werten (wie bei dir a,b,c) die Entscheidung yi ein Wert sein kann,
den kein Prozessor als Eingabe hatte, zum Beispiel so ein c

Da bist du ja endlich! [img]http://www.fb18.de/gfx/22.gif[/img]

Man kann also folgendes sagen (nicht auf meinem Mist gewachsen):
Der Algorithmus garantiert, daß, wenn es vorher eine Mehrheit unter den zuverlässigen Prozessoren gab, diese am Ende des Algorithmusse jedem Prozessor bekannt ist. Gab es keine Mehrheit, ist das Ergebnis unbestimmt.

was heißt schon Mehrheit?
bei a,a,a,b bei den 4 normalen Prozessoren
kann der fehlerhafte 5. Prozessor a, b oder selbst c durchdrücken,



man kann sagen:
der Algorithmus garantiert die drei goldenen Regeln,
die Einigung ist nicht gerade vorhersehbar ;), kann auch das undefinierte Symbol sein,

haben mehr als n/2+f fehlerfreie Prozessoren die gleiche Eingabe (das ist die Mehrheit, ja),
dann wird dies auch die Ausgabe aller fehlerfreien Prozessoren sein,

gab es keine Mehrheit dann kann alles mögliche raus kommen, auf jeden Fall bei allen das gleiche

Hmm, dann leistet der Alg. irgendwie echt weniger, als man so erwarten könnte.

Ich verstehe diesen Algorithmus irgendwie auch noch nicht so ganz.
Sehe ich das richtig, dass "maj" die Majorität bezeichnet, also für einen Prozessor, der aaabb erhält, wäre das dann a. Und wenn der King auch a sagt, ist dann "king-maj" = a-a, also Null??? Was soll das denn? Oder bezeichnet "maj" die Anzahl, die zur Mehrheit führte? In dem Falle dann 3. Ich dachte, das sei dann in "mult" gespeichert.
Und was ist dieses ominöse k in dem Algorithmus?
Gibt es eigentlich innerhalb jeder Runde zwei Runden?

maj bezeichnet den Wert, der am meisten gewählt wurde: a
mult bezeichnet, wie oft dieser gewählt wurde: 3
king-maj ist eine Variable, die die Meinung des Schlichters repräsentiert.
Der Schlichterstatus geht reihum, daher das k. In der 2. (von 2n Runden) ist Proz 1 der Schlichter. In der 3. Runde verschicken wieder alle ihre Meinungen und gucken, ob es ne Mehrheit gibt. In der 4. ist dann Proz. 2 der Schlichter usw.

Wenn irgendwann mal ein zuverlässiger Schlichter dran ist,
dann haben entweder alle eine absolute Mehrheit (dieses 2n+f) erhalten und brauchen ihn nicht, oder keiner der zuverlässigen Prozessoren. Diese 2n+f sind wohl so gewählt dass sich die fehlerhaften Proz. sonst was einfallen lassen können, aber nicht eine abs. Mehrheit herbeiführen noch verhindern können. In dem Fall dass keiner eine abs. Mehrheit erhält, entscheidet der zuv. Schlichter und alle übernehmen den Wert. Daher ist nach 2(f+1) Runden eine Einigung erzielt.

wenn du schon 2x 2n+f schreibst, dann muss ich das ja korrigieren, bevor du dir das falsch einprägst ;)
die Mehrheit liegt bei n/2+f

——–

auch nicht weiter wild, nur der Korrektheit wegen
nachdem ich das alles mal durchgerechnet [edit ehrlicher: durchprobiert] habe ;):

wenn irgendwann mal ein zuverlässiger Schlichter dran ist,
müssen NICHT alle oder keine eine absoulte Mehrheit haben,
es gilt aber:
wenn keiner der zuverlässigen Prozessoren in dieser Situation die absolute Mehrheit hat,
dann bekommen alle die Meinung vom Schlichter
(und danach steht das Endergebnis schon fest)


anderenfalls hat mindestens einer bereits die absolute Mehrheit,
dann muss das bei den anderen nicht auch der Fall sein,

aber auf jeden Fall hat der Schlichter eine king-maj,
die GLEICH dieser absoluten Mehrheit ist,
da sie nur um die Anzahl f geringer sein kann, also immer noch über n/2

jedenfalls haben danach dann auch alle die gleiche Meinung

autsch! Ob ich mich besser für morgen krank schreiben lasse? [img]http://www.fb18.de/gfx/2.gif[/img]

Naja, im Zweifelsfall werd ich einfach nur genau das gefragt, was ich weiß [img]http://www.fb18.de/gfx/23.gif[/img]

War ja fast so.
Ich werd immer ganau das gefragt, was ich nicht weiß und das sind im Moment die Kapitel 6-9 [img]http://www.fb18.de/gfx/26.gif[/img]

Meint ihr man brauch 8 und 9 so richtig intensiv angucken????

Also Kapitel 8 wurde ja offenbar wohl mal abgefragt (siehe PNL-Prüfungsprotokolle) und Kapitel 9 (FEn) wird in mehreren Protokollen der Fachschaftsseiten erwähnt. Vielleicht muss man sie weniger in- und auswendig kennen als PA oder Definitionen für Netze, aber so grob kennen und das Gesetz von Little mit ein paar Worten präsentieren sollte man wohl doch können [img]http://www.fb18.de/gfx/26.gif[/img]