1. "RPC" over SSH

Recall the warmup exercises from the second lecture week with ssh key management
and a first look at the Ukko cluster.
http://www.cs.helsinki.fi/en/compfac/high-performance-cluster-ukko
http://www.cs.helsinki.fi/ukko/hpc-report.txt

Select 4 nodes from the HPC report that are not reserved for research groups.

Use the parallel-ssh tool installed on the Ukko cluster nodes ('man
parallel-ssh') to connect to these 4 nodes and run the 'uptime' command in all
of them.

Notice how the responses of the different cluster nodes are (probably) not in
the same order as you put them in the hosts file. What could cause this, and
what do you expect would be the most likely explanation?
 

2. Causal and total ordering in multicast.

On the lectures we noted that while FIFO ordering is induced by causal
ordering, causal and total ordering do not induce each other.

a) Give examples to show that a message passing system which implements
causal ordering does not always deliver messages in total order, and a
system which implements total ordering does not always deliver messages in
causal order. The message passing system is not expected to fulfil any
other ordering requirements.

b) How would you implement a message passing system which fulfils a
"combined causal and total ordering"?
 

3. Mutual exclusion in a distributed system.

a) Provide a convincing argument (semiformal proof) that the
Ricart-Agrawala distributed mutual exclusion algorithm works correctly:
* M1: at most one process may execute in the critical section at a time
* M2: requests to enter the critical section eventually succeed
  (starvation not possible)
* M3: if the relation Ra -> Rb exists between the requests Ra and Rb
  then Ra is served first.

What can you say about the fault tolerance of the algorithm?

(The algorithm is described in the book (6.3) and on the lecture slides; we didn't actually get to it on Monday yet.)

b) Provide an example of a situation where the centralized algorithm does
not necessarily satisfy the requirement M3.

c) How could you improve the fault tolerance of the centralized model in
case of client and/or server crashes?
 

4. Three processes communicate exchanging messages. Each process Pi
maintains its own vector clock Vi. All messages have a timestamp t based
on the sender's clock; using t the receiver updates its own clock.

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

a) What did P2 learn about the history of its colleagues?
b) Show that the relation Vj[i] <= Vi[i] always holds.
c) Sketch an induction-based proof that e->e' => V(e) < V(e'). (A full formal
   proof is not required.)
 

5. You are consulting for a theoretical large academic organization
located in Hillville, which suffers from a chronic issue with the clocks
in the campus all showing different times. The main issue of your client
seems to be that lecturers and students arrive to lectures at different
times from coffee breaks, workrooms, study group meetings etc.

Explain to your client how clock synchronization works. Argue (for all
three scenarios) why your company's solution based on a) Christian's
algorithm, b) the Berkeley algorithm or c) NTP would solve the client's
problems better than the two other competing solutions. (You may forget to
mention particular strengths of competing solutions in your sales pitch here.)

For this task we assume that each wall clock is handled by a small
computer of its own; you can add further assumptions for the different
sales scenarios as needed.