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

The exam was held online via TUWEL. Each student got an individual exam, where each question is randomly pulled from a pool of questions.

Aufgabe 1: Edge or cloud computing?

An online game for mobile devices involves rendering in real time complex game scenes. This requires a lot of processing and has stringent latency requirements so that a smooth user experience is provided to the player. The application developers have created the game software in such a way that rendering can be offloaded to a remote service component, which sends back game scenes to the mobile device. This involves streaming of real-time high-definition video to the device. Would you run this rendering service at an edge computing server or in the Cloud and why?

(Bei einem Online-Spiel für mobile Geräte werden komplexe Spielszenen in Echtzeit gerendert. Dies erfordert viel Rechenaufwand und stellt strenge Latenzanforderungen, sodass dem Spieler eine reibungslose Benutzererfahrung geboten wird. Die Anwendungsentwickler haben die Spielesoftware so erstellt, dass das Rendern auf eine Remote-Service-Komponente verlagert werden kann, die Spielszenen an das mobile Gerät zurücksendet. Dies beinhaltet das Streaming von hochauflösendem Echtzeitvideo auf das Gerät. Würden Sie diesen Rendering-Service auf einem Edge-Computing-Server oder in der Cloud ausführen und warum?)

Aufgabe 2: Performance transparency

A network file system allows performing read and write operations on remote file objects. The operating system provides system calls such as read() and write() to applications, and a middleware takes care of detecting if these refer to local or to remote objects. In the first case, the middleware executes a local read or write operation and returns the result to the calling application. In the second case, it passes the operation on to a special client, which in turn invokes a remote procedure call on the file server, and returns the result of the operation to the middleware. Finally, the middleware returns the result of the read or write system call to the calling application. Explain if this system guarantees performance transparency or not.

(Ein Netzwerkdateisystem ermöglicht das Ausführen von Lese- und Schreibvorgängen für entfernte Dateiobjekte. Das Betriebssystem stellt Systemaufrufe wie read() und write() für Applikationen bereit, und eine Middleware erkennt, ob sich diese auf lokale oder entfernte Objekte beziehen. Im ersten Fall führt die Middleware eine lokale Lese- oder Schreiboperation aus und gibt das Ergebnis an die aufrufende Applikation zurück. Im zweiten Fall wird die Operation an einen speziellen Client weitergeleitet, der wiederum einen Fernprozeduraufruf (engl. Remote Procedure Call - RPC) auf dem Dateiserver ausfürht und das Ergebnis der Operation an die Middleware zurückgibt. Schließlich gibt die Middleware das Ergebnis des Lese- oder Schreibaufrufs an die aufrufende Applikation zurück. Erklären Sie, ob dieses System Leistungstransparenz garantiert.)

Aufgabe 3: Encrypted DNS

An Internet Service Provider (ISP) controls the traffic of its customers by inspecting their DNS requests and blocking them (i) if they point to forbidden domains or (ii) if the DNS requests are encrypted and the ISP cannot decrypt them, so it drops them by default. Which mechanism for encrypted DNS makes it harder for the ISP to perform this type of traffic control and why?

(Ein Internetanbieter kontrolliert den Datenverkehr seiner Kunden, indem er ihre DNS-Anforderungen überprüft und blockiert (i) wenn sie auf verbotene Domänen verweisen oder (ii) wenn die DNS-Anforderungen verschlüsselt sind und der Internetanbieter sie nicht entschlüsseln kann, sodass sie standardmäßig gelöscht werden . Welcher Mechanismus für verschlüsseltes DNS erschwert es dem Internetanbieter, diese Art der Datenverkehrssteuerung (engl. Traffic Control) durchzuführen, und warum?)

Aufgabe 4: TCP or UDP?

You are developing the online mode for a real-time game (could be a shooter, but also a real-time strategy game). In this setting, would you select TCP (Transmission Control Protocol) or UDP (User Datagram Protocol) for the communication between server and client (e.g., PC or home video game console)? Explain your choice.

(Sie entwickeln den Online-Modus für ein Echtzeit-Spiel – dies könnte ein Shooter sein, aber auch ein Echtzeitstrategiespiel. Würden Sie in einem solchen System TCP (Transmission Control Protocol) oder UDP (User Datagram Protocol) für die Kommunikation zwischen Server und dem Client (z. B. PC, Spielekonsole) verwenden? Begründen Sie Ihre Wahl.)

Aufgabe 5: client-centric monotonic read consistency

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?)

Aufgabe 6: Diffie-Hellman

Entities A and B wish to establish a secret key using the Diffie-Hellman protocol. The public information that A selects as the configuration of the system is n = 23 (modulo) and g = 3 (base). What is the secret key that will be derived if A and B pick values a = 3 and b = 2, respectively, as their private information, and how is this key derived?

(Die Entitäten A und B möchten einen geheimen Schlüssel unter Verwendung des Diffie-Hellman-Protokolls einrichten. Die öffentliche Information, die A als Konfiguration des Systems auswählt, ist n = 23 (Modulo) und g = 3 (Basis). Was ist der geheime Schlüssel, der abgeleitet wird, wenn A und B die Werte a = 3 bzw. b = 2 als private Informationen auswählen, und wie wird dieser Schlüssel abgeleitet?)

Aufgabe 7: sequential consistency

Consider the following Read/Write events. 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 sequentielle Konsistenz? Wenn ja, warum? Wenn nicht, erklären Sie warum und schlagen Sie eine Reihenfolge vor, die sequentielle Konsistenz bietet.)

Aufgabe 8: broker in SOA

The role of a broker in a Service-Oriented Architecture is optional. Mention a problem that may appear if a broker does not exist.

(Die Rolle eines Brokers in einer Service-orientierten Architektur ist optional. Erwähnen Sie ein Problem, das auftreten kann, wenn kein Broker vorhanden ist.)

Aufgabe 9: why does DNS scale?

Despite the fact that the Domain Name System (DNS) has been originally deployed in the 1980s, when the number of objects in the Internet was way smaller than today, DNS still works very well. One reason for this is that DNS scales very well. Please explain how DNS achieves scalability.

(Obwohl das Domain Name System (DNS) bereits in den 1980er-Jahren entwickelt wurde, als die Anzahl an Objekten im Internet sehr viel kleiner war als heute, funktioniert DNS immer noch sehr gut. Ein Grund hierfür ist, dass DNS sehr gut skaliert. Erklären Sie, wie DNS Skalierbarkeit umsetzt.)

Aufgabe 10: Lamport's Logical Clocks

Lamport’s Logical Clocks: In the figure, you find three processes P1, P2, and P3, which each maintain a local counter (i.e., a logical clock). As you can see, the counters are incremented using different values. The processes exchange messages mx. Fill in the empty boxes with the correct values.

(Lamport’s logische Uhren: In der Abbildung finden Sie drei Prozesse P1, P2 und P3, welche jeweils über einen lokalen Zähler (d. h., eine logische Uhr) verfügen. Wie Sie sehen, werden die Zähler unterschiedlich inkrementiert. Die Prozesse tauschen Nachrichten mx aus. Füllen Sie die leeren Boxen mit den korrekten Werten.)

Aufgabe 11: greedy server placement algorithm

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 in Bezug 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 user to reach a location
(Latenz für einen Client einen Ort erreichen)

	L1	L2	L3
Client 1	10	150	20
Client 2	200	20	250
Client 3	100	10	30

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): L1, L2 or L3?
• Location of Server 2, selected at step 2 of the algorithm (Speicherort von Server 2, ausgewählt in Schritt 2 des Algorithmus): L1, L2 or L3?
• 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)): _______

(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.)

Aufgabe 12: PAXOS

PAXOS Algo: Wenn der "Proposer" nicht auf eine Mehrheit wartet was passiert dann?

Materialien

Neues Material hinzufügen

L

• Logicalclocks (1).png (details)