da sind ja noch ein paar ;)
aber keine Angst, die meisten sind recht einfach und kurz zu beantworten wenn man es denn weiss,

ich danke schon mal,
werd um 18.00 wieder reinschauen, danach ist dann egal ;)


S. 54

broadcast nur in orthogonalen Komponenten
-> nicht in tieferen und höhereren Ebenen?

was ist wenn dort Übergänge mit der gleichen Ereignis a verknüpft sind,
für die eine Aktion a ausgelöst wurde
-> keine Reaktion? also lokale Namensräume?

S. 56

kann man aus dem Heimtrainer-Beispiel irgendetwas gewinnen?

S. 97

muss man Invarianten ausrechnen können/ was genau dazu wissen?

S.100

wo steht eigentlich in der MOB-Beschreibung welche Variable an welcher Kante steht?
bei gefärbten Netzen gabs wenigstens Kantengewichtung, hier nicht..

muss man zum MOB irgendwas besonderes wissen, ausser dass sie Objekte erzeugen und
dass das Erreichbarkeitsproblem nicht entscheidbar ist?
-> irgendwas für Referenznetze wichtig?

-> gibts zu letzterem auch nen plausiblen Grund den man erzählen kann
(sowohl für Zählerautomaten als auch gefärbte Netze)?

-> ist das Erreichbarkeitsproblem bei 3-Zählerautomaten entscheidbar?
wenn ja wieso?


S. 108

an einer Transition this:tuwas und an einer anderen :tuwas

kann dann nur die erste von alleine schalten und die andere nur reagieren
oder auch selber schalten wenn es mit der Aktivierung passt (Auswirkung auf die andere?)/
oder müssen beide aktiviert sein?

S. 111

zyklische Referenz, da muss wohl die Referenz als Parameter übergeben werden?
dann kann man wohl auch 'this' übergeben?

S. 118

kann man aus dem Garbage-Can-Modell etwas wichtiges mitnehmen?

S. 139

da wird öfter RS(S) verwendet, das ist wohl das vorher definierte R(S)?
welches von beiden soll man denn verwenden?

S. 149

Algorithmus 5.4 2.2.2, da wird einmal < und einmal <!= zum Vergleich der Markierungen verwendet,
ist beides das selbe?

S. 155
Kripke-Struktur in logischer Darstellung:
wofür ist das L(s) dort gut?
gilt nicht immer nur L((1,1)) = {x=1, y=1}, also praktisch nur s e L(s) oder noch mehr?
-> was ist die Aussage?



S. 163

Ef ist Zustandsformel -> auch Pfadformel nach Regel 4?

M,pi|=a heißt a gilt in Pfad pi? (oder Semantikregel 7 auf nächster Seite?)
M,pi|=Ga heißt a gilt auf gesamten Pfad,

Unterschied zum vorherigen?

funktioniert das immer so?
Beispiel:
Ea als Pfadformel aufgefasst,
für M,pi|=E… gibt es keine Semantikregel,
-> muss man dann die Regel 7 verwenden, da keine andere da?

S.164 + 165

AXf = -EX(-f)

aber

E[fRq] == -A[-fU-g]

wieso der Unterschied im Gleichheitszeichen?

Ich bin eigentlich noch nicht so weit, aber ich tue mein Bestes!

S. 54

broadcast nur in orthogonalen Komponenten
-> nicht in tieferen und höhereren Ebenen?

Doch, solange da eine Orthogonalität (=Nebenläufigkeit) vorliegt; wenn eine Aktion ausgelöst wird, gilt sie für den gesamten Graphen; was dann genau geschieht, hängt ja davon ab, welche(r) Zusta(e)nd(e) gerade aktiv sind.

was ist wenn dort Übergänge mit der gleichen Ereignis a verknüpft sind,
für die eine Aktion a ausgelöst wurde
-> keine Reaktion? also lokale Namensräume?

Ich weiß nicht, ob ich Dich richtig verstanden hab, aber IMO ist der Namensraum global (wie sollte man sonst global das drücken eines bestimmten Knopfes darstellen?) und Dein a/a würde immer wieder das Ereignis a auslösen (was aber auch nicht völlig sinnfrei wäre, wenn man sich eine ähnliche Struktur wie z.B. auf S.72 in regular anschaut, die aber von selber durchschaltet).

S. 56

kann man aus dem Heimtrainer-Beispiel irgendetwas gewinnen?

Ein allgemeines Verständnis für einen angewandten Harel-Graphen ?

S. 97

muss man Invarianten ausrechnen können/ was genau dazu wissen?

Wie hast Du denn die F4-Prüfung geschafft ? <eg>

IMO müßten ein ungefähres Wissen, was das ist, und das man es berechnen kann, reichen. Sagen die Prüfungsprotokolle nichts dazu ?

S.100

wo steht eigentlich in der MOB-Beschreibung welche Variable an welcher Kante steht?

Zitat Def. 4.21: "[Sei] z: F -> V eine Variablenzuordnungsfunktion".

bei gefärbten Netzen gabs wenigstens Kantengewichtung, hier nicht..

Ich glaube, das wird durch die Variablenbindungsfunktion miterledigt, also mit Abb. 4.24 könnte v1 an 2'a gebunden werden. Allerdings weiß ich nicht, ob das mit dom(f)=V paßt.

muss man zum MOB irgendwas besonderes wissen, ausser dass sie Objekte erzeugen und
dass das Erreichbarkeitsproblem nicht entscheidbar ist?
-> irgendwas für Referenznetze wichtig?

-> gibts zu letzterem auch nen plausiblen Grund den man erzählen kann
(sowohl für Zählerautomaten als auch gefärbte Netze)?

-> ist das Erreichbarkeitsproblem bei 3-Zählerautomaten entscheidbar?
wenn ja wieso?

Leider keine Ahnung!
EDIT: Lt. S.98 sind 2-Zählerautomaten gleichmächtig zu Turing-Maschinen, und bei denen wurde bereits bewiesen, daß das Erreichbarkeitsproblem unentscheidbar ist. Außerdem steht da, daß man Zählerautomaten relativ einfach mit gefärbten Netzen simulieren kann. 3-Zälerautomaten sind natürlich noch komplizierter…

S. 108

an einer Transition this:tuwas und an einer anderen :tuwas

kann dann nur die erste von alleine schalten und die andere nur reagieren
oder auch selber schalten wenn es mit der Aktivierung passt (Auswirkung auf die andere?)/
oder müssen beide aktiviert sein?

Ich finde im Moment nichts, was gegen ein alleiniges Schalten von :tuwas spricht. Bedenke aber, daß alle Variablen im gesamten Netz die gleiche Bindung haben müssen, dadurch werden die beiden Transitionen wohl immer etwas abhängig voneinander sein.

S. 111

zyklische Referenz, da muss wohl die Referenz als Parameter übergeben werden?
dann kann man wohl auch 'this' übergeben?

Ich glaube hier ist nur gemeint, was da auch steht, als Person ruft Tra. in Konto auf, welche wiederrum eine Tra. in Person aufruft (usw.). Als Parameter übergibts Du doch normalerweise keine Referenz, sondern einen Wert (Bsp.: acc:withdraw(1) wird in acc withdraw mit m=1 aufgerufen). Ergo kannst Du kein this übergeben.

Oder ich habe etwas übersehen…

Zu langes Posting, Pah!

S. 118

kann man aus dem Garbage-Can-Modell etwas wichtiges mitnehmen?

k.A.

S. 139

da wird öfter RS(S) verwendet, das ist wohl das vorher definierte R(S)?
welches von beiden soll man denn verwenden?

R(S) ist die Erreichbarkeitsmenge (Def.5.3), RS(S) der Erreichbarkeitsgraph eines unbeschränkten Netzsystems S (S.139, mitte). Ich vermute, daß RG(S) und RS(S) synonym benutzt werden.

S. 149

Algorithmus 5.4 2.2.2, da wird einmal < und einmal <!= zum Vergleich der Markierungen verwendet,
ist beides das selbe?

vermutlich

S. 155
Kripke-Struktur in logischer Darstellung:
wofür ist das L(s) dort gut?
gilt nicht immer nur L((1,1)) = {x=1, y=1}, also praktisch nur s e L(s) oder noch mehr?
-> was ist die Aussage?

k.A.

S. 163

Ef ist Zustandsformel -> auch Pfadformel nach Regel 4?

Ja, daß heißt ja als Zustandsformel "Es gibt von diesem Zustand einen Pfad, in dem f gilt" und als Pfadformel "Es gibt in diesem Pfad einen Zustand, von dem es einen Pfad gibt, von dem f gilt".

Hinweis: f in Regel 3 != f in Regel 4

M,pi|=a heißt a gilt in Pfad pi? (oder Semantikregel 7 auf nächster Seite?)
M,pi|=Ga heißt a gilt auf gesamten Pfad,

Unterschied zum vorherigen?

pi=Folge von Zuständen die durchlaufen werden.

M,pi|=a <=> a gilt im ersten Zustand von pi, über pi_hoch_i wird nichts ausgesagt.

M,pi|=Ga <=> a gilt auf gesamten Pfad == a gilt in jedem Zustand, der durchlaufen wird

funktioniert das immer so?
Beispiel:
Ea als Pfadformel aufgefasst,
für M,pi|=E… gibt es keine Semantikregel,
-> muss man dann die Regel 7 verwenden, da keine andere da?

Dann gilt doch Regel 1: p ist eine Pfadformel (weiß ich auch nur, weil ich es mir in der Vorlesung daneben geschreiben habe), dafür setzt Du dann halt Dein Ea ein. Mit Regel 7 würdest Du Ea als Zustandsformel betrachten.

S.164 + 165

AXf = -EX(-f)

aber

E[fRq] == -A[-fU-g]

wieso der Unterschied im Gleichheitszeichen?

Leider k.A.

Hoffentlich findet sich noch jemand, der die Lücken füllt.

Viel Erfolg!

EDIT: Huchu, Veteran geworden durch ein sinnvolles Posting![img]http://www.fb18.de/gfx/22.gif[/img]

S. 149

Algorithmus 5.4 2.2.2, da wird einmal < und einmal <!= zum Vergleich der Markierungen verwendet,
ist beides das selbe?

vermutlich

Es ist nicht das gleiche (meine ich). Denn < bedeutet in ALLEN Komponenten des Vektors kleiner, <!= bedeutet nur: In min. einer Komp. kleiner, alle anderen gleich.

also

[img]http://mokrates.de/cgi-bin/texstring?%5Cleft(%5Cbegin%7Barray%7D%7Bc%7D4%5C%5C4%5C%5C4%5Cend%7Barray%7D%5Cright)%20%3C%5Cnot=%20%5Cleft(%5Cbegin%7Barray%7D%7Bc%7D6%5C%5C4%5C%5C5%5Cend%7Barray%7D%5Cright)%20%5Ctextnormal%7Baber%20nicht%20%7D%3C[/img]

Es ist nicht das gleiche (meine ich). Denn < bedeutet in ALLEN Komponenten des Vektors kleiner, <!= bedeutet nur: In min. einer Komp. kleiner, alle anderen gleich.

Hättest Du "<=" geschrieben, würde es mir logischer vorkommen (was nicht heißt, daß ich weiß, ob das jetzt richtig oder falsch ist).

Mal eine Frage meinerseits:
Warum braucht man F-Erhaltung und A-Erhaltung, um einen Netzmophismus zu definieren, würde A-Erhaltung nicht alleine reichen ? (S.79f., Def. 4.5)

was ist wenn dort Übergänge mit der gleichen Ereignis a verknüpft sind,
für die eine Aktion a ausgelöst wurde
-> keine Reaktion? also lokale Namensräume?

Ich weiß nicht, ob ich Dich richtig verstanden hab, aber IMO ist der Namensraum global (wie sollte man sonst global das drücken eines bestimmten Knopfes darstellen?) und Dein a/a würde immer wieder das Ereignis a auslösen (was aber auch nicht völlig sinnfrei wäre, wenn man sich eine ähnliche Struktur wie z.B. auf S.72 in regular anschaut, die aber von selber durchschaltet).

ich meinte:was ist wenn a an einer Kante in höherer oder tieferer Ebene steht
und woanders ein a ausgelöst wird,

globale Namensräume also.., ich nehm das mal als Meinung hin ;)

wo steht eigentlich in der MOB-Beschreibung welche Variable an welcher Kante steht?

Zitat Def. 4.21: "[Sei] z: F -> V eine Variablenzuordnungsfunktion".

wow, das steht da wirklich?, muss nochmal nachschauen

zyklische Referenz, da muss wohl die Referenz als Parameter übergeben werden?
dann kann man wohl auch 'this' übergeben?

Ich glaube hier ist nur gemeint, was da auch steht, als Person ruft Tra. in Konto auf, welche wiederrum eine Tra. in Person aufruft (usw.).
Als Parameter übergibts Du doch normalerweise keine Referenz, sondern einen Wert (Bsp.: acc:withdraw(1) wird in acc withdraw mit m=1 aufgerufen). Ergo kannst Du kein this übergeben.

Person ruft Konto auf -> Person könnte Konto erzeugt haben,
Konto ruft Person auf -> woher kennt Person Konto?,

na wird schon so sein mit Referenzenübergabe (nur einmal zur Bekanntmachung),
nur kein Beispiel im Skript oder übersehen ;)

Beispiel:
Ea als Pfadformel aufgefasst,
für M,pi|=E… gibt es keine Semantikregel,
-> muss man dann die Regel 7 verwenden, da keine andere da?

Dann gilt doch Regel 1: p ist eine Pfadformel (weiß ich auch nur, weil ich es mir in der Vorlesung daneben geschreiben habe), dafür setzt Du dann halt Dein Ea ein. Mit Regel 7 würdest Du Ea als Zustandsformel betrachten.

Semantikregel 1 gilt nur für elementare Formeln
die beiden auf der Seite davor sagen nicht viel aus..

es gibt eben keine Pfadregel für Pfadformel E…!,
nur Regel 7,

ach ohne Skript ist jetzt doof ;)

Denn < bedeutet in ALLEN Komponenten des Vektors kleiner, <!= bedeutet nur: In min. einer Komp. kleiner, alle anderen gleich.

ich glaube das macht da in dem Algorithmus keinen Sinn,
und meine auch das wäre auf der Seite gegenüber definiert

aber schau ich auch noch mal nach, danke an beide ;)

Ich weiß nicht, ob ich Dich richtig verstanden hab, aber IMO ist der Namensraum global (wie sollte man sonst global das drücken eines bestimmten Knopfes darstellen?) und Dein a/a würde immer wieder das Ereignis a auslösen (was aber auch nicht völlig sinnfrei wäre, wenn man sich eine ähnliche Struktur wie z.B. auf S.72 in regular anschaut, die aber von selber durchschaltet).

ich meinte:was ist wenn a an einer Kante in höherer oder tieferer Ebene steht
und woanders ein a ausgelöst wird,

globale Namensräume also.., ich nehm das mal als Meinung hin ;)

Heißt das jetzt Zustimmung ??

Ich glaube hier ist nur gemeint, was da auch steht, als Person ruft Tra. in Konto auf, welche wiederrum eine Tra. in Person aufruft (usw.).
Als Parameter übergibts Du doch normalerweise keine Referenz, sondern einen Wert (Bsp.: acc:withdraw(1) wird in acc withdraw mit m=1 aufgerufen). Ergo kannst Du kein this übergeben.

Person ruft Konto auf -> Person könnte Konto erzeugt haben,
Konto ruft Person auf -> woher kennt Person Konto?,

na wird schon so sein mit Referenzenübergabe (nur einmal zur Bekanntmachung),
nur kein Beispiel im Skript oder übersehen ;)

jetzt, wo ich mir das nochmal durch den Kopf gehen lasse, höhrt sich Deine Variante ganz vernünftig an.

Dann gilt doch Regel 1: p ist eine Pfadformel (weiß ich auch nur, weil ich es mir in der Vorlesung daneben geschreiben habe), dafür setzt Du dann halt Dein Ea ein. Mit Regel 7 würdest Du Ea als Zustandsformel betrachten.

Semantikregel 1 gilt nur für elementare Formeln
die beiden auf der Seite davor sagen nicht viel aus..

es gibt eben keine Pfadregel für Pfadformel E…!,
nur Regel 7,

ach ohne Skript ist jetzt doof ;)

Okay, das mit den elementare hatte ich übersehen. dann gilt wohl regel 7.

ich glaube das macht da in dem Algorithmus keinen Sinn,
und meine auch das wäre auf der Seite gegenüber definiert

aber schau ich auch noch mal nach, danke an beide ;)

Bitte ! Hoffentlich bringt es was. [img]http://www.fb18.de/gfx/14.gif[/img]

Mal eine Frage meinerseits:
Warum braucht man F-Erhaltung und A-Erhaltung, um einen Netzmophismus zu definieren, würde A-Erhaltung nicht alleine reichen ? (S.79f., Def. 4.5)

A-erhaltung impliziert nur lokale Offen- und Abgeschlossenheit, nicht F-Erhaltung. Steht da in einem Satz kurz nach der Def… Irgendwie war mir das auch mal plausibel, müsste aber nochmal nachgucken.

S. 149

Algorithmus 5.4 2.2.2, da wird einmal < und einmal <!= zum Vergleich der Markierungen verwendet,
ist beides das selbe?

Es ist nicht das gleiche (meine ich). Denn < bedeutet in ALLEN Komponenten des Vektors kleiner, <!= bedeutet nur: In min. einer Komp. kleiner, alle anderen gleich.

also auf der Definition links ist < zwischen Vektoren wirklich wie <!= definiert, vielleicht Scheibfehler,
aber auch egal, denn im Algortihmus steht ja nicht m < m' sondern m[p] < m'[p]!,
jaja, ich bin blind ;)

globale Namensräume also.., ich nehm das mal als Meinung hin ;)

Heißt das jetzt Zustimmung ??

die Formulierung 'Aktionen, die Zustandsübergänge in orthogonalen Komponenten auslösen'
lässt mich weiter zweifeln,
im Skript findet sich ja auch kein Gegenbeweis,

wenn du jetzt sagen würdest: 'das hat H. Valk so gesagt in der Vorlesung mit global'
dannn kriegst auch Zustimmung, so ist es nur eine Meinung [img]http://www.fb18.de/gfx/24.gif[/img]

die Formulierung 'Aktionen, die Zustandsübergänge in orthogonalen Komponenten auslösen'
lässt mich weiter zweifeln,
im Skript findet sich ja auch kein Gegenbeweis,

wenn du jetzt sagen würdest: 'das hat H. Valk so gesagt in der Vorlesung mit global'
dannn kriegst auch Zustimmung, so ist es nur eine Meinung [img]http://www.fb18.de/gfx/24.gif[/img]

Wenns Dir nur um die Orthogonalität geht: Nur in einem solchen Fall sind mehrere Zustände aktiv.

Außerdem, was ergibt der 'broadcast' für einen Sinn, wenn jeder Zustand seinen lokalen Namensraum für die internen Aktionen hat. Wie willst Du dann das (globale) Drücken eines Knopfes (Bsp. Heimtrainer) darstellen ??

------------------------------------------------------------- | | | ----------------------- | ------------------------- | | | | | | | | | A | B | | | C | D | | | | | | | | | | | | | | |a | | | | | | | | | | | | |/ |b | | | a |b | | | | |b | | | | | | | | | | | | | | | | | | | | | | v | v | | | v | | | | | | E F | | G H | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ----------------------- | ------------------------- | | | ------------------------------------------------------------- aktueller Zustand: A,B,C,D

wenn jetzt Ereigneis a auftritt,
dann wird wohl A nach E wechseln, und C nach G,

ausserdem wird b ausgelöst,
wenn b nur in den Orthogonalen Komponenten bekannt ist, dann nur B -> F

wenn b global also überall anders bekannt ist, dann auch D -> H,
aber ist ja auch egal ;)

Siehs mal so: Innerhalb von AB wird b ausgelöst, also wird es auch in der orthogonalen Komponente CD ausgelöst.

ich kanns auch so malen ;)
----------------------- ------------------------- | | | | | A | B | | C | D | | | | | | | | | | |a | | | | | | | | | |/ |b | | | a |b | | |b | | | | | | | | | | | | | | | | | v | v | | v | | | | E F | | G H | | | | | | | | | | | | | | | | | | | | | ----------------------- ------------------------- ^ ^ ------- | | |Start|-------------------------------- -------
oder ist bei dir alles orthogonal? ;)

Nebenbei:
gibt es einen Unterschied zwischen
m(p) und m[p] (m=Makeriung,p=Platz) ????
Beide geben mir doch nur die Anzahl der Marken auf dem Platz zurück, oder????

Ja, aber bei m(p) siehst Du m als Funktion

m: P -> |N (bei ungefärbten Netzen)

und mit m[p] siehst Du m als Vektor, an dessen Stelle p steht, wieviele Marken in p liegen.

EDIT: Mist, slater's letztes Posting übersehen!

Für mich ist alles, was nebenläufig ist, orthogonal. Wenn du also gleichzeitig in Deinem AB und CD Zustand bist, dann sind die orthogonal.

Ähm, sagt mal, ich bin gerade über die Anmerkung auf S. 74 gestolpert, da steht:
"Eine Menge kann gleichzeitig offen und abgeschlossen sein, wie z.B. Y := P vereinigt T."

Das stimmt doch nicht?!?

offen ist definiert als: wenn der Rand Teilmenge/ gleich P ist
abgeschlossen: wenn der Rand Teilmenge/ gleich T ist.

wie soll nun der Rand Teilmenge von P sein, aber auch Elemente von T enthalten, wenn doch nach Netz-Definition (und intuition) P und T disjunkt sind.

Ist das n Fehler im Skript oder hab ich was offensichtliches übersehen?
-> kann eine Menge überhaupt offen und absgeschlossen sein? (also jetzt nicht im Analysis-Sinn, sondern Petrinetz mäßig)

[img]http://www.fb18.de/gfx/23.gif[/img]
die leere Menge ist Teilmenge jeder anderen!

sonst noch was?

sonst noch was?

Interpretier ich mal als Nachfrage:

Wenn es keine Elemente im Rand gibt, d.h. wenn zum Beispiel Y = P vereinigt T (in Worten: "gleich")ist, dann ist der Rand sowohl Teilmenge von T als auch von P. Genauso, falls Y leer ist, oder eben in den Fällen, wo das Netz in mehrere unabhängige Teile zerfällt und Y genau einen oder mehrere davon komplett ausmacht.

Ach Christoph.

Ja, das mit der leeren Menge ist mir bewußt. Ich meine außer in diesem (trivialen [img]http://www.fb18.de/gfx/23.gif[/img]) Fall sonst noch was?

es gibt nur den Fall Randmenge = leere Menge,

dafür kannst du unendlich viele verschiedene Netze bauen,
die Christoph wohl schon vollständig aufgezählt hat,
kann man natürlich alle als trivial ansehen, ja ;)

2 Fragen zu PA erstmal:

a) ist die Spezifikation E= { X= aXb } geschützt?
Im Skript steht ja, dass alle Gleichungen aus E die Form
X_i = a_1 * s_1(X_1..X_n) + … + a_k * s_k(…) + b_1 + … + b_l
haben müssen. Nur: was ist s_i? Ist das gleich t_i, also irgendein Term, der mit diesen Variablen erzeugt wird?

b) Kann ich sagen: <X_i|E> = (in Worten: "gleich") t_i(X_1,..,X_n) ? Ist also die Lösung von X_i in E gleich einem Prozessterm (der ja bei gesch. rek. Spez. eindeutig mod Bisimulation ist)?

[img]http://www.fb18.de/gfx/9.gif[/img] Ich hab irgendwie so gar keine Lust mehr auf PNL-Prüfung!

zu a):
ich glaube ja

zu b):
nein, es gilt ja <X_i|E> = t_i(<X_1|E>,..,<X_n|E>), d.h. <X_i|E> ist "abgewickelt" und ohne Variablen, bei Deiner Gleichung wären ja noch Variablen drin gewesen. Wobei andererseits bzgl. mod. Bi. das schon gleich ist (=> verhaltensgleichheit, das eine ist halt unendlich lange ausgeschrieben, das andre hat Variablen zur "Abkürzung").

Ich hab irgendwie so gar keine Lust mehr auf PNL-Prüfung!

freu Dich, danach bist Du frei!

danke erstmal! Wird sicher noch ne Handvoll mehr Fragen geben…

Ich hab irgendwie so gar keine Lust mehr auf PNL-Prüfung!

freu Dich, danach bist Du frei!

naja geht so… :-/

so: Fragen zu CTL:
Gilt: M,s |= p <=> M,s|= Ep <=> M,s|= GP? Weil sich alles immer nur auf den ersten/aktuellen Zustand bezieht?

CTL erlaubt ja keine Fairness. Was ist mit der Formel:
AGAF f
also für alle Pfade gilt immer, dass auf allen Pfaden irgendwann mal f gilt, und f bedeutet irgendwas wie Prozess 1 ist im krit. Abschnitt oder Proz. 2 oder 3….
Die Formel AGAFf sollte doch in CTL sein und müsste sie nicht auch eben das faire Verhalten erzwingen?

Wozu braucht man LTL? CTL ist ja von der Komplexität her besser berechenbar als CTL*, aber wofür ist LTL gut?

Bei BDDs: Was genau machen die logischen Operationen wie Shannon-Expansion und "apply"? Wozu macht man sowas? Fügt apply 2 BDDs zu einem zusammen?

Algoritmus für Ausfallkonsens (S.221)

In der Runde f+1 soll angeblich die Entscheidung y (y ist der Ausgefallene Prozessor, ne?)durch min(V) getroffen werden.
Wie kann das sein, V ist doch eine Menge und jede Zahl kommt nur einmal vor, also gibts auch nie ein Minimum. Was check ich da nicht???

Algoritmus für Ausfallkonsens (S.221)

In der Runde f+1 soll angeblich die Entscheidung y (y ist der Ausgefallene Prozessor, ne?)

nein, y ist die Variable, die an den Wert der Entscheidung gebunden wird. In Runde f+1 sollen alle zuv. Proz. eine Anweisung
y = b; ausführen, wobei b bei allen zuv. Proz. gleich ist.
Und wenn die Menge der möglichen Entscheidungen geordnet ist, haben spätestens in Runde f+1 alle Prozessoren die gleiche Menge und wählen daher auch das gleiche Minimum.

Wie kann das sein, V ist doch eine Menge und jede Zahl kommt nur einmal vor, also gibts auch nie ein Minimum. Was check ich da nicht???

in der Menge {1,2,3} ist 1 das Minimum,
das geht,
das ist nicht das Element mit der kleinsten Anzahl, sondern das kleinste Element

————

für E: X = aXb (ja ist geschützt, eine atomare Aktion vor jeder Variable genügt,
s_i ist sowas wie t_i, ja (so hab ichs verstanden))

würde ich <X|E> = a<X|E>b für richtig halten,
jedenfalls sieht <X|E> = aXb unnötig schlecht aus ;)

————
LTL ist auch von der Komplexität her besser,
da ist doch sogar ein Algorithmus angegeben,
mit dem man alle LTL-Formeln berechnen kann! (label(s))
oder ist der für CTL?

AGAFf klingt nett, aber vielleicht gibts ja doch ein Gegenbeispiel ;)

BDD keine Ahnung, kommt sicher auch nicht dran ;)

PNL-Prüfung macht doch Spass, bestimmt die einfachste im Hauptstudium

nein, y ist die Variable, die an den Wert der Entscheidung gebunden wird. In Runde f+1 sollen alle zuv. Proz. eine Anweisung
y = b; ausführen, wobei b bei allen zuv. Proz. gleich ist.

Ok, das ist mir jetzt klar. Aber was hat das y=b zu sagen?
Geht es wirklich nur um die Einigung auf ein Wert???

Aber was hat das y=b zu sagen?
Geht es wirklich nur um die Einigung auf ein Wert???

Ja. "Prozessor x entscheidet sich für b" ist ganz genau die Anweisung "y=b", die der Proz. x ausführt. y=b ist die Entscheidung, die halt bei allen die gleiche sein soll.

so eine Frage hab ich noch:

Kann mir irgendwer erklären, wie das mit dem exponentiellen Byzantinischen Konsensalgorithmus mit seiner Baumstruktur funktioniert?
Da steht doch, dass ein Prozessor die aktuelle Ebene in seinem Baum an alle verschickt, also im zweiten Schritt doch wohl eine Nachricht mit dem Inhalt p_0,p_1,p_2,…,p_n ggf noch mit den Werten, die diese Prozessoren im vorher in der 1. Runde mitgeteilt haben.
Wie soll jetzt diese Kette der Länge n in einen der Bäume passen, die doch alle nur die Tiefe 1 haben bzw. im gesamten Algorithmus nur auf Tiefe f+1 kommen? Irgendwie sinnvoller klingt es für mich, dass man die Dinger da oben einzeln verschickt und die dann irgendwie getrennt einsortiert, aber das geht für mich aus dem Skript nicht hervor….. [img]http://www.fb18.de/gfx/26.gif[/img]

ich sags mal wie ich mich erinnere (grad wieder ohne Skript), evtl. falsch,

0 a / | \ Baum von Prozessor 0 / | \ 1 2 3 | \ | \ | \ 2 3 1 3 1 2 | | | | | | 3 2 3 1 2 1

solche Bäume gibts bei jedem Prozessor 0 .. 3
(sind jetzt nur 4 und nicht min. 5 Prozessoren,
da gibts evtl. keinen Konsens, aber das Prinzip erkennt man auch hier)


oben steht immer die eigene Nummer (hier Prozessor 0) und wohl der eigene Startwert a,

in der nächsten Zeile 1, 2 und 3,
dort kommt direkt rein, was diese Prozessoren als eigenen Wert senden
-> '1 sagt sein Wert ist x' und
'2 sagt sein Wert ist c' und
'3 sagt sein Wert ist d'


betrachten wir mal den linken 1-Baum,
in der nächsten Zeile stehen eine 2 und eine 3,
dort kommt rein was 1 über diese beiden direkt aussagt
-> '1 sagt, dass 2 den Wert y hat' und
'1 sagt, dass 3 den Wert z hat'
(was 1 über 0 sagt ist egal falls das ankommt,
was wir selber haben wissen wir)

darunter ist noch eine Reihe für die Aussagen über die längsten Ecken
-> '1 sagt, dass 3 sagt, dass 2 den Wert b hat' und
'1 sagt, dass 2 sagt, dass 3 den Wert e hat'

('1 sagt, dass 2 sagt, dass 1 den Wert f hat' oder ähnliche weitere Fälle sind wohl sinnlos),

bei den anderen Teilbäumen entsprechend,


im ersten Schritt hat jeder schon die oberste Zeile (Startwert) ausgefüllt
und schickt diesen an die anderen ab,
-> die zweitoberste Zeile bei allen gefüllt,

in der nächsten Runde ist also die zweitoberste Reihe gefüllt,
diese kann man nun rumschicken,
damit dürfte sich die dritte Reihe quer durcheinander aber doch vollständig füllen lassen

usw.

so ich hab mich nun selbst überzeugt, ist bestimmt richtig [img]http://www.fb18.de/gfx/23.gif[/img]

prima, danke schön! So ähnlich hatte ich das auch mal im Kopf glaub ich, aber das Skript hat mich da total verwirrt. Werds mir auch besser nicht mehr ansehen *g*

bisschen falsch ist es eh, seh ich jetzt,

so siehts aus bei allen:

lambda / | | \ 0 1 2 3 | 1 ...
und links die 1 heißt
'1 sagt dass 0 den Wert w hat' und nicht
'0 sagt dass 1 den Wert w hat'

na egal

Hallo, kann jemand nochmal die Prozeßgraphen für Aufgabe
2.30 b)<X|X=aXb> und c)<X|X= aXb + c> posten ?

Ich bin unsicher bei der Frage, wie die Aktion b im Prozeßgraphen behandelt wird, da sie hinter der Variablen X steht?

zu b) würde mal tippen, <X|X> a <X|X>
—->
muss b eventuell nicht mehr berücksichtigt werden ?

Erst wird ja die Aktion a und dann die Aktion X ausgeführt. Zu b kommt man deshalb gar nicht. Die Lösung ist <X|X=aXb>bbbb…

Was genau ist eigentlich eine Klique?
Gibt es da nicht einen schönen Satz???

Warum nimmt beim co-bc-algo. jeder Prozessor nur Nachrichten an, wenn diese einen kleineneren Zeitstempel haben, als der Prozessor in seinem Vektor?
Dann dürfte er doch nie ein Annehmen, da sein Vektor(0 0 0) ist. Ausserdem kann ich das im Code auch nicht entdecken? Ist der Satz falsch formuliert???

eine Klique bezüglich R ist eine Menge, deren Elemente jedes zu jedem in der Relation R stehen. Eigentlich recht anschaulich, oder?

Der Prozessor p_2 kriegt eine Nachricht von p_1 und hat anfangs den Zeitstempel (0,0,0) bei 3 Prozessoren. Dann sieht er: Die Nachricht hat den Zeitstempel (1,0,0) ist also die erste Nachricht von p_1. Also sind die Bedinungen erfüllt:
(vt: Zeitstempel der Nachricht, v: Zeitst. von p_2)

Edit: hatte Smileys hinter vt und v stehen [img]http://www.fb18.de/gfx/22.gif[/img]
vt[ 1] = v[ 1]+1 // ist also die nächste erwartete
vt[ 2] = v[ 2] = 0 = vt[ 3] = v[ 3]
Also wird die Nachricht angenommen.

Wenn jetzt p_2 mit v = (0,0,0) die Nachricht mit vt = (1,0,1)
bekommt, heißt das, dass p_3 zuerst eine Nachricht geschickt hat, die ist bei p_1 angekommen und darauf hat dieser seine Nachricht abgeschickt. Also wartet p_2 erstmal, bis die Nachricht von p_3 auch bei p_2 angekommen ist.

Nach dem Empfang/der Verarbeitung einer Nachricht wird bei p_2 der Zeitstempelwert von p_1 bzw. p_3 erhöht.

zu b) würde mal tippen, <X|X> a <X|X>
—->

zu b) würde mal tippen, <X|X> a <X|X> ----> das wird so schön nur mit text tags angezeigt

(will auch im HS Moderator werden wenn ein gewisser anderer Herr das nicht korrigiert ;))

die beiden Prozessgraphen sind hier zu finden:
http://3773.rapidforum.com/topic=107582295597

Hallo!

Ich hab morgen Pruefung und hab da nochmal ein paar Fragen..

zu den Prufungen
1.
Kam schonmal bei jemanden der probabilistische Alg. zum wechselseitige auschluss, speicherzugriff in verteilten systemen oder logische/vektorielle Zeitstempel dran?

2. zum Stoff:
a) warum wird auf seite 207 bei bsp zum to-alg bei der ersten angekommen nachricht von p2 kein ts-up geschickt?

b) kann mir nochmal jemand sagen, was das R0 und S0 beim Alternierbitprotokoll anschaulich heisst? Und warum steht auf der rechten Seite dort ein Summenzeichen vor? (wenn es bedeuten wuerde fuer alle eingehenden datenelemente dannb braeuchte man ja die rekursion nicht) (wurde schonmmal nach dem beweis gefragt oder nur, nach der Def?)

Danke schonmal im voraus fuer die Anworten!

zu 1) Keines der Themen kam bei mir dran.
zu 2 a) müsste ich nachgucken … der formale Algorithmus stimmt jedenfalls.
b) R0 bedeutet: Der Empfänger ist im Zustand, dass er eine neue Nachricht erwartet und zwar mit dem Kontrollbit 0.
S0 bedeutet: Der Sender ist im Zustand, dass er eine neue zu versendende Nachricht annehmen kann und dann über T (?) verschicken wird. Das Kontrollbit soll dann 0 sein.
Die Summe ist in der Prozessalgebra sowas wie ein oder. Das + steht ja für eine Auswahl aus mehreren Alternativen. Also Summe der Nachrichten bedeutet einfach nur, dass die Spezifikation für alle Nachrichten gilt. Nicht, dass der Inhalt der Nachricht beeinflussen würde, wie das Protokoll abläuft…

Erstmal danke fuer die Antwort!

Aber warum geht er dann nie in R1 bzw S1?

Und kann mir nochmal jemand sagen, was das Summenzeichen beim Makierungspraedikat zu bedeuten hat? Das wird doch dann gar nicht mehr benutzt oder steckt das dann irgentwo drin?

Das mit dem Summenzeichen ist glaub ich ne Darstellungssache, ich würd mich nicht so an dem Markierungsprädikat festhalten, sondern mir lieber die Beispiele für Lebendigkeits- und Markierungs-Invarianzeigenschaften ansehen.
Wann hast du den Morgen Prüfung?

Aber warum geht er dann nie in R1 bzw S1?

Das hat mich auch etwas gewundert. Vielleicht ist das Verhalten gleich (weil ja eine Nachricht vorne rein und hinten rauskommt, egal ob 0 oder 1)…

Und kann mir nochmal jemand sagen, was das Summenzeichen beim Makierungspraedikat zu bedeuten hat? Das wird doch dann gar nicht mehr benutzt oder steckt das dann irgentwo drin?

Das wird doch benutzt! Ein Markierungsprädikat hat doch die Form:

[img]http://mokrates.de/cgi-bin/texstring?%5Csum_%7Bp%5Cin%20A%7D%20k_p%5Ccdot%20m(p)%20%5Cle%20k[/img]

Dabei hast du jeder Stelle, die von dem Prädikat "betroffen" ist, eine Gewichtung k_p zugewiesen und eine Gesamtobergrenze k festgelegt. Und in der Summe sollen halt die Gewichtungen mal die Zahl der Marken auf den Stellen in der Markierung m nicht übertreffen. Dann ist das M-Präd. in der Markierung m erfüllt.

a) warum wird auf seite 207 bei bsp zum to-alg bei der ersten angekommen nachricht von p2 kein ts-up geschickt?

da gibts keinen guten Grund denke ich,
ein kleiner Fehler im Bild

mal eine kurze zwischenfrage…

was ist dom(x)….bzw. wo finde ich eine definition von…

mal eine kurze zwischenfrage…

was ist dom(x)….bzw. wo finde ich eine definition von…

Wertebereich von x
auch definiert in M1 [img]http://www.fb18.de/gfx/15.gif[/img]

mal eine kurze zwischenfrage…

was ist dom(x)….bzw. wo finde ich eine definition von…

Im F2-Skript stehts z.B. drin. Wenn ichs richtig erinnere ist dom() diejenige Teilmenge des Urbildbereichs einer (partiellen) Funktion, auf der diese definiert ist.

Aeh, gut. 2x knapp daneben. Twoenn: das was Du beschreibst ist range(). Ich hab jetzt mal nachgeguckt:
Sei [img]http://mokrates.de/cgi-bin/texstring?R%20%5Csubseteq%20A%20%5Ctimes%20B[/img] eine Relation. Dann ist
[img]http://mokrates.de/cgi-bin/texstring?dom(y)%20%3A%3D%20%5C%7Bx%20%5Cin%20A%20%5Cmid%20x%20R%20y%5C%7D[/img]
und
[img]http://mokrates.de/cgi-bin/texstring?dom(R)%20%3A%3D%20%5Cbigcup_%7By%20%5Cin%20B%7D%20dom(y)[/img]

thx…lang her is =)

hab in F4 gesucht, hab nicht gedacht, dass ich noch weiter zurück musste..

xphilosoph:

R(S) ist die Erreichbarkeitsmenge (Def.5.3), RS(S) der Erreichbarkeitsgraph eines unbeschränkten Netzsystems S (S.139, mitte). Ich vermute, daß RG(S) und RS(S) synonym benutzt werden.

Aber auf Seite 140 sieht das ganze garnicht nach einem Graphen (also einem Tupel) aus…

[img]http://mokrates.de/cgi-bin/texstring?%24RS(S)%3D%5C%7B%20p_1%20%2B%20p_6%2C%20%5Cdots%20%5C%7D%24[/img]

RS(S) ist das gleiche wie R(S), also eine Erreichbarkeitsmenge. Das RS steht für Reachability Set.
Der Erreichbarkeitsgraph ist RG(S) für Reachability Graph.

Dann handelt es sich also nach Def. 5.4 um einen Tippfehler:

Der Erreichbarkeitsgraph RS(S) eines unbeschränkten Netzsystems S ist nicht endlich

Ja, auf alle Fälle. Habe extra im Tutorium nochmal nachgefragt.
Im Skript gibt es noch ein paar Ungereimtheiten…

Kann mir jemand folgendes erklären?

Im Beweis zu Satz 7.6 ("Es gibt keinen Konsens-Algorithmus für ein System aus n Prozessoren mit mehr als ceiling(n/3) Byzantinern") steht:

Auf T ist Satz 7.5 anwendbar. Die Vorraussetzung des Satzes lautet: maximal ein byzantinischer Prozessor

7.5 besagt, dass es keinen Konses-Algorithmus für drei Prozessoren mit einem Byzantiner gibt. Den Zusammenhang verstehe ich nicht.

Ah und noch was: Seh ich das richtig, dass beim exponentiellen byzantinischen Algorithmus, wirklich nur die Werte in den Blättern ausgewertet werden?

[edit] Keine Ahnung, warum ich "gespeichert" geschrieben habe ich meinte "ausgewertet"

nur die Blätter werden ausgewertet, ja



zum Beweis: ich verstehen den so wie er da steht auch nicht,

vielleicht gehts so:man teilt die Prozessoren von S so wie angegeben in 3 Gruppen
und zwar in eine Gruppe nur die byzantinischen,
da >= n/3 byzantinische da sind muss man eine Gruppe voll kriegen,

also kann man daraus ein System T basteln, dass wie in Beweis 7.5 funktioniert:
3 Prozessoren und mindestens einer byzantinisch,

gäbe es nun einen Algorithmus A für S dann auch für T im Widerspruch zu Beweis 7.5

Hmm, morgen Prüfung, nochmal kurz den Ausfallkonsens (nicht-byzantinisch!) angeguckt und plötzlich gewundert:

Bei 4 Prozessoren und einem Ausfall sollte das in f+1=1+1=2 Runden hinhauen. Warum klappt das nicht in meinem Beispiel?

In der ersten Runde senden alle ihren Startwert, p4 schickt nur an p1, fällt dann aus. In der zweiten Runde könnte p1 dann "9" schicken, in der dritten "2" und erst in der vierten wäre sichergestellt, dass alle die eins haben. Da das Minimum gewählt wird würde doch (in dem Fall) kein Konsens nach der 2ten Runde bestehen…

Start nach 1ter p1 {3} {3,1,9,2} p2 {9} {3,9,2} p3 {2} {3,9,2} p4 * {1} {3,9,2}

In der zweiten Runde könnte p1 dann "9" schicken, in der dritten "2" und erst in der vierten

Da ist der Fehler: Er sendet alle Elemente gleichzeitig, in einer Nachricht. (Alternativ: Er sendet alle Elemente, die er in der letzten Runde neu dazubekommen hat) In jedem Fall haben alle noch aktiven Prozessoren nach 2 Runden {1,2,3,9}.

Viel Erfolg morgen!

Das war schnell, danke, aber:

Ein unzuverlässiger Prozessor verschickt in der letzten Runde vor seinem Ausfall dieselbe Nachricht an andere Prozessoren aber nicht mehr unbedingt an alle

Edit: oder meintest Du das auf die Zeile "send bla to all processors? Das damit sozusagen synchronisiert wird?

Edit 2: Aber ist es dann nicht witzlos? Geht es dann nicht immer in einer Runde, egal wieviele ausfallen

Edit: oder meintest Du das auf die Zeile "send bla to all processors?

Genau das mein ich. Er verschickt die _Menge_ der Werte, die er noch nicht verschickt hat.

Edit 2: Aber ist es dann nicht witzlos? Geht es dann nicht immer in einer Runde, egal wieviele ausfallen

Nein. Nimm an, dass jede Runde genau ein Prozessor ausfällt, und der ausfallende Prozessor jeweils immer nur eine Nachricht an den, der in der Runde da drauf ausfallen wird, verschicken kann. Dann gelangt die Meinung des ersten ausfallenden Prozessors erst dann zu allen anderen, wenn alle unzuverlassigen Prozessoren ausgefallen sind.

"Die Menge der Werte"… [img]http://www.fb18.de/gfx/wand.gif[/img] und ich grübel mir hier n Ast. Gracias!

Und noch was. Wenn jemand noch vor 12 antwortet weiss ichs in der Prüfung:

Der polynomielle Algorithmus für den byzantinischen Konsens hat angeblich "konstante Nachrichtengröße", ich hab aber eigenlich den Eindruck, dass die Nachrichten beliebig gross werden können, was ja nicht mehr in die Ordnung konstant fallen dürfte…

jede Nachricht von der ersten bis zur letzen Runde gleich groß?

ne die sind doch sogar konstant, nur das eigene pref wird geschickt

im exponentiellen Algorithmus wird ja jeweils eine ganze Ebene des größer werdenen Baums geschicht (-> unendlich große Nachrichten)

was meinst du mit "das eigene pref(i)"? es wird jedesmal eine Teilmenge der (eigenen) menge pref verschickt. am anfang je ein element, im zweiten schritt - wenn alle zuverlässig sind - (n-1) elemente.

man könnte natürlich die nachrichtengrösse als "1" interpretieren, da "eine" Menge verschickt wird, aber das fände ich nicht sehr nützlich.

oder ist gemeint, dass die nachrichtengrösse innerhalb der Runden kostant bleibt? Ich dachte das konstant würde sich darauf beziehen, dass die Größe in Bezug auf die Teilnehmer (also n) konstant bleibt.

ich seh das so, dass jeder Prozessor seine eigene Meinung an alle schickt:
1. send < pref > to all processors

nicht mehr und schon gar nicht pro Runde wachsend viele Werte

bei der king-Runde wird auch nur ein einzelner Wert (der häufigste Wert) geschickt

Oh mann, ich hab grad den byzantinischen polynomiellen und den Ausfallkonsens völlig durcheinander bekommen. Mann, mann mann… So ich mach mal schnell die Prüfung.

@merlin und wie war die prüfung denn?????

Bin zufrieden. Ich hatte ja nur 8 Tage, weil vorher PNL anstand und die Vorlesung vor einem Jahr gehört. Dafür lief es wirklich gut. Valk ist aber auch der netteste Prüfer, den ich je erlebt hab. Protokoll schreib ich morgen

An dieser Stelle nochmal Dank an alle, die mir immer so schnell geantwortet habeb… [img]http://www.fb18.de/gfx/danke.gif[/img]

Hallo, ich habe auch einmal ein paar Fragen:

S. 18
Wieso "erzwingt" der Verdeckungsoperator Kommunikation?? Das verstehe ich nicht..

S.152
Kann mir jemand in natürlicher Sprache erklären was "konservativ" heißt?

Kann mir jemand den totally Broadcast-Algirithmus und/oder den (nur) kausalen "beschreiben" -auch natürlichsprachlich.

Meint ihr auch, dass man S.212 - S.219 getrost auslassen kann?

Was ist die "Sättigung"? Ich habe nur was über die "Sättigungsfüllung" gefunden" -oder ist das das Gleiche?

Kam schonmal bei jemandem BDDs oder Zeitstempel dran?

Wofür ist die Temporallogik eigentlich direkt? Was kann man alles damit machen?

Vielen Dank schonmal im Vorraus!

S. 18
Wieso "erzwingt" der Verdeckungsoperator Kommunikation?? Das verstehe ich nicht..

Friss oder stirb, so habe ich es verstanden. Wenn die Prozesse (Aktionen?) nicht miteinander kommunizieren wollen, führt das zum Abbruch.
-geschrieben, jemand der sich im Theorie-Bereich über einer 3.7 freut. [img]http://www.fb18.de/gfx/22.gif[/img]

S.152
Kann mir jemand in natürlicher Sprache erklären was "konservativ" heißt?

IMHO: Konservative P/T-Netze sind ``altmodisch'':

1) Ihre Plätze/Transitionen haben eine maximale Kantengewichtung
von 1 (W(x,y) <= 1) - es gibt also keine multiplen Kanten, sondern
maximal eine einzige zwischen einer Stelle zu einer Transition bzw.
eine einzige von einer Transition zu einer Stelle.

2) Naja, es wird noch eine Funktion f erwartet, die jede Stelle
einen Wert zuordnet, also jede Stelle gewichtet.
Die Summe der Gewichte aller Eingangsstellen ist gleich der Summe
der Gewichte aller Ausgangsstellen.

Die zweite Bedingung hat man wohl eingeführt, um so etwas nicht
durchgehen zu lassen:

+-------| ( ) b | ^ | | | ----- | | T |<----+ ----- ^ | ( ) a a, b: Stellen T: Transition Die erste Bedingung wird erfüllt.
Die zweite aber nicht:

Eingangsgewichte = Ausgangsgewichte
<=> f(a) + f(b) = f(b)

Hoffentlich sehe ich das jetzt richtig…

Was ist die "Sättigung"? Ich habe nur was über die "Sättigungsfüllung" gefunden" -oder ist das das Gleiche?

Wird im Skript irgendwo, dieses Wort ``Sättigung'' erwähnt?

Für BDDs reicht es glaub ich zu wissen, das es binäre Entscheidungsbäume sind, die die Variablen des Systems als boolsche Formeln repräsentieren. Dadurch kann man Zustände zusammenfassen.
BDDs benutzt man beim symbolischen Model Checking. Hierbei ist es nicht notwendig, explizit den gesamten Berechnungsbaum im Speicher aufzubauen, der zum Beispiel beim Abwickeln einer Kripke-Struktur entsteht.

Super! Vielen Dank schonmal!

Ich habe in einem Prüfungsprotokoll gelesen, dass er nach der "Sättigung" gefragt hätte..

Bitte kann mir jemand nochmal den exponentiellen und den polynomiellen byzantinischen Algorithmus einfacher erklären?
Woher weiss ich denn jetzt wer zuverlässig ist und wer nicht?
Danke

Bitte kann mir jemand nochmal den exponentiellen und den polynomiellen byzantinischen Algorithmus einfacher erklären?

Ich versuchs mal:

Beim byzantinischen exponentiellen ist die Hauptidee, dass sich jeder Prozessor
einen Baum baut, wo er die Nachrichten der anderen Prozessoren
speichert. Nach f+1 Runden lassen die Prozessoren die Funktion
resolve() auf je ihren Baum los, der dann die Mehrheitsmeinung
im Baum errechnet - am Ende hat jeder zuverlässige (= heile)
Prozessor die gleiche Meinung (Ausgangswert).

Beim polynomiellen Algorithmus benutzt man in jedem Rechenschritt
(= 2 Runden) einen anderen Prozessor als König.
Da man 2*(f+1) Runden lang diesen Algo fährt, kommt mindestens 1
zuverlässiger Prozessor als König dran. Die Konsensbedingungen -
Termination, Einigung und Gültigkeit - sind auch hier garantiert.

Woher weiss ich denn jetzt wer zuverlässig ist und wer nicht?

IMHO: Du weisst es nicht! Es ist auch egal, wer zuverlässig ist
und wer nicht. Beide Algorithmen garantieren Termination,
Gütligkeit und Einigung und nur das ist wichtig.

In einem Prüfungsprotokoll stand recht knapp "wie Paralleoperator in PA? Ableitungsregel in PA und Kalkül dazu?". Dabei fiel mir auf, dass ich noch kein Stück begriffen habe, was hier mit "im Kalkül" gemeint wäre. Ich hätte in der Prüfung jetzt erst mal die vier hier aufgeschrieben:

x -v-> # x -v-> x ' y -v-> # y -v-> y' ----------- --------------- ----------- --------------- x||y -v-> y x||y -v-> x'||y x||y -v-> x x||y -v-> x||y'
Das sind die Ableitungsregeln. Wären die das jetzt für "in PA"? Im Skript habe ich unter "Ableitung im Kalkül" nur auf Seite 9 ein Beispiel gesehen, allerdings als konkrete Anwendung für einen PA-Ausdruck. In Verallgemeinerung wüßte ich nicht, wie das nun aussehen sollte.

ohne Kalkül machts doch gar keine Spass,
in meinen Skript kommen auf Seite 17 nach Satz 2.14 die 'Axiome des PAP-Kalküls':
M1, LM2-4, CM5-10

das sind so Regeln der Art M1: x||y = (x||_y + y||_x) + x|y

Öhm. Danke. Da bin ich wohl an der Formulierung der Frage gescheitert. An die Axiome hatte ich zwar auch gedacht, aber … "Ableitungsregeln in PA und Axiome dazu?" hätte ich verständlicher gefunden. [img]http://www.fb18.de/gfx/25.gif[/img]

Ich noch mal mit was zu einfachen. [img]http://www.fb18.de/gfx/22.gif[/img]

Definition 2.24 Prozesse p1, … pn werden als eine Lösung einer rekursiven Spezifikation {X_i = t_i(X_1, …, X_n) | i e {1, …, n}} modulo Bisimulations-Äquivalenz bezeichnet, fals p_i <-> t_i(p1, …, p_n) for i e {1, …, n} gilt.

Prozesse sind hier doch als Konkretisierungen von Ausdrücken mit möglichen Rekursionsvariablen zu verstehen, oder? Also bei X = aX + a würde hier p_1 = a, p_2 = aa, … gemeint sein?

Hmm. Wo ich das Kapitel gerade zum sechsten oder siebten Mal lese. Da steht doch die Anwort gleich bei Beispiel 2.25. Nichts für ungut. [img]http://www.fb18.de/gfx/21.gif[/img]

Wir hatten hier schon ein, zwei Mal das Thema, wie dernn der Prozessgraph zu <X|X=aXb+c> aussehen würde und waren da zu dem Ergebnis gekommen:

aXb+c --a-- (aXb+c)b --a-- (aXb+c)bb | | |c |c |c |b | |b |b # # #
Was dabei aber noch nicht geklärt wurde ist, wie denn die Ableitung dafür aussieht. Ich habe mir das bis jetzt so überlegt:

Gleich c:

c -c> # ( # / v -v> #) v:=c <X|E>+c -c> # (y -v> # / x+y -v> #) v:=c
Nutzung der Rekursion:

a -a> # ( # / v -v> #) v:=a a<X|E> -a> <X|E> (x -v> # / x*y -v> y) v:=a, x:=a, y:=<X|E> a<X|E>+c -a> <X|E> (x -v> x' / x+y -v> x') v:=a, x:=a, y:=c x':=<X|E> Drei Fragen:
- Wie kann ich Formal jetzt noch schön aufschreiben, dass dieses <X|E> das <X|X = aXb+c> darstellt, sofern ich damit überhaupt richtig liege?
- Wäre das so alles an Ableitung oder müsste ich noch die "Nutzung der Rekursion" mit der Wahl von c hinzufügen? Wie würde so was aussehen?
- Ist in den Zeilen oben selbst noch was falsch?

aXb+c --a-->(aXb+c)b --a-->(aXb+c)bb --a-->.. | | | |c |c |c | | | # <----b---- b <----b----- bb <----b-..... so ist doch gleich hübscher imho [img]http://www.fb18.de/gfx/25.gif[/img]

Hi, da ich in ein paar Tagen meine PNL-Prüfung habe, wollte ich noch mal ein paar Unklarheiten klären.

1. Wurde zwar schon gefragt, aber noch nicht wirklich 100%ig beantwortet, glaube ich: Wie ist das mit der Fairness in temporaler Logik? In LTL ist die Fairness-Formel doch AGFp, oder? Entspricht das "auf allen Pfaden gilt immer wieder p"? Und ist das - wie Christoph schon fragte - nicht äquivalent zu AGAFp in CTL? Ich versteh den Unterschied noch nicht…

2. An diejenigen, die ihre Prüfung bereits hinter sich haben: wenn es um Algorithmen für total/kausal geordnete Broadcast-Kommunikation geht, wie genau musstet ihr das beantworten? Reicht das, das Prinzip des Algos zu erzählen oder muss Pseudo-Code her? Wie wollte Herr Valk das haben?

3. Wie ist das mit dem Alternierbitprotokoll? Gilt das als Verifikation bei Prozeßalgebra? Was wird da genau verifiziert?
Und reicht es, wenn man als Spezifikation des Protokolls
X = rA(d)*sD(d)*X
angibt? Oder sollen die Spzifikation von Sender und Empfänger (diese jeweils 3 Zeilen a la Sb, Tdb und Udb) angegeben werden?

Und reicht es, wenn man als Spezifikation des Protokolls
X = rA(d)*sD(d)*X
angibt? Oder sollen die Spzifikation von Sender und Empfänger (diese jeweils 3 Zeilen a la Sb, Tdb und Udb) angegeben werden?

Das reicht, wenn er nach der externen Spezifikation schreibt. Das andere will er nicht mal haben, wenn man drei Mal versucht es ihm unterzuschieben, weil man das so schön auswendig gelernt hat. [img]http://www.fb18.de/gfx/22.gif[/img]

Danke, das hört sich schonmal ein bisschen beruhigend an.
Jemand da, der noch auf die anderen Fragen antworten kann?

Kann mir denn keiner ne Antwort geben?
Vor allem die Sache zur Fairness in Temporal-Logik würde ich gerne nochmal erklärt bekommen. Ist die Formel jetz AGFp?
Und wie kann man Fairness bei Temporal-Logik schön in einem Satz ausdrücken? "Die Alternative von einer sich immer wiederholenden Alternative kommt immer wieder dran"?

wenns keiner weiß dann weiß es eben keiner,

zu Algorithmus erklären: da DENKE ich, dass Formulieren a la 'x sendet an y vektor mit blah blah' reichen,
wichtiger als Code ist auf jeden Fall zu wissen WARUM das eine total ist und das andere kausal oder was auch immer die Algorithmen garantieren