Set 1

The deadline is November 2. We will go through the exercises and provide answers in the Thursday workshop sessions after the deadline.

Return your answers through Moodle as a single PDF file. Besides text, feel free to use figures, plots, scanned images and so on. Please return your answer set as a zip file on moodle and name it "username_DS16_SE1.zip". Please make sure that you follow the correct naming convention for submission.

1. Lamport clocks (1 point)

Lamport clocks can be used to agree on the global timing of a series of events. Simulate the algorithm for three processes A, B, and C. Present each process's local clocks given the following order of events:

Note: In the shorthand, snd means "sends message to", rcv means "receives message from", and ticks n means "advances local clock by n". Initially, the local clocks read A=19, B=40, C=28.

A snd B; B ticks 6; A ticks 3; B rcv A; B snd C; C ticks 4; C rcv B; C snd A; A ticks 16; A   rcv   C; C ticks 1

2. More Lamport clocks (2 points)

Prove the following two properties for Lamport's clocks:

1. If e → e' then L(e) < L(e')
2. L(e) < L(e') does not necessarily imply e → e'

3. Vector clocks (3 points)

Assume that when P2's clock was (4,5,1) it received a message from P1. The timestamp of the message was (8,3,2). Given that knowledge, answer the following questions:

1. What can we tell about the overall system?
2. What did P2 learn about the history of its colleagues?
3. Show that the relation Vj[i] <= Vi[i] always holds.
4. Show that e->e' => V(e) < V(e').
5. Solve Lamport clock problem in Q1. using vector clocks. Show how clocks of all processes will progress with the events.

4. Clock synchronization (2 points)

Consider a scenario with multiple wall clocks showing different times. Each clock is controlled by its own computer which is connected to the rest of the network as well as the Internet. How would you synchronize the individual clocks? The goal is to have them be as closely synchronized to each other as possible.

In your answer, consider the merits of Christian's algorithm, Berkeley algorithm, and NTP, and make a case for each of them why that algorithm would be the best one for this scenario. You can make additional assumptions about the operating environment, but please state them explicitly.

Set 2

The deadline is December 18.

Return your answers through Moodle as a single PDF file. Besides text, feel free to use figures, plots, scanned images and so on.

1. Byzantine generals (1p)

Are these Byzantine generals forming a quorum... or what?

a) Explain the problem of the Byzantine generals, and the algorithm proposed to solve their communication problem (as presented in lecture, see slides 17-18 http://www.cs.helsinki.fi/webfm_send/1262).

b) Give an example of an equivalent (i.e. similarly solvable) distributed system problem. (Preferably one that does not involve war.)

c) Explain what kind of problem quorum-based protocols are designed to solve.

d) What do these two topics have in common? What are their most relevant differences?

2. Two-phase commit (1p)

a) Describe the behaviour of the two-phase commit protocol in cases where

• the coordinator suffers a (temporary) crash,
• the participant suffers a (temporary) crash.

For what purposes are the different states needed?
Is the ACKNOWLEDGMENT message (see Wikipedia) necessary?

Assume a reliable data communication network (e.g., LAN). Would it be possible to simplify the protocol in this case?
Assume that the nodes are reliable but the data communication is unreliable. Would it be possible to simplify the protocol in this case?
A distributed agreement should not be possible in a case like this.However, it seems to work. Why? Or does it work?

3. Bully algorithm (1p)

a) Suppose that two members of a group detect the demise of the coordinator simultaneously and both decide to hold an election using the bully algorithm. What happens?

b) Does the bully algorithm work properly even if during the election the state of some member changes (present <=> absent)?

c) If the ring algorithm would be used in a) then we would have two ELECTION messages circulating simultaneously. Devise an improved algorithm which kills off superfluous messages.