TU Wien:Verteilte Systeme VO (Dustdar)/Pruefung 2018-12-12

(Fragen nicht in spezifischer Reihenfolge)

Wie leicht zu erkennen ist, haben sich bei der Prüfung auffallend viele Fragen aus vergangenen Prüfungsangaben wiederholt. Das war früher mMn nicht unbedingt der Fall.

Fragenausarbeitung

Transparenz 2 Eigenschaften erklären

• Access: Hide differences in data representation and how a resource is accessed
• Location: Hide the location of the resource
• Migration: Hide that a resource may be moved to another location
• Relocation: Hide that a resource may be moved while being used
• Replication: Hide that a resource is replicated
• Concurrency: Hide that a resource may be shared by competitive users.
• Failure: Hide the failure and recovery of a resource

IaaS, SaaS, PaaS erklären

• IaaS (Infrastructure as a Service)
  Computer Infrastruktur wird als Service angeboten.
  z.B. Virtuelle Maschinen oder Speicher

• PaaS (Platform as a Service)
  Eine Computerplattform wird als Service angeboten.
  z.B. Betriebssystem, Datenbank, Web-Server

• SaaS (Software as a Service)
  Zugriff auf Anwendungssoftware, die häufig als "On-Demand-Software" bezeichnet wird.
  Man muss sich keine Sorgen um Installation, Aufsetzen oder Ausführen machen.
  Der Service Provider macht das für einen. z.B. Google Apps

Overprovisioning erklären

Ein Ressourcen Provider hat mehr Ressourcen als von seinen Kunden tatsächlich benutzt werden.
Ungenutzte Kapazitäten -> unnötige Kosten
(darum häufig flexible Cloud statt festes Datenzentrum)

Token Election-Ring erklären, also die 2 Nachrichtenarten

Election Algorithms
Viele Algorithmen brauchen einen Koordinator.
Der Koordinator soll aus den beteiligten Prozessen dynamisch bestimmt werden.

• Bullying Algorithm
  • Jeder Prozess hat ein Gewicht. Der schwerste Prozess soll Koordinator sein.
  • Jeder Prozess kann eine Election starten: schickt sein Gewicht an alle anderen Prozesse.
  • Wenn ein anderer Prozess schwerer ist, schickt er eine "take-over" Nachricht an den herausfordernden Prozess und sendet sein Gewicht an alle weiteren Prozesse.
  • Wenn kein Prozess mit einer "take-over" Nachricht antwortet, gewinnt der herausfordernde Prozess und schickt eine "victory" Nachricht an alle anderen Prozesse.

• In a Ring Algorithm
  • Wie bei Bullying, nur wird die Nachricht von Prozess zu Prozess weitergegeben.
  • Wenn die Nachricht einmal durch den Kreis gelaufen ist, haben alle ihr Gewicht bekannt gegeben.
  • Der herausfordernde Prozess kann anschließend den Koordinator bekannt geben.

Unterschied Synchronisation bei Multiprozessoren und Multicomputern

Kommunikations-Modelle:

• Multiprozessoren: geteilter Speicher
  (Synchronisation: benötigt Schutz gegen fehlerhaften gleichzeitigen Zugriff, Semaphors, Monitors etc.)
• Multicomputer: Nachrichten schicken
  (Synchronisation: Blocken im Message Passing)

Lease - alle 3 Arten nennen und beschreiben

Leases
Ein Lease ist ein Versprechen vom Server:
dass er einem Client solange Updates pushed
bis das Lease von diesem Client abgelaufen ist.
Ist das Lease abgelaufen: dann muss Client Informationen pullen.
Generell werden Leases verwendet um den Server zu entlasten.

• Age-based
  

Ein Objekt, das sich länger nicht geändert hat, wird das auch demnächst nicht tun, also lange leasen.

• Renewal-frequency-based
  

Je öfters ein Client nach einem Objekt fragt, desto länger wird seine expiration-time für dieses Objekt.

• State-based
  

Je mehr ein Server belastet ist, desto kürzer wird die Expiration-Time.

Lamport-Clock Werte einzeichnen und Formeln angeben

Lamport-Clock

Problem:

• Wie erreichen wir, dass ein Verteiltes System sich global konsistent verhaltet mit Hilfe der happened-before Beziehung?

Lösung:

• Zu jedem Event einen Timestamp C(e) hinzufügen, sodass folgende Kriterien erfüllt sind:
  • Wenn a und b zwei Events von einem Prozess sind und a kommt vor b,
    dann muss auch C(a) < C(b) gelten.
  • Wenn a mit dem Senden einer Nachricht zusammenhängt und b mit dem Empfangen,
    dann muss auch C(a) < C(b) gelten.

• Jeder Prozess hat einen eigenen Counter Ci
  • Bevor ein Ereignis in Pi (ein Prozess) ausgeführt wird, wird Ci um 1 erhöht
  • Immer wenn eine Nachricht von Pi gesendet wird,
    bekommt sie (vor dem Senden) den Timestamp ts(m) = Ci.
  • Immer wenn eine Nachricht von Pj empfangen wird,
    setze den Cj auf max{Cj, ts(m)} und führe Schritt 1 vor der Verarbeitung der Nachricht aus.

Achtung: Wir können keine kausalen Zusammenhänge durch das Vergleichen der Timestamps herausfinden.
C(a) < C(b) bedeutet nicht unbedingt, dass a -> b gilt!

Begründen, wieso FIFO und/oder Causality

FIFO-Consistency

• Wenn ein Prozess zwei Write-Befehle in einer gewissen Reihenfolge ausführt,
  müssen all Prozesse die Read-Befehle zu diesen Werten in der selben Reihenfolge durchführen.
  
• Write-Befehle aus verschiedenen Prozessen sind unabhängig voneinander.

Causal-Consistency

• Wenn zwischen 2 Write-Befehlen ein Read-Befehl ausgeführt wird, müssen alle Prozesse,
  die die Werte (von den 2 Write-Befehlen betroffen) lesen wollen,
  dies in der selben Reihenfolge machen, wie die 2 Write-Befehle ausgeführt wurden.
• Ist kein Read-Befehl zwischen zwei Write-Befehlen, können diese als concurrent angesehen werden.
  Das bedeutet die Reihenfolge wie die betroffenen Werte gelesen werden ist egal.

Sequential-Consistency (alle guten Dinge sind drei)

• Die Read-Befehle von allen Prozessen müssen in der selben Reihenfolge sein.
  (unabhängig von Writes)

Soll ein Single-Thread/Multi-Thread/Multi-Processor-Ansatz bei Webservern genommen werden (aus Server-Sicht)

Multi-threaded webserver with multiprocessors.
There should be no blocking of clients and their requests,
which is why each client should receive its own thread to interact with the server.
-> Ein dispatcher-Thread teilt die Anfragen auf die Worker-Threads auf, die dann parallel ablaufen.

Vorteil von KDC mit Tickets gegenüber herkömmlichen KDC

Aus dem Buch übernommen:

The main drawback of this approach (der herkömmlichen KDCs, Anmk.) is that Alice may want to start
setting up a secure channel with Bob even before Bob had received the
shared key from the KDC. In addition, the KDC is required to get Bob into
the loop by passing him the key. These problems can be circumvented if
the KDC just passes KB,KDC(KA,B) back to Alice, and lets her take care of
connecting to Bob.

Namespace und Naming Domain erklären (2 Fragen, bei Naming Domain musste man auch einen Zusammenhang zu Namespaces herstellen)

Name Spaces

• Beinhaltet alle Namen, die bei einem Service verwaltet werden.
• Namen sind in einem name space so organisiert, sodass sie als Graph dargestellt werden können.
• Jeder Blatt Knoten repräsentiert eine Entity. (Auch die anderen Knoten sind Entities.)
• Ein Alias ist ein Name, der auf einen anderen Namen zeigt.
• Eine Naming domain ist ein Name-Space mit einer einzelnen Administrations-Authoritiy
  für ihre Namen (Beispiel: nic.at ist für alle *.at Domains zuständig)

Capabilities erklären

(vom Thema: Access Control,
Alternativen zu Capabilities: Access Control Matrix, Access Control List)

Capabilities: Jedes Subjekt S hat eine Fähigkeit: ACM[S,*]
beschreibt die erlaubten Operationen für jedes Objekt (oder Kategorie von Objekten)

Unterschied transiente / persistente Kommunikation

Persistent
Nachrichten werden am Server solange gespeichert, bis sie zugestellt werden können.

Transient
Nachrichten werden vom Server gelöscht, wenn sie nicht zugestellt / weitergeleitet werden können.

3 Arten der Redundanz erklären

• Physical Redundancy: Add additional components (e.g. Backup server)
• Time Redundancy: Repeat request (e.g. Retransmissions in TCP/IP)
• Information Redundancy: Add extra information (e.g. parity bit)

Warum gibt es nicht nur eine Lösung, wenn der Server crasht?

Verhalten vom Server

• At-least-once-semantic
  Der Server garantiert, dass jede Operation mindestens einmal ausgeführt wird.

• At-most-once-semantics
  Der Server garantiert, dass jede Operation maximal einmal ausgeführt wird.

Verhalten vom Client

• Den Request immer neu ausstellen.
• Den Request nie neu ausstellen.
• Den Request nur neu ausstellen, wenn Client kein ACK vom Server erhalten hat.
• Den Request nur neu ausstellen, wenn Client ACK vom Server erhalten hat.

2 * 4 = 8

Quorum: Welche 2 Bedingungen müssen gelten?

• Write Konflikte vermeiden: W >= (N+1)/2
• Starke Konsistenz: W+R > N

• Lesen optimieren: R=1 W=N
• Schreiben optimieren: R=N W=1