Gedächtnisprotokoll FGI209-2

Zum zweiten Versuch der FGI2-Klausur wurde in PhilA geschrieben, Aufsichten hatten Herr Valk und Herr Köhler. Insgesamt waren 181Punkte zu erreichen, der Schwierigkeitsgrad war ähnlich hoch wie zur ersten Klausur.

Aufgabe 1

• 1) Gegen waren zwei Transitionssysteme mit Sync = *leereMenge*. Geben sie das synchrone TS an.
• 2) Geben sie L(TS_1) und L(TS_2) an, bestimmen sie auch L(TS_3) = L(TS_1) \cap L(TS_2)
• 3) Formen sie TS_3 so um, dass es den Schnitt akzeptiert.
• 4) Geben sie die Synchronisationsmenge an.

Aufgabe 9

Man musste die logischen, nicht die vektoriellen, Zeitstempel eintragen.

Aufgabe 10

• 1) Wie unterscheiden sich der Ausfallalgorithmus von dem des byzantinischen Konsenses?
• 2) Was ist Nachrichtenkomplexität?
• 3) Geben Sie die Nachrichtenkomplexität des Ausfallalgorithmuses an.
• 4) Warum ist der erste Algorithmus aus der Vorlesung exponentiell?
• 5) Warum ist der zweite Algorithmus aus der Vorlesung polinomiell?