These are additional exercises for Distributed Systems course. Returning them is not required for passing the course. Each of the exercises is worth 2 points and these will be added to your points from the essays and home exercises.

The deadline for returning them is November 30. We will go through the exercises and provide answers in the last two Thursday sessions of the course (4.12. and 11.12.)
Return your answers through Moodle as a single PDF file. Besides text, feel free to use figures, plots, scanned images and so on.

1. Lamport clocks

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' local clocks given the following order of events. 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=59, B=80, C=75.

A snd B; B ticks 6; B rcv A; B send C; C ticks 8; C rcv B; C snd A; A ticks 31; A rcv C

2. More Lamport clocks

Prove the following two properties for Lamport's clocks:

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

3. Vector clocks

Assume that when P2's clock was (5,4,2) it received a message from P1. The timestamp of the message was (7,3,5).

What can we tell about the overall system?
What did P2 learn about the history of its colleagues?
Show that the relation Vj[i] <= Vi[i] always holds.
Show that e->e' => V(e) < V(e').
 

4. Vector clocks with a twist

An interesting dilemma regarding Vector Clocks concerns year 2009's Exercise 4, task 3, section b). Please familiarize yourself with the task description before reading its model answer. Now,

Describe the full state of the given Bulletin Board System: processes, channels, and messages
Argue for or against the model answer. Is it correct? Under what circumstances should local events increment the vector clock, if any?
 

5. Real clocks

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.
 

6. Content distribution

Familiarize yourself with CoralCDN: http://www.coralcdn.org/.

Create a large file (maybe 10-20 MB) in your own ~/public_html/ directory here at the department (or use any other file of similar size). Perform the following retrievals and measure how long they take:

- Retrieve the file directly from the server
- Retrieve the file through Coral
- Retrieve the file again through Coral

What can you see from the results? When would Coral be useful?

The Linux shell commands time and wget might prove helpful.