FIFO Multicast R und S

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

FIFO Multicast R und S

Beitrag von Wambolo » 2. Dez 2009 20:59

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?

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: FIFO Multicast R und S

Beitrag von MisterD123 » 3. Dez 2009 00:17

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 ;)

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

Re: FIFO Multicast R und S

Beitrag von Tigger » 3. Dez 2009 08:17

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.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: FIFO Multicast R und S

Beitrag von MisterD123 » 3. Dez 2009 11:46

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.

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: FIFO Multicast R und S

Beitrag von Wambolo » 3. Dez 2009 12:37

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 ;)

Immanuel Schweizer
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 12. Okt 2009 08:47

Re: FIFO Multicast R und S

Beitrag von Immanuel Schweizer » 3. Dez 2009 15:07

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.

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: FIFO Multicast R und S

Beitrag von Wambolo » 3. Dez 2009 18:11

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?

Benutzeravatar
dEeP-fRiEd
Kernelcompilierer
Kernelcompilierer
Beiträge: 432
Registriert: 19. Okt 2005 00:58
Wohnort: Darmstadt
Kontaktdaten:

Re: FIFO Multicast R und S

Beitrag von dEeP-fRiEd » 10. Dez 2009 22:18

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?
NOSCE TE IPSUM
visit: http://www.flicknetwork.net.tc

Benutzeravatar
Shoggo
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 26. Okt 2005 19:23
Wohnort: Darmstadt

Re: FIFO Multicast R und S

Beitrag von Shoggo » 11. Dez 2009 10:48

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.
Shinson Hapkido - Bewegung für das Leben
Shinson Hapkido Trailer

Benutzeravatar
dEeP-fRiEd
Kernelcompilierer
Kernelcompilierer
Beiträge: 432
Registriert: 19. Okt 2005 00:58
Wohnort: Darmstadt
Kontaktdaten:

Re: FIFO Multicast R und S

Beitrag von dEeP-fRiEd » 11. Dez 2009 11:30

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.
NOSCE TE IPSUM
visit: http://www.flicknetwork.net.tc

Immanuel Schweizer
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 12. Okt 2009 08:47

Re: FIFO Multicast R und S

Beitrag von Immanuel Schweizer » 11. Dez 2009 12:06

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.

Benutzeravatar
dEeP-fRiEd
Kernelcompilierer
Kernelcompilierer
Beiträge: 432
Registriert: 19. Okt 2005 00:58
Wohnort: Darmstadt
Kontaktdaten:

Re: FIFO Multicast R und S

Beitrag von dEeP-fRiEd » 11. Dez 2009 16:22

Ah, ja das macht Sinn. Danke für die Klarstellung :)
NOSCE TE IPSUM
visit: http://www.flicknetwork.net.tc

Antworten

Zurück zu „Archiv“