TU Wien:Verteilte Systeme VO (Dustdar)/Pruefung 2021-05-19

Frage 1:

A website is replicated across a large number of servers. The domain name of the website is resolved to the IP address of an HTTP load balancer. The load balancer receives a client request and dispatches it to one of the available servers in a random manner. Explain how this setup helps to provide failure transparency, and argue whether it provides replication transparency or not.

(Eine Website wird auf einer großen Anzahl von Servern repliziert. Der Domainname der Website wird in die IP-Adresse eines HTTP-Load-Balancers aufgelöst. Der Load Balancer empfängt eine Client-Anfrage und sendet sie nach einem Zufallsprinzip an einen der verfügbaren Server. Erläutern Sie, wie dieses Setup zur Bereitstellung von Fehlertransparenz beiträgt, und diskutieren Sie, ob es Replikationstransparenz bietet oder nicht.)

Frage 2:

Let’s assume we’ve got a Paxos run with eight acceptors and two proposers. Because of network issues, we end up with two partitions of nodes, each containing four acceptors and one proposer. The two partitions (more precisely: the nodes in each partition) agree on two different values in the Paxos run. Would this work? If not, explain why this will not happen.

(Wir haben einen Paxos-Durchlauf mit acht Akzeptoren und zwei Vorschlagenden. Aufgrund von Netzwerkproblemen erhalten wir aber zwei Partitionen, mit jeweils vier Akzeptoren und einem Vorschlagenden. Die beiden Partitionen (oder genauer: die Knoten in jeder Partition) einigen sich auf zwei unterschiedliche Werte in diesem Paxos-Durchlauf. Würde dies funktionieren? Falls nicht, erklären Sie, warum dies nicht geschieht.)

Frage 3:

A robot control application works as follows: It receives sensing information from a mobile robot connected to the Internet over a Wi-Fi link, processes the sensing data, and decides in real time on an appropriate robot control action which it sends to the robot (e.g., instructs the robot to change its direction to avoid an obstacle). Would you execute the robot control application in an edge computer or in a cloud virtual machine and why?

(Eine Robotersteuerungsapplikation funktioniert wie folgt: Sie empfängt Sensorinformationen von einem mobilen Roboter, der über eine Wi-Fi-Verbindung mit dem Internet verbunden ist, verarbeitet die Sensordaten und entscheidet in Echtzeit über eine geeignete Robotersteuerungsaktion, welche sie an den Roboter sendet (z.B. weist den Roboter an, seine Richtung zu ändern, um ein Hindernis zu vermeiden). Würden Sie die Robotersteuerungsapplikation auf einem Edge-Computer oder in einer virtuellen Maschine in der Cloud ausführen und warum?)

Frage 4:

Explain why HTTP-based communication is usually transient and synchronous. What are the benefits of this communication approach?

(Erklären Sie, warum HTTP-basierte Kommunikation üblicherweise transient (flüchtig) und synchron ist. Was sind die Vorteile eines solchen Kommunikationsansatzes?)

Frage 5:

(Hier schein ein Bild zu fehlen, kann man daher leider nicht beantworten)

Consider the following Read/Write events.

   Does this system provide causal consistency? Why/Why not?
   Does this system provide sequential consistency? If yes, why? If not, explain why and propose an ordering that offers sequential consistency.

(Betrachten Sie die folgenden R/W-Ereignisse.

   Bietet dieses System kausale Konsistenz? Warum/Warum nicht?
   Bietet dieses System sequentielle Konsistenz? Wenn ja, warum? Wenn nicht, erklären Sie warum und schlagen Sie eine Reihenfolge vor, die sequentielle Konsistenz bietet.)

Frage 6:

Let’s assume that we are making use of flat naming in a distributed system. The network is rather small (with about 20 nodes/entities). The nodes/entities may change their locations from time to time, but the number of nodes/entities is stable, i.e., nodes and entities do not leave the system and also no new nodes and entities enter the system. Would you rather use Hierarchical Location Services or Broadcasting for such a distributed system? Motivate your answer.

(Nehmen wir einmal an, dass wir flache/unstrukturierte Benennung in einem verteilten System verwenden. Das Netzwerk ist relativ klein (mit ca. 20 Knoten/Entitäten). Die Knoten/Entitäten wechseln von Zeit zu Zeit auf einen neuen Ort, aber die Anzahl an Knoten/Entitäten ist stabil, d. h. Knoten und Entitäten verlassen das System nicht und es kommen auch keine neuen Knoten/Entitäten in das System. Würden Sie eher Hierarchical Location Services (Hierarchische Lokalisierungs-Dienste) oder Broadcasting (Massenaussendung) für solch ein verteiltes System verwenden? Motivieren Sie Ihre Antwort.)

Frage 7:

You have to conceptualize and implement a new backend system for the Austrian public health sector, i.e., a server-based software which is able to store all patient data and allows doctors and pharmacists to access patient-related data. Explain why you would design the software as either a singlethreaded process, a multithreaded process, or a multiprocess program. You can ignore that a server cluster would be needed to answer all requests, i.e., just assume that you have one machine with virtually unlimited resources available.

(Sie sollen ein neues Backend-System für das österreichische Gesundheitswesen konzipieren, d. h. eine serverbasierte Software, welche die gesamten Patientendaten speichert und es ÄrztInnen und ApothekerInnen erlaubt, auf diese Patientendaten zuzugreifen. Erklären Sie, warum Sie die Software als Single-Thread-Prozess, als Multi-Thread-Prozess oder als Multi-Prozess-Programm designen würden. Sie können dabei vernachlässigen, dass Sie ein Server-Cluster benötigen, um alle Anfragen zu beantworten. Nehmen Sie der Einfachheit halber an, dass Sie über einen Server mit praktisch unendlichen Ressourcen verfügen.)

Frage 8:

(Hier schein ein Bild zu fehlen, kann man daher leider nicht beantworten)

Three processes p1, p2 and p3 use vector clocks VC1, VC2 and VC3, respectively. In the figure above, you see the initial state of the vector clocks as well as some events ex and messages my. Fill in the missing values of the vector clocks for each time step t1-4 in the format (X,Y,Z), e.g., (0,0,1). This is important, your answer is not graded correctly if you use a different format. If the vector value is not defined yet, use "0" to indicate this. In your answers, do not use blanks, but provide the brackets.

Hints: To simplify the figure, the vector clocks are shown in parallel for the three processes. Fill in all empty boxes, even if there is no change for a particular process. Events only apply to one process and are applied instantly to the according vector clock. Messages are delivered instantly (which is of course not possible in reality).

(Drei Prozesse p1, p2 und p3 verwenden jeweils eine Vektoruhr VC1, VC2 bzw. VC3. In der Abbildung sehen Sie den initialen Status der Vektoruhren sowie Ereignisse ex und Nachrichten my. Tragen Sie die fehlenden Werte der Vektoruhren für die einzelnen Zeitpunkte t1-4 ein. Nutzen Sie das Format (X,Y,Z), z. B. (0,0,1). Dies ist wichtig, weil Ihre Antworten nicht korrekt bewertet werden, falls Sie ein anderes Format nutzen. Falls ein Vektorwert bisher nicht definiert wurde, nutzen Sie "0", um dies anzugeben. Verwenden Sie in Ihren Antworten keine Leerzeichen, aber geben Sie die Klammern an.

Hinweise: Um die Grafik einfacher zu gestalten, werden die Vektoruhren für die drei Prozesse parallel dargestellt. Füllen Sie alle leeren Felder ein, auch wenn es keine Änderung für einen bestimmten Prozess gibt. Ereignisse wirken sich nur auf einen Prozess aus und werden sofort auf die jeweilige Vektoruhr angewendet. Nachrichten werden sofort ausgeliefert (was natürlich in der Realität nicht der Fall ist.))

Frage 9:

Two replica servers need to be placed, and there are three candidate locations (L1, L2, L3). The replica servers will serve three clients and, for each client, its distance in terms of latency to any of the locations L1, L2, and L3 is known and is given in the table below (each cell of the table shows the latency for the respective client to reach a location):

(Es müssen zwei Replikatserver platziert werden, und es gibt drei Kandidatenstandorte (L1, L2, L3). Die Replikatserver bedienen drei Clients, und für jeden Client ist die Entfernung im Hinblick auf die Latenz zu einem der Standorte L1, L2 und L3 bekannt und in der folgenden Tabelle angegeben (jede Zelle der Tabelle zeigt die Latenz für den jeweiligen Client, um einen Ort zu erreichen):

Latency for a client to reach a location (Latenz für einen Client um einen Ort erreichen)

	L1	L2	L3
Client 1	10	100	100
Client 2	100	50	60
Client 3	100	30	15

Execute a greedy server placement algorithm that aims to minimize the total latency experienced by the clients and provide the derived placement below:

(Führen Sie einen gierigen (engl. "greedy") Server-Platzierungsalgorithmus aus, der darauf abzielt, die Gesamtlatenz der Clients zu minimieren und die folgende abgeleitete Platzierung bereitzustellen:)

Location of Server 1, selected at step 1 of the algorithm
(Speicherort von Server 1, ausgewählt in Schritt 1 des Algorithmus):
 Antwort

Location of Server 2, selected at step 2 of the algorithm
(Speicherort von Server 2, ausgewählt in Schritt 2 des Algorithmus):
Antwort

Total latency of the solution (sum of the latencies of all clients in the given solution)
(Gesamtlatenz der Lösung (Summe der Latenzen aller Clients in der angegebenen Lösung)):
Antwort

(Please note that you are not asked to necessarily provide the optimal placement, but the one returned by this algorithm. Since this is a greedy heuristic algorithm, its solution is not guaranteed to be the optimal one.)

(Bitte beachten Sie, dass Sie nicht unbedingt die optimale Platzierung angeben müssen, sondern die von diesem Algorithmus zurückgegebene. Da es sich um einen heuristischen Greedy Algorithmus handelt, kann nicht garantiert werden, dass die Lösung optimal ist.)

Frage 10:

Consider a social network where data are replicated across a number of distributed servers. Each user accesses the social network via the closest replica server. We make the following assumptions:

   There are 3 users in this social network, A, B, and C.
   There are two replica servers, L1 and L2.
   Initially, the read and write sets of each user are empty.

Then, consider the following sequence of events:

   User A accesses the social network via L1 and adds a "like" to B's profile picture.
   B accesses his profile via L1 and sees the "like" from A.
   User C accesses the social network via L1 and adds a "like" to B's profile picture.
   The next day, B views the profile picture from a different location served by server L2, and sees the "like" from A but not the one from C.

Assuming a naive implementation of a client-centric consistency protocol for monotonic read consistency, what are the contents of B's read and write sets at the end of the above sequence of events?

(Stellen Sie sich ein soziales Netzwerk vor, in dem Daten auf mehreren verteilten Servern repliziert werden. Jeder Benutzer greift über den nächstgelegenen Replikatserver auf das soziale Netzwerk zu. Wir gehen von folgenden Annahmen aus:

   Es gibt 3 Benutzer in diesem sozialen Netzwerk, A, B und C.
   Es gibt zwei Replikatserver, L1 und L2.
   Zu Beginn sind die Lese- und Schreibsätze jedes Benutzers leer.

Betrachten Sie dann die folgende Abfolge von Ereignissen:

   Benutzer A greift über L1 auf das soziale Netzwerk zu und fügt dem Profilbild von B ein "like" hinzu.
   B greift über L1 auf sein Profil zu und sieht das "like" von A.
   Benutzer C greift über L1 auf das soziale Netzwerk zu und fügt dem Profilbild von B ein "like" hinzu.
   Am nächsten Tag sieht B das Profilbild von einem anderen Ort aus, der vom Server L2 bedient wird, und sieht das "like" von A, aber nicht das von C.

Unter der Annahme einer naiven Implementierung eines clientzentrierten Konsistenzprotokolls für monotone Lesekonsistenz, was sind die Inhalte der Lese- und Schreibsätze (read and write sets) von B am Ende der obigen Abfolge von Ereignissen?)

Frage 11:

A small company is developing a mobile application. In order to host the application's back end, which includes user authentication, authorization, and data storage functionality, the company has the option of using either an Infrastructure-as-a-Service (IaaS) or a Platform-as-a-Service (PaaS) solution. For each of the two potential cloud solutions, provide one advantage and one disadvantage.

(Ein kleines Unternehmen entwickelt eine mobile Anwendung. Um das Back-End der Anwendung zu hosten, das Benutzerauthentifizierung, Autorisierung und Datenspeicherungsfunktionen umfasst, kann das Unternehmen entweder eine Infrastructure-as-a-Service- (IaaS) oder eine Platform-as-a-Service-Lösung (PaaS) verwenden. Geben Sie für jede der beiden möglichen Cloud-Lösungen einen Vorteil und einen Nachteil an.)

Frage 12:

Consider the following public-key cryptosystem: (Betrachten Sie das folgende Kryptosystem mit öffentlichen Schlüsseln:)

   Each user's key information includes a key pair (K+, K-) and a value n, where K+ is the public key, K- is the private key, and n is a modulus used in the encryption and decryption operations of these specific keys, as shown below. The modulus n and key K+ are public information. K- is kept secret by the user. 
   (Die Schlüsselinformationen jedes Benutzers umfassen ein Schlüsselpaar (K+, K-) und einen Wert n, wobei K+ der öffentliche Schlüssel, K- der private Schlüssel und n ein Modulus (Teilungsrest) ist, der bei den Verschlüsselungs- und Entschlüsselungsoperationen dieser spezifischen Schlüssel verwendet wird, wie nachfolgend dargestellt. Der Modulus n und der Schlüssel K+ sind öffentliche Informationen. K-  wird vom Benutzer geheim gehalten.)

   The following function is used for encryption and decryption: E(K, m, n) = mK mod n, where K is the key, m the message, and n the modulus corresponding to the specific key. When this function is used for encryption, K is the encryption key, m is the plaintext message, and the output of the function is the ciphertext (encrypted message). When it is used for decryption, K is the decryption key, m is the ciphertext, and the output is the original plaintext message.
   (Die folgende Funktion wird zum Ver- und Entschlüsseln verwendet: E(K, m, n) = mK mod n, wobei K der Schlüssel, m die Nachricht und n der dem spezifischen Schlüssel entsprechende Modulus ist. Wenn diese Funktion zur Verschlüsselung verwendet wird, ist K der Verschlüsselungsschlüssel, m die Klartextnachricht und die Ausgabe der Funktion der Chiffretext (verschlüsselte Nachricht). Wenn die Funktion zur Entschlüsselung verwendet wird, ist K der Entschlüsselungsschlüssel, m der Chiffretext und die Ausgabe die ursprüngliche Klartextnachricht.)

   To produce message digests, the following hash function is used: H(m) = m mod 5, where m is the message whose hash value we want to compute, and the output is the message digest.
   (Um Nachrichtenübersichten zu erzeugen, wird die folgende Hash-Funktion verwendet: H (m) = m mod 5, wobei m die Nachricht ist, deren Hashwert wir berechnen möchten, und die Ausgabe die Nachrichtenübersicht ist.)

User A wishes to send a message to user B using this cryptosystem. This plaintext message is the integer m = 4. The two users have the following keys:

(Benutzer A möchte mit diesem Kryptosystem eine Nachricht an Benutzer B senden. Diese Klartextnachricht ist die Ganzzahl m = 4. Die beiden Benutzer haben die folgenden Schlüssel:)

   User A: K+A = 7 (public key / öffentlicher Schlüssel), K-A = 3 (private key / privater Schlüssel), nA = 33 (modulus / Modulus),
   User B: K+B = 3 (public key / öffentlicher Schlüssel), K-B = 11 (private key / privater Schlüssel), nB = 15 (modulus / Modulus).

Answer the following questions filling in the correct integer values: (Beantworten Sie die folgenden Fragen und geben Sie die richtigen Ganzzahlwerte ein:)

   If A wishes to send the message encrypted in order to ensure confidentiality, what is the ciphertext value that B will receive?
   (Wenn A die Nachricht verschlüsselt senden möchte, um Vertraulichkeit zu gewährleisten, welchen Chiffretext erhält dann B?)
   Antwort

   If A wishes to assure B of the authenticity and integrity of the message, but not its confidentiality, what is the value of the message signature that B will receive?
   (Wenn A B die Authentizität und Integrität der Nachricht, aber nicht deren Vertraulichkeit versichern möchte, welchen Wert hat die Nachrichtensignatur, die B erhält?)