Set 1

The deadline is October 11. 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.

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' 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 (2 points)

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 (2 points)

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. The Datacenter as a Computer (3 points)

Read through The Datacenter as a Computer by Barroso, Clidaras, and Hölzle. Based on what you have learned this far in this course and your previous experience, write a reflective essay (1-2 pages) about the content of the book. Discuss about the various topics the book covers, and try to fit them into the context of your previous studies and the context of this course, e.g. scalability, fault-tolerance, consistency etc.

Set 2

The deadline is December 6. We will go through the exercises and provide answers in the Thursday Workshop session 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.

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 on 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. (Preferrably 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. Clock synchronization (1p)

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.

3. Two-phase commit (1p)

a) Describe the behavior 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?

4. Bully algorithm (1p)

a) Suppose that two members of a group detect the demise of the coordinator simultaneuously 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.

5. DNS & Coral (2p)

a) DNS concepts

Explain the following concepts related to DNS

- Caching and TTL
- Stub resolver
- Iterative / recursive lookup
- Zone delegation
- Zone transfer
- Glue record

b) DNS resolving

You are running your application on our CS department computer. The
application sends to DNS the following names to be resolved

- www.cs.helsinki.fi
- cs.helsinki.fi
- fi
- cs

To which computer are these enquiries sent?
Which computers correspond to the IP addresses DNS returns?
("Which computer": what is the role of the computer, and in which domain is it located.)

c) DNS redirection

Experiment with DNS redirection using different lookup services and try to map the IP addresses to geographical locations. Use at least three locations for sending your queries. One of the locations should be here in the department, for the other two, select DNS lookup services on the web, such as http://network-tools.com/ (you need to find at least one additional service). Make lookups for the following domain names:

- www.google.com
- www.facebook.com
- www.apple.com
- cnn.com

d) Content distribution with Coral
Note: Because Coral seems to be down quite often these days you can choose to do either i or ii.

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

ii) How is a DNS entry updated? How is the update propagated, and what about caches?
What kinds of name conflicts or other surprises are possible and what are
avoided by design? How does DNS handle consistency, i.e. ensure that the user
gets the correct information? Explain the use of the TTL value of a DNS record
in this context.

6. Sum and substance (2p)

Based on the ten articles we have covered during the course write a summary (~2 pages) of how the ideas and concepts presented in the papers approach, tackle, handle, or ignore:

• scalability
• fault tolerance
• co-ordination (who should do what and when)
• consistency
• and security.