+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Diplom Informatik ( /forumdisplay.php?fid=114 )
+--- Forum: Theoretische Informatik (HS) ( /forumdisplay.php?fid=75 )
+--- Thema: PNL: to broadcast algorithm (Algorithmus 6.2) ( /showthread.php?tid=4839 )
PNL: to broadcast algorithm (Algorithmus 6.2) - Elnino - 20.02.2005 13:34
Hallo Leute, kann mir mal jemand diesen Algorithmus erklären? So richtig Schritt für Schritt? Irgendwie komme ich damit nicht klar?!
Die Nachrichten werden doch mit einem Zeitstempel und der Sender-ID verschickt, was davon ist den die ID? das "i"? Und dann wird der Zeitstempel inkrementiert? Falls die Zeitstempel gleich sind, hat doch die Nachricht Vorrang, deren Sender-Id kleiner ist, richtig?
Wäre für eine schnelle Hilfe sehr dankbar!
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Elnino - 20.02.2005 15:34
So, ich versuch mich mal selbst:
Zeilen 1-4) Wenn eine Nachricht m mit verschickt werden soll, wir der eigene Zeitstempel inkrementiert, und anschließend mit der Sender-ID an die Nachricht hinzugefügt (add<m,ts(i),i> ?!
Dann wird die Nachricht mit qos=ssf versandt?
Zeilen 5-10: wenn nun ein Prozessor j die Nachricht empfängt, wird der eigene Zeitstempel aktualisiert (ts(j):=T), der neue Zeitstempel nun mit der Sender-ID j an die Nachricht hinzugefügt und dann= zeilen 8-9 sind mir nicht ganz klar?
Was bedeutet ts-up,T in Zeile 10?
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Marrow - 20.02.2005 15:47
Zitat:
Was bedeutet ts-up,T in Zeile 10?
Timestamp-Update, der Prozessor informiert die anderen darüber, dass er seinen Timestamp aktualisiert hat.
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Elnino - 20.02.2005 15:55
Aha, jetzt rattert's glaub ich! Also wenn der neue T größer ist als die Zeitstempel der anderen Proz. (Zeile 8 und 9), dann verschickt er diese ts-up mit dem aktuellen timestamp an alle, damit diese ihre Zeitstempel auch auf diesen T setzen?
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Anonymer User - 20.02.2005 18:02
kann uns jemand auch mal den co- Algorithmus Schritt für Schritt natürlichsprachlich erlklären? Und worin der Unterschied zwischen co und to liegt?
Danke
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Elnino - 20.02.2005 20:12
Ich glaub bei "to" ist es egal, in welcher Reihenfolge die Nachrichten versendet werden, wichtig ist nur, das sie für alle Prozessoren in der selben Reihenfolge ankommen! Z.B. auf s.205 muss für beide Proz. die Reihenfolge b,a sein
Bei "co" ist es durchaus möglich, dass sie in einer anderen Reihenfolge ankommen, da es hier nämlich davon abhängt, wie die Prozessoren die Nachrichten versenden. (hier übernehme ich keine Haftung!!!)
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - asdf - 20.02.2005 23:05
Zitat:
Zeilen 1-4) Wenn eine Nachricht m mit verschickt werden soll, wir der eigene Zeitstempel inkrementiert, und anschließend mit der Sender-ID an die Nachricht hinzugefügt (add<m,ts(i),i> ?!
Dann wird die Nachricht mit qos=ssf versandt?
Dann wird die Nachricht mit qos=ssf versandt?
Ich sehe das so:
Prozessor i moechte Nachricht m versenden; er erhöht seinen eigenen
Zeitstempel um 1; steckt dann <m, ts[ i ], i> in seinen lokalen Puffer
(er empfängt seine eigene Nachricht also noch nicht!); er veschickt
per broadcast seine Nachricht mit seinem Zeitstempel an die anderen
Prozessoren.
Zitat:
Zeilen 5-10: wenn nun ein Prozessor j die Nachricht empfängt, wird der eigene Zeitstempel aktualisiert (ts(j):=T),
Nein. Jeder Prozessor verfügt über ein eigenes ``Array'' an
Zeitstempel (dieses ts[]), wo er die ``angeblich'' lokale Zeit
der anderen Prozessoren speichert.
Ein Prozessor i updatet also in Zeile 6 den Zeitstempel von j,
von dem er also die Nachricht m erhalten hat.
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Anonymer User - 21.02.2005 08:43
Klingt nicht schlecht, aber dann verstehe ich den Rest nicht mehr..hmm..dabei habe ich heute Prüfung...
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Anonymer User - 21.02.2005 11:32
@anonymous Berichte doch bitte über deine Prüfung!!!
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Elnino - 21.02.2005 18:11
Yup, das war ich, war nur nicht eingeloggt! Also hatte mir das etwas anders vorgestellt...hatte alle Kapitel bis auf das letzte gut vorbereitet...und was kam dran?! Ich nenn nur stichwortartig was dran kam, soweit ich mich noch dran erinnern kann. Also:
P.S. Atmosphäre wie immer bei Herrn Valk richtig gut!
Little's Formel, Voraussetzung, wie im Operationalen Modell und wie im stochastischen? Zusammenhänge usw.? Und einige kleine Fragen dazu.
Alternierbitprotokoll: was ist das, Skizze, wie funktioniert das ganze, wie in PA spezifiziert, Prozessgraphen aufmalen, alles genau erklären wie wir auf die Spezifikation gekommen sind (uff...das war mir zu viel)
Wie funktioniert Verifikation hier? Allg. Unterschied Verifikation und Modelchecking?
BPA Kalkül, Bisimulation, wie beweist man Äquivalenzen usw.?
aX+B Prozessgraph + Ableitungsregel, wie Paralleoperator in PA? Ableitungsregel in PA und Kalkül dazu
Welche Klassen von Sys.eigenschaften bei Petrinetzen (mar.- und lebendigkeitsinvarianzeig.) welche gibt es dort genau? alle formal aufschreiben und definieren, erklären,
was beschränktheit, und k-beschränktheit, sind die anders? wieso?
konsens, was ist das, wie funktioniert Ausfallkonsens, welche Voraussetzngen, was ist der Unterschied zu byz. Konsens, welche Algorithmen gab es da, wo unterschiede zwischen exp. Konsens Algo. und poly.Konsens Algo,expo.Konsens erläutern, so richtig wie der Verteilungsbaum aufgebaut wird usw.
Re: PNL: to broadcast algorithm (Algorithmus 6.2) - Elnino - 21.02.2005 18:19
WEITER:
dann gab's probalistische Algos, was ist hier so besonders, welche Voraussetzungen bei prob.Konsensalgo., wie funktioniert der?
ähm...welche Komplexitäten und was ist an dem anderen so polynomiell?
ach ja, was ist PA, wieso hat man Bisim. und BPA-kalkül?
da gab's noch viele zwischenfragen, aber so grob müsste es stimmen..was die Gesamtübersicht angeht.
Hauptsächlich ging es um ALLES bei PA, bis ins kleinste Detail, ausführlich Kapitel 9, dann alles was mit Konsens zu tun hat (Kapitel 7 und 8),bisschen was zu Petrinetzen und Modellchecking und Verifikation
Prozesse, broadcast, statecharts --> nada, nix davon...schade...meine Stärken waren Kapitel 2-8
dann sollte man noch einige von diesen Algorithmen erklären, hab das Skript aber gerade nicht zur Hand, daher weiß ich nicht mehr welche es waren...
Hab bestanden, wären die Gebiete jedoch anders gewählt worden, so wäre meine Note viel besser. Viel Glück allen!