TU Wien:Verteilte Systeme VO (Dustdar)/Pruefung 2023-03-02

Quorum

A distributed storage system with $N=6$ replica servers. The system receives requests by clients to read or write/update objects and uses a quorum-based protocol.

What's the minimum value that the write quorum can have to guarantee consistency?

> $N_{w}=4$

What's the minimum value that the read quorum can have to guarantee consistency, given the minimum write quorum?

> $N_{r}=3$

Now assume that the system receives 10 read requests and 30 write requests per second. Each such request translates to read or write operations on a number of replica servers, following the quorum-based protocol. A read operation on one replica costs 2 units, a write operation on one replica costs 1 unit.

What values should be picked for the read and write quorums to minimize cost and to guarantee consistency?

> $N_{w}=4$

> $N_{r}=3$

> Basically you calculate the cost for all possible quorums, here being ($N_{w}=4,N_{r}=3$) and for ($N_{w}=5,N_{r}=2$) and for ($N_{w}=6,N_{r}=1$) and pick the best one.

What's the overall minimum cost with that read and write quorum?

> 180 units per second

Stateful vs Stateless

You have to develop a weather app, running on a smartphone. The app extracts the device's location (GPS coordinates) and sends it to a backend application server. This server then queries the public API of a weather forecast provider to retrieve a forecast for the user's current location, and returns the forecast to the app. The app also sends to the application server anonymized data from the smartphone sensors, which are then forwarded to a database server for storage and further analysis.

Choose the correct answer

a. The application server should be stateful by definition, since it stores data submitted by the app permanently and across user sessions.

b. The application server can be stateless, since it does not need to store any state information in order to respond a request for a weather forecast.

c. The application server can be stateless, but the overhead per request will significantly increase compared to a stateful design.

d. The application server should be stateful, since it needs to store user authentication state across requests.

> Answer is b.

Transparency violations

A Linux operating system distribution is replicated in a number of mirror servers. A user accesses the distribution's web portal, where they are asked to select a mirror server to download the Linux distribution from a list of server URLs, such as http://server1.linux.org. As soon as the user clicks on one of the mirror servers, the download starts. If the mirror server the user selected is overloaded or if there are connectivity problems, the user receives the message "Download error." Explain which forms of transparency are violated and why?

> Answer

> Replication transparency is violated, since the user sees that there are multiple mirror servers.

> Failure transparency is also violated, because the user doesn't automatically get forwarded to a functioning server.

Cryptography

Consider the following public-key cryptosystem:

• 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 theses specific keys, as shown below. The modulus $n$ and the key $K^{+}$ are public information. $K^{-}$ is kept secret by the user.

• The following function is used for encryption and decryption: $E(K,m,n)=m^{K}\mod {n}$, where $K$ is the key, $m$ is 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.

• To produce the hash of a message, the following 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 hash of the message.

User A wishes to send a message to user B using this cryptosystem. This plaintext message is the integer $m=3$. The two users have the following keys: - User A: $K_{A}^{+}=7$ (public key), $K_{A}^{-}=3$ (private key), $n_{A}=33$ (modulus), - User B: $K_{B}^{+}=3$ (public key), $K_{B}^{-}=11$ (private key), $n_{B}=15$ (modulus).

Answer the following questions filling in the correct integer values: - If A wishes to send the message encrypted in order to ensure confidentiality, what is the ciphertext that B will receive?

> $3^{3}\mod {15}=12$

- If A wishes to assure B of the authenticity and integrity of the message, but not its confidentially, what is the value of the message signature that B will receive?

> $(3\mod {5})^{3}\mod {33}=27$

Clock Synchronisation

todo

Paxos

We use Paxos in order to find consensus in a distributed system made up of 3 acceptors and 1 proposer these are the only nodes in our system, but they may not be online at the same time, since the system is faulty.

Each acceptor has stored information about the last message ID it promised, and an accepted value:

• Acceptor 1: ID 5, Value "Red"
• Acceptor 2: ID 4, Value "Green"
• Acceptor 3: ID 4, Value "Green"

Is this an acceptable state in a valid Paxos run, i.e., can this state be reached if Paxos has run correctly? Explain your answer by showing a possible sequence of PREPARE, PROMISE, and ACCEPT messages sent by both the Acceptors and the Proposer during the Paxos run. If this is a valid state, show how such a message sequence can lead to this state. If this is an invalid state, in the message sequence clearly indicates the invalid message or the reason for the early termination of the execution. Please list all the relevant messages and also, indicate which of the nodes might have been offline at times during the Paxos run.

> Es ist kein gültiger Zustand, da folgende Nachrichten verschickt werden würden:

> PREPARE 4 von Proposer an Acceptor 2 und Acceptor 3

> (Acceptor 1 ist offline)

> PROMISE 4 von Acceptor 2 und Acceptor 3 an den Proposer

> (Proposer hat eine majority bekommen)

> ACCEPT 4 "Grün" vom Proposer an Acceptor 2 und Acceptor 3

> ACCEPT 4 von Acceptor 2 und Acceptor 3

> (Acceptor 1 geht wieder online)

> PREPARE 5

> PROMISE 5, accepted 4 "Grün" <== Ab hier würde man nicht mehr zu dem ungültigen Zustand kommen. Im Alternativfall, wo Acceptor 2 und Acceptor 3 offline gegangen sind, würde der Proposer keine Mehrheit bekommen, und somit nicht weiter machen.

Cloud Computing Service Models

For each of the following two examples, name the Cloud Computing service model that characterizes it.

1. A collaborative online spreadsheet editing system.
2. A Cloud provider offers a stack including an http server and the libraries and runtime environment to deploy web services written in Python

> 1. Cloud Software as a Service

> 2. Cloud Platform as a Service