TU Wien:Verteilte Systeme VO (Göschka)/Prüfung 2009-11-30

Aus VoWi
Wechseln zu: Navigation, Suche

« Prüfung 2009-10-12 | Prüfung 2010-01-08 »

Modus[Bearbeiten]

5 Fragen, nur 4 davon sind zu beantworten. zeit: 45 Minuten

Prüfungsfragen[Bearbeiten]

Frage 1[Bearbeiten]

Frage: Welche Arten von asynchronen RPCs gibt es? Geben Sie auch einen verallgemeinerten Überblick über verschiedene Typen der Kommunikation (persistent/transient bzw. synchron/asynchron).

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Asynchrone RPC\s*/si}}

Grundsätzlich kann zwischen 3 Arten von RPCs unterschieden werden:

  • synchron - Der Client wartet auf ein Ergebnis des RPCs.
  • asynchron - Der Client wartet auf eine Empfangsbestätigung des RPCs.
  • one-way - Der Client wartet nicht (nicht einmal auf eine Empfangsbestätigung).


Der verzögerte synchrone RPC besteht aus der Aneinanderreihung von 2 asynchronen RPCs:

  • 1. asynchroner RPC (Anfrage) wird vom Client an den Server gesendet.
  • 2. asynchroner RPC (Ergebnisse) wird vom Server an den Client gesendet.

somit ergeben die beiden asynchrone RPCs einen verzögerten synchronen RPC (es wird verzögert ein Ergebnis gesendet)


Warum in der Grafik der RPC als one-way gekennzeichnet wurde ist fraglich. Meine Vermutung wäre, dass der Server trotzdem nicht untätig auf eine Empfangsbestätigung vom Client wartet sondern weitere Anfragen bearbeitet und die Bestätigung optional bekommt.

ein verzögerter RPC besteht aus einem RPC vom Client zum Server mit der Anfrage, und einem RPC vom Server zum Client mit der Antwort. Zweiterer ist ein Einweg-RPC. Das Zusammenführen der beiden Calls ist also quasi der "verzögerte-RPC" --thomas 18:13, 7. Mär. 2012 (CET)

Verzögerter synchroner RPC:

Verzögerter synchroner RPC.jpg



Allgemeiner Überblick über verschiedene Typen der Kommunikation (Kapitel Message-Oriented-Communication):

Achtung: Bedeutung von asynchron unterscheidet sich hier etwas von der Bedeutung bei RPCs.

RPC Überblick.jpg

(a) Persistente asynchrone Kommunikation; (b) Persistente synchrone Kommunikation; (c) Transiente asynchrone Kommunikation; (d) Empfangsbasierte transiente synchrone Kommunikation; (e) Auslieferungsbasierte transiente synchrone Kommunikation; (f) Antwortbasierte transiente synchrone Kommunikation

Bei einer persistenten Kommunikation wird eine zur Übertragung übergebene Nachricht so lange von der Kommunikations-Middleware gespeichert, wie es dauert, sie an den Empfänger auszuliefern. Im Gegensatz dazu wird bei transienter Kommunikation eine Nachricht nur so lange gespeichert, wie die sendende und empfangende Anwendung ausgeführt werden. Die charakteristische Eigenschaft asynchroner Kommunikation ist, dass der Sender sofort fortfährt, nachdem er seine Nachricht zur Übertragung abgegeben hat. Bei der synchronen Kommunikation ist der Sender gesperrt, bis er weiß, dass seine Anforderung akzeptiert wurde.


Frage 2[Bearbeiten]

Frage: Wozu braucht man Uhrensynchronisation? Erläutern Sie das NTP und den Berkeley Algorithmus. Was ist die Problematik bei der Synchronisation von Physical Clocks?

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Uhrensynchronisation\s*/si}}

Uhrensynchronisation braucht man für die Festlegung der Reihenfolge von Operationen in Verteilten Systemen (Korrektheit verteilter und zeitabhängiger Informationsverarbeitung). Es muss nicht immer eine "wirkliche" Uhr verwendet werden. Es kann auch nur eine logische Uhr verwendet werden.

NTP (Network Timing Protocol): Es handelt sich dabei um eine Synchronisation mit einem externen Zeitgeber. Die Genauigkeit von Zeitgebern wird durch das sogenannte Stratum definiert. Je niedriger es ist, desto genauer ist eine Zeitquelle. Beim NTP wird ein höheres Stratum mit einem niedrigeren synchronisiert. Ein Rechner sendet eine Nachricht an den Zeitserver und merkt sich den Sendezeitpunkt t1. Der Server zeichnet sich den Empfangszeitpunkt t2 sowie den Sendezeitpunkt der Antwort (kurz davor) t3 und schickt die Antwort. Der Rechner zeichnet den Empfangszeitpunkt t4 auf. (t1 und t4: lokale Zeit; t2 und t3: Serverzeit)

Berechnung der Abweichung und des Delays:

Abweichung = ((t2 - t1) + (t3 - t4)) / 2

Delay = ((t2 - t1) + (t4 - t3)) / 2


Die Abweichung mit zugehörigem Delay wird acht mal ermittelt und die Abweichung mit dem kleinsten delay effektiv verwendet. Korrektur: beschleunigen oder bremsen der lokalen Uhr.

Delay über einem Grenzwert --> Zeitquelle nicht vertrauenswürdig (citation needed!).

Timing delay.png

Berkley Algorithmus: Es handelt sich dabei um eine interne Synchronisation. Es gibt einen Koordinator, welcher seine lokale Zeit an alle sendet (auch an sich selbst). Jeder antwortet mit seiner Abweichung von dieser Referenzzeit. Danach berechnet der Koordinator die durchschnittliche Abweichung und schickt jedem zurück, um wie viel er seine Zeit vor- oder zurückstellen muss. Korrektur: beschleunigen oder bremsen der lokalen Uhr.

  • Problematik: Uhren dürfen nie zurück gestellt werden, nur über längere Zeit verlangsamt. Antwortzeiten über Netzwerk unterschiedlich.

Clock Problem.png

weiß nicht, ob man sich dabei nur physische Uhren konzentrieren soll oder nicht (bitte diesen Punkt überarbeiten). Bei physischen Uhren kann es durch den Kristall-Oszillator zu einer Uhr-Asymmetrie kommen.

Edit: Ich glaub das Problem von "Physical Clocks" ist auf den Folien (WS2012/13) Seite 6 beschrieben. TAI seconds are of constant length, unlike solar seconds. Leap seconds are introduced when necessary to keep UTC in phase with the sun. Weiterer Punkt: ZeitZonenProblematik


Frage 3[Bearbeiten]

Frage: Erläutern Sie das Domain Name System DNS, sowie den Ablauf bei der Namens-Auflösung anhand der DNS Database (Resource Records). Was ist reverse lookup? Was ist ein zone-transfer?

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Domain Name System\s*/si}}


DNS ist das NS für das Internet. Es wird verwendet um Domainnamen auf IP-Adressen zu mappen. Eine Domain kann man sich als „Unterbaum“ eines hierarchischen Graphen vorstellen. Pfadnamen nennt man „Domainname“.


Knoten speichern ihre Daten in Resource Records. Resource Record ist die kleinste Informationseinheit im DNS.

ausgewaehlte Resource Record Typen:

  • SOA ? Start of Authority: Informationen zur dargestellten Zone
  • A ? IP eines Hosts
  • MX ? Mailserver
  • NS ? Name eines NS der die dargestellte Domain implementiert
  • CNAME ? Alias-Implementierung von DNS: speichert den cannonical name (= primary name) des hosts (--> soft link)
  • PTR ? wird für reverse DNS verwendet: hat host mit cannonical name soling.cs.vu.nl die IP 130.37.20.20, dann wird ein PTR eintrag für soling.cs.vu.nl mit wert 20.20.37.130.in-addr.arpa angelegt
  • (etc.)

Caching und Replikation werden zur Steigerung der Effektivität verwendet.


Zone-Transfer = Zonenübertragung (Übertragung von Resource Records) auf einen anderen NS also z.b. von Primary NS auf Secondary NS. Dies dient der Ausfallsicherheit und Performance.


(Ein Secondary NS kann ein Primary NS einer anderen Zone sein. Beide sind authorative).


Reverse-lookup: wird benötigt um von einer IP auf einen Domainname zu schließen. Dazu wurde eine eigene Domain (mit 3 (Ebenen von) Subdomains) begründet: in-addr.arpa-Domäne.

Somit lassen sich z.B. alle IP Adressen die mit 193 beginnen in der 193.in-addr.arpa Domäne finden.

Ablauf bei der Namens-Auflösung anhand der DNS Database (Resource Records):

Wenn man eine Verbindung zu einer Domain aufbauen will, braucht man zunächst einmal dessen IP-Adresse. Angenommen, ein Rechner X will eine Verbindung zu „de.wikipedia.org.“ (Rechner Y) aufbauen. Dazu braucht er dessen IP-Adresse. In den folgenden Schritten wird beschrieben, wie dies ablaufen könnte.

  1. Der Rechner X sucht in seiner Hosts-Datei, ob die IP-Adresse für „de.wikipedia.org“ dort hinterlegt ist. Falls dem nicht so ist, fragt er beim DNS-Server nach.
  2. Hat der DNS-Server von Rechner X eine IP-Adresse für den angefragten Namen zwischengespeichert, antwortet er damit und die Anfrage kommt zum Ende (siehe letzter Punkt). Andernfalls fragt er einen der 13 Root-Nameserver nach „de.wikipedia.org.“.
  3. Der Root-Nameserver findet heraus, dass die Auflösung dieses Namens in der „org.“-Zone weitergeht und sendet die Namen und die IP-Adressen der „org.“-Nameserver zum DNS-Server von Rechner X.
  4. Nun fragt der DNS-Server von Rechner X einen der Nameserver für „org.“-Domains nach „de.wikipedia.org.“.
  5. Der „org.“-Nameserver sendet ihm die Namen der Nameserver für die Zone „wikipedia.org.“.
  6. Anschließend fragt der DNS-Server von Rechner X einen „wikipedia.org.“-Nameserver wie die IP-Adresse des Namens "de.wikipedia.org." ist.
  7. Mit dieser Adresse wird an den DNS-Server von Rechner X geantwortet und der …
  8. … sendet sie an den Rechner X, welcher nun zum Beispiel seine HTTP-Anfragen an die IP-Adresse von „de.wikipedia.org.“ senden kann.


Frage 4[Bearbeiten]

Frage: Welche Besonderheiten sind bei der Replikation von Objekten zu beachten? Erläutern Sie (inkl. genauer Skizze) wie man "Replication transparency" in Objektsystemen umsetzen könnte ("replicated invocation").

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Replikation von Objekten\s*/si}}

folgender Absatz ist meiner Meinung nach zu wenig

Eine Menge von Replikaten wird zu einer Gruppe zusammengefasst, wobei ein Replikat der Koordinator dieser Gruppe ist. Aufgerufen wird eine Methode immer bei allen Replikaten um sicherzustellen, dass alle den aktuellen Status haben (etwa über Reliable Multicast). Falls dieses replizierte Objekt jedoch selbst wieder eine Methode eines anderen distributes Objects aufruft, dann wird das nur vom Koordinator der Gruppe gemacht. Andernfalls würde die Methode zu oft aufgerufen werden. Auch die Antwort eines Aufrufs wird nur vom Koordinator zurückgeschickt.


Schon eher trifft es das hier:

Problem: Wenn Objekte in verteilten Systeme verwendet werden und ebenfalls verteilt sind, dann müssen auch die Zugriffe auf Objekte konsistent gehalten werden, da es sonst zu inkonsitenten Zuständen innerhalb des Systems führen kann (entry consistency). Wir müssen also eine gleichzeitige Ausführung von Methoden am Objekt verhindern (durch Locking relativ einfach zu lösen) und wir müssen Änderungen (Methodenaufrufe) auf ALLE Replikate des Objektes verteilen um sicherzustellen, dass nicht 2 unterschiedliche Aufrufe auf ein verteiltes System zur gleichen Zeit geschehen.

Dies kann folgendermaßen geschehen:

  • primary-based approach: ein "Koordinator" übernimmt die Kontrolle und delegiert die Aufrufe. Problem: Overhead, Skalierbarkeit geht verloren, "Koordinator" muss andere verteilte Objekte kennen.
  • totally-ordered-multicasts: Methodenaufrufe werden zB durch Lamport clocks durchnummeriert und dann in der Reihenfolge auf jedes Objekt ausgeführt. Problem dabei: sehr aufwändig, viel Overhead

Folgendes Bild beschreibt ein weiteres Problem:

Repl meth invoc problem.png

Methodenaufrufe auf ein vielleicht nicht verteiltes Objekt werden mehrmals ausgeführt. Um dies zu verhindern, gibt es zB folgenden Ansatz:

Repl meth invoc solutions.png

Falls von A aus ein Aufruf in B erfolgt, so ruft A alle Replikate in B (B1, B2, B3) auf. Wenn B nun seinerseits wieder eine Methode von C aufruft, so wird das nur vom Koordinator von B (z.B. B1) gemacht (und zwar bei C1 und C2). Andernfalls (wenn alle 3 Replikate von B den Aufruf durchführen würden) wäre die Methode von C zu oft aufgerufen worden. Die Antworten werden nur vom Koordinator zurückgegeben, also von z.B. C2 zu allen 3 Replikaten von B, und von B1 zu A.

Wird hier ausreichend auf das "Replication transparency" eingegangen? Wie wird die Replikationstranpsarenz hier konkret umgesetzt?


Frage 5[Bearbeiten]

Frage: Erklären Sie, wie sich zwei Kommunikationsteilnehmer basierend auf symmetrischen Schlüsseln gegenseitig authentifizieren können. Zeigen Sie auch auf, welche Probleme entstehen können, wenn ein Protokoll falsch "optimiert" wird.

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Symmetrische Authentifizierung\s*/si}}

Zur Auflockerung: https://web.archive.org/web/20180817172259/https://xkcd.com/177/

TU Wien-Verteilte Systeme VO (Göschka) - distsys security S27.gif

  • 1 : Alice sendet ihre Identität an Bob um einen Kommunikationskanal zu eröffnen.
  • 2 : Bob Sendet eine Aufforderung Rb an Alice (Kann z.B. eine Zufallszahl sein)
  • 3 : Alice verschlüsselt es mit dem secret Key Kab (den sie mit Bob teilt) und schickt die Nachricht an Bob. Bob kann die Nachricht entschlüsseln und festzustellen, ob sie Rb enthält, wenn das der Fall ist, weiß er, dass Alice an der anderen Seite sitzt. Alice weiß aber noch nicht, dass es sich sicher um Bob handelt auf der anderen Seite.
  • 4 : Alice sendet eine Aufforderung Ra an Bob.
  • 5 : Bob sendet Kab(Ra) zurück.

TU Wien-Verteilte Systeme VO (Göschka) - distsys security S28.gif

Diese Reduzierung ist sehr unsicher und kann leicht zu einer Reflection Attack führen.

TU Wien-Verteilte Systeme VO (Göschka) - distsys security S29.gif

Reflaction Attack: Chuck gibt sich als Alice aus. Er lässt Bob die Nachricht selbst in einem zweiten Kanal verschlüsseln.