Seite 1 von 1

FIFO Multicast R und S

Verfasst: 2. Dez 2009 20:59
von Wambolo
Jeder Prozess p hat Attribute S_p_g und R_q_g.

Ich interpretiere das jetzt mal so, dass jeder Prozess so viele S_p_g, so dass er jeder Gruppe genau ein S zuordnen kann.
Genauso hat jeder Prozess genau so viele R_q_g [wie er Prozesse q kennt] * [Anzahl der Gruppen in denen er Mitglied ist]

Bsp ein Prozess p2 ist Mitglied in zwei Gruppen(g1 und g2) und bekommt Nachrichtem vom Prozess px, dann hat p2
die Attribute R_px_g1 und R_px_g2, sehe ich das richtig?

Re: FIFO Multicast R und S

Verfasst: 3. Dez 2009 00:17
von MisterD123
Hier stimmt einfach die Notation auf den Folien nicht. Das R_q_g ist copy&paste vom reliable multicast, welcher in den nachrichten die Gruppe mitsendet. Schaust du dir den B-Multicast vom Fifo an dürfte dir auffallen, dass q:B-Multicast(g, m) zu ganz vielen q:reliable-send(r,m) (für alle empfänger r aus der gruppe g) wird, jeder r empfängt also deliver(m) von q, aber _ohne_ die Information, an welche Gruppe der Multicast nun adressiert war - daher sollte R_q_g eigentlich eher nur R_q heißen, damit die Terminologie stimmt. Folglich hätte jeder Prozess p auch nur [anzahl sender] viele R_q-Zähler zusätzlich zu seinen [anzahl gruppen] vielen S_p_q-Zählern.

angaben ohne gewähr, ich bin nicht teil des veranstalter-teams - so haben wir das in meiner gruppe interpretiert und zur Lösung der aufgabe verwendet. Warum nun der Sende-Zähler für Prozess p durch S_p die ID des Prozesses, der ihn speichert, in seinem Namen trägt, und die R-Zähler nur die ID der Sender, nicht aber die ID des speichernden Prozesses ist ein Rätsel welches vermutlich niemals aufgelöst werden wird, du wirst dich mit einer geringfügig inkonsitenten nomenklatur abfinden müssen ;)

Re: FIFO Multicast R und S

Verfasst: 3. Dez 2009 08:17
von Tigger
MisterD123 hat geschrieben:aber _ohne_ die Information, an welche Gruppe der Multicast nun adressiert war
Habe das am Montag schonmal in der Sprechstunde gefragt. Demnach weiß der Empfänger sehr wohl an welche Gruppe der Multicast gerichtet war. Es ist auch so, das das jeder Client separate R_qx und S_qx für jede Gruppe, in der er Mitglied ist, verwaltet. Folglich muss er ja wissen, aus welcher Gruppe der Multicast kam.

Re: FIFO Multicast R und S

Verfasst: 3. Dez 2009 11:46
von MisterD123
bei reliable ip-multicast ja - da steht schließlich die gruppe als adressat im paket drin, bei (fifo- bzw.) b-multicast nein - da wird immer nur eine einnzelne nachricht via tcp an vom sender an jeden empfänger verschickt, und da steht die gruppen-ID nicht drin.
warum geht b-multicast dann nicht bei überlappenden gruppen? die zähler sind die einzigen Datenstrukturen, die der algo zu bieten hat - ich wüsste keine andere stelle, an der der algorithmus im beschriebenen Fall sonst kaputt gehen sollte.

Ich würde also soweit gehen und behaupten, dass ihr in kombination mit diesen schrecklichen notationen auf den folien einfach erfolgreich den Sprechstunden-Tutor verwirrt habt, so dass er mist erzählt hat ;D ich hab grade das problem mal bei google reingeschmissen, nur auf englisch, und siehe da, die computer science abteilung in illinois hat exakt die selbe aufgabe gestellt und die lösung die dabei stand passt genau zu dem problem wie ich es beschrieben habe, nämlich dass die gruppen-ID mitgesendet werden muss damit der Fehler verhindert werden kann.

Re: FIFO Multicast R und S

Verfasst: 3. Dez 2009 12:37
von Wambolo
schade, dass die Definitionen auf den Folien nicht immer ausreichend sind.

Aber ich finde sowohl für Deine als auch für Tiggers und meine Interpretation Fehlerpotential.

Jetzt muss ich mir nur noch überlegen welche Variante ich abgebe.

Im Coulouris wird auch die Notation aus der Vorlesung verwendet und dort sind bei R explizit Gruppen angegeben ich tendiere daher zu meiner
ursprünglichen Interpretation, aber Du verunsicherst mich leider ;)

Re: FIFO Multicast R und S

Verfasst: 3. Dez 2009 15:07
von Immanuel Schweizer
Naja :) Also ich würde mich immer an den Folien orientieren. Und natürlich gibt es ein S pro Gruppe und mehrere Rs wenn ein Prozess q in mehreren Gruppen multicastet.
Steht aber auch so auf den Folien und wie Ihr darauf kommt, dass beim B-Multicast die Gruppe nicht bekannt ist beim Reliable aber schon, obwohl auch der über den B-Multicast gemacht werden kann, erschließt sich mir nicht.
Zu der Nomenklatur, auch diese ist nicht inkonsistent, sondern es macht natürlich Sinn bei S den Prozess, der S ausgibt zu schreiben, denn dieser wird ja in die Welt hinausgesendet und so kann man bei der Beschreibung eines abstrakten Systems zwischen Sp1,g und Sp2,g unterscheiden. Bei den Rs ist dies nicht nötig, da sie ja für jeden Prozess lokal sind (nicht gesendet werde).

Lange Rede kurzer Sinn. Die Folien sind richtig und damit auch Deine, Wambolo, erste Interpretation.

Re: FIFO Multicast R und S

Verfasst: 3. Dez 2009 18:11
von Wambolo
Ich habe mir gerade nochmal die Musterlösung angeschaut und genau so hatte ich mir das auch gedacht, aber jetzt verstehe ich auf einmal nicht mehr wo das Problem liegt. Und zwar gilt doch die FIFO Eigenschaft, laut Definition in der VL, immer nur für eine Gruppe. (K3 Folie 47) Und da die Nachrichten in der MuLö ja für zwei verschiedene Gruppen bestimmt sind spielt doch die Reihenfolge in diesem Fall keine Rolle.

Oder gibt es im Rahmen der Vorlesung eine weitere Definition die ich übersehen habe, bzw. interpretiere ich die Definition auf Folie 47 falsch?

Re: FIFO Multicast R und S

Verfasst: 10. Dez 2009 22:18
von dEeP-fRiEd
Wambolo hat geschrieben:Ich habe mir gerade nochmal die Musterlösung angeschaut und genau so hatte ich mir das auch gedacht, aber jetzt verstehe ich auf einmal nicht mehr wo das Problem liegt. Und zwar gilt doch die FIFO Eigenschaft, laut Definition in der VL, immer nur für eine Gruppe. (K3 Folie 47) Und da die Nachrichten in der MuLö ja für zwei verschiedene Gruppen bestimmt sind spielt doch die Reihenfolge in diesem Fall keine Rolle.

Oder gibt es im Rahmen der Vorlesung eine weitere Definition die ich übersehen habe, bzw. interpretiere ich die Definition auf Folie 47 falsch?
Bin grade am Lernen für die Klausur und dabei jetzt auf genannter Folie 47 hängen geblieben. Die dortige Definition des FIFO Multicasts würde ich auch so interpretieren, dass sie nur innerhalb einer Gruppe gilt. (Was natürlich jetzt irgendwie ein Widerspruch zur Übung ist!) Also verstehen wir da was falsch?

Re: FIFO Multicast R und S

Verfasst: 11. Dez 2009 10:48
von Shoggo
Servus!

Wo genau steht denn da was von Gruppenzugehörigkeit im FIFO?
Ich fasse es so auf das es für jeden Process gilt. Also unabhängig der Gruppenzugehörigkeit. Daher ja auch das Problem, dass ein Prozess \(P_i\) die Nachrichten in korrekter Reihenfolge vom Sender empfangen muss. Egal über welche Gruppe er ihn erhalten hat, da der Prozess die Gruppenabhängigkeit ignoriert.

Re: FIFO Multicast R und S

Verfasst: 11. Dez 2009 11:30
von dEeP-fRiEd
Shoggo hat geschrieben:Servus!

Wo genau steht denn da was von Gruppenzugehörigkeit im FIFO?
Ich fasse es so auf das es für jeden Process gilt. Also unabhängig der Gruppenzugehörigkeit. Daher ja auch das Problem, dass ein Prozess \(P_i\) die Nachrichten in korrekter Reihenfolge vom Sender empfangen muss. Egal über welche Gruppe er ihn erhalten hat, da der Prozess die Gruppenabhängigkeit ignoriert.
Hi,

da steht ja
if a correct process P:
multicast(g, m);
multicast(g, m’);
...
Also die Vorbedingung ist, dass zwei Nachrichten vom gleichen Sender an die gleiche Gruppe g gesendet werden! Über Nachrichten aus verschiedenen Gruppen wird also keine Aussage getroffen.

Re: FIFO Multicast R und S

Verfasst: 11. Dez 2009 12:06
von Immanuel Schweizer
if a correct process P:
multicast(g, m);
multicast(g, m’);
Der FIFO Algorithmus garantiert ja auch, dass Nachrichten die von einem Sender an die gleiche Gruppe gesendet werden, in der richtigen Reihenfolge ankommen.
Die Aufgabe war ja aber, zu überlegen, warum FIFO verletzt wird, wenn wir von überlappendend Gruppen ausgehen.
Was auf den Vorlesungsfolien steht, ist also völlig korrekt, bei einer Gruppe oder innerhalb einer Gruppe funktioniert FIFO immer, die Aufgabe war sich zu überlegen, warum es bei überlappenden Gruppen nicht mehr garantiert werden kann.

Re: FIFO Multicast R und S

Verfasst: 11. Dez 2009 16:22
von dEeP-fRiEd
Ah, ja das macht Sinn. Danke für die Klarstellung :)