Hi,

ich hab irgendwie schwierigkeiten das causally ordered (co) bei der ordnung von nachrichten zu verstehen.
(folie 7 bei 8_3. hier gibts die folien)
definiert ist co als: m1 vor m2 -> m2 wird nicht vor m1 von einem prozessor empfangen.
aber wenn das nur für EINEN prozessor gelten muss, dann müsste doch das beispiel auf folie 7 unten auch co sein, weil der untere prozessor a b empfängt, oder seh ich das falsch?
ich kann auch nicht so recht nachvollziehen, warum das beispiel links oben auf der folie co sein soll, denn was gilt denn da a vor b oder b vor a?
wär schön, wenn mir jemand weiterhelfen könnte…

ich hab zwar das passwort zu den folien nicht, aber ich versuch trotzudem mal zu helfen ^^

definiert ist co als: m1 vor m2 -> m2 wird nicht vor m1 von einem prozessor empfangen.

das heisst doch wenn du ein nachrichtenpaar und einen prozessor findest bei dem die relation nicht gilt ist die eigenschaft für das gesamte system widerlegt. -> die relation muss für alle nachtichten und alle prozessoren gelten.



hoffe geholfen zu haben…

zum Unteren:
a sendet m1 aus. für b gilt: m1 wird empfangen, dann wird m2 verschickt. Also ist m1 vor m2 für b erfüllt. Dieses soll nun aber bedeuten, dass ALLE Prozessoren auch m1 vor m2 (vor nicht unterstrichen, sondern einfach zeitlich vor) empfangen. Dies ist ja aber nicht der Fall, weil a empfängt m2 vor (zeitlich) m1.
Der Ausdruck "von einem Prozessor" in der vor Beziehnung und in der Implikation bezieht sich dabei nicht auf denselben Prozessor (glaube ich zumindest. Vll. ist hier jemand, der das bestätigen kann??).

Der Ausdruck "von einem Prozessor" in der vor Beziehnung und in der Implikation bezieht sich dabei nicht auf denselben Prozessor (glaube ich zumindest. Vll. ist hier jemand, der das bestätigen kann??).

In der vor-Relation geht es immer um ein- und denselben Prozessor - also m1 vor m2 gilt, wenn entweder ein Prozessor X erst m1 empfängt und dann m2 sendet, oder wenn ein Prozessor X erst m1 sendet und dann m2 sendet.

Bei "casually ordered" muss nun gelten: Wenn für zwei Nachrichten m1 und m2 die vor-Relation gilt, also m1 vor m2, dann gibt es keinen einzigen Prozessor Y, der m2 empfängt, bevor er m1 empfängt. (Anders gesagt: Alle Prozessoren empfangen m1 vor m2, und das schließt auch den Prozessor X von oben ein. Dieses "m2 wird nicht vor m1 von einem Prozessor empfangen" ist zu verstehen als "es gibt nicht einen Prozessor, der m2 vor m1 empfängt" - das ist in der Tat ein bisschen komisch formuliert.)

ich kann auch nicht so recht nachvollziehen, warum das beispiel links oben auf der folie co sein soll, denn was gilt denn da a vor b oder b vor a?

Eben, es gilt gar nichts von beiden. Und wenn die Prämisse nicht erfüllt ist, ist auch automatisch die Implikation erfüllt. (Wenn Du sagst: "Alle 20m hohen Bäume aus Glas können sprechen", dann ist das auch wahr, wenn es überhaupt keine 20m hohen Bäume aus Glas gibt. Aussagenlogik: [img]http://mokrates.de/cgi-bin/texstring?A%20%5CRightarrow%20B%20%5Cequiv%20%5Cneg%20A%20%5Cvee%20B[/img])

erstmal vielen dank für die antworten. jetzt leuchtet mir das ein, vielleicht hab ich gestern einfach etwas zu viel pnl am stück gemacht, da lässt die konzentration irgendwann stark nach…

eine frage hätte ich aber doch noch zum lemma 8.51 (folie 55 8_4).
sei f=1, n=5, n/2 + f = 3,5, p0 ist fehlerhaft, p1 ist king.
p0(-), p1(b), p2(a), p3(a), p4(a)
p0(-), p1(bbaaa), p2(bbaaa), p3(abaaa), p4(bbaaa)
p0(-), p1(b), p2(b), p3(a), p4(b)

p2 und p4 haben keine mehrheit und befragen deshalb den king und legen sich somit auf b fest. bei p3 gibt es aber eine mehrheit für a. folglich haben nicht alle zuverlässigen prozessoren denselben wert. ich sehe keinen grund,warum ein solches szenario nicht möglich wäre. aber das würde dem lemma 8.51 widersprechen und ich glaube nicht, dass ich einen unentdeckten fehler in dem algorithmus aufgedeckt habe [img]http://www.fb18.de/gfx/25.gif[/img]

@Fok: Dann war ich ja gar nicht so weit daneben ;-)

erstmal vielen dank für die antworten. jetzt leuchtet mir das ein, vielleicht hab ich gestern einfach etwas zu viel pnl am stück gemacht, da lässt die konzentration irgendwann stark nach…

eine frage hätte ich aber doch noch zum lemma 8.51 (folie 55 8_4).
sei f=1, n=5, n/2 + f = 3,5, p0 ist fehlerhaft, p1 ist king.
p0(-), p1(b), p2(a), p3(a), p4(a)
p0(-), p1(bbaaa), p2(bbaaa), p3(abaaa), p4(bbaaa)
p0(-), p1(b), p2(b), p3(a), p4(b)

p2 und p4 haben keine mehrheit und befragen deshalb den king und legen sich somit auf b fest. bei p3 gibt es aber eine mehrheit für a. folglich haben nicht alle zuverlässigen prozessoren denselben wert. ich sehe keinen grund,warum ein solches szenario nicht möglich wäre. aber das würde dem lemma 8.51 widersprechen und ich glaube nicht, dass ich einen unentdeckten fehler in dem algorithmus aufgedeckt habe [img]http://www.fb18.de/gfx/25.gif[/img]

Hm, wenn p1 der King ist und er als Werte (bbaaa) hat, dann entscheidet er sich doch wohl aber für a und teilt den anderen a mit, oder nicht?

aber für a gibt es doch keine mehrheit (a = 3 < 3,5), also richtet sich der king nach seiner ersten meinung, was b war. oder lieg ich da falsch?

Ich denke der King hat schon in Zeile 5 sein maj verschickt, was aber aus Zeile 3 a sein sollte, oder liege ich nun falsch? [img]http://www.fb18.de/gfx/3.gif[/img]

aber für a gibt es doch keine mehrheit (a = 3 < 3,5), also richtet sich der king nach seiner ersten meinung, was b war. oder lieg ich da falsch?

Ja, liegst Du ;)

Ich denke der King hat schon in Zeile 5 sein maj verschickt, was aber aus Zeile 3 a sein sollte, oder liege ich nun falsch? [img]http://www.fb18.de/gfx/3.gif[/img]

Nein, Du hast Recht ;)

Also: Es wird ja im ersten Schritt immer lokal bei jedem Prozessor bestimmt, was er als Mehrheit aller anderen und seiner eigenen Meinung bekommen hat.
Hier ist es egal wie groß die Mehrheit ist, Hauptsache eine Mehrheit.
p1 sieht also (aaabb) und sagt Präf := a Mult := 3

Dann wird p1 etwas später zum King und schickt seine Meinung a.
p3 hat mult == 4, was damit größer als 3,5 ist und hört nicht auf den King, alle anderen nehmen den Wert vom King an. p3 hat sich aber selber (aaaab) für a entschieden. Also nehmen alle a.

ups, das hab ich wohl übersehen. dann stimmt ja alles mit dem lemma. danke