1. MapReduce with SSH

Modify the SSH-RPC solution from Exercise session 2 to recurse an additional level, i.e., the calling node "root" will execute the same script on three intermediary nodes "parents", which will each in turn call three "leaf" nodes. Use:

• ukko160.hpc.cs.helsinki.fi as the root node
• ukko161, ukko165, ukko169 as the parent nodes
• ukko162-ukko164, ukko166-ukko168, ukko170-ukko172 as the leaf nodes

Each node prints to standard output and the root node assembles all of the output to a file. Hints:

1. You will need ssh-agent, ssh-add and .bashrc for  ssh, e.g.,  ssh ukko161.hpc.cs.helsinki.fi "ssh ukko162.hpc.cs.helsinki.fi 'hostname'" must work without prompting for a password
2. One script file is sufficient: the model solution is 10 lines of code, no semicolons
3. For the root-parent-leaf mapping, one solution is to use a directory structure and symbolic links

One possibility for the output format:

MAP: ukko160 remotely calling ukko161.hpc.cs.helsinki.fi at ke 26.10.2011 14.00.51 +0300

MAP: ukko160 remotely calling ukko165.hpc.cs.helsinki.fi at ke 26.10.2011 14.00.51 +0300

MAP: ukko160 remotely calling ukko169.hpc.cs.helsinki.fi at ke 26.10.2011 14.00.51 +0300

REDUCE: ukko160 finishing at ke 26.10.2011 14.00.51 +030

[...]

MAP: ukko165 remotely calling ukko168.hpc.cs.helsinki.fi at ke 26.10.2011 14.00.52 +0300

REDUCE: ukko165 finishing at ke 26.10.2011 14.00.52 +0300

REDUCE: ukko166 finishing at ke 26.10.2011 14.00.52 +0300

REDUCE: ukko167 finishing at ke 26.10.2011 14.00.52 +0300

REDUCE: ukko168 finishing at ke 26.10.2011 14.00.52 +0300

2. Total ordering with Lamport Clocks

Background material:

• Section 5.2 Logical Clocks, T&vS 1st Ed.
• Section 6.2 Logical Clocks, T&vS 2nd Ed.

In group communication an often useful operation is a multicast service which implements total ordering: the message passing system delivers the messages to all members of the group (application components) in exactly the same order. For an example of the architecture of a message passing system, see Fig. 2-28, T&vS 1st Ed or Fig. 4-20, T&vS 2nd Ed (same picture). A rather simple algorithm for the message passing system is as follows:

1. the sender timestamps the message using the local time (Lamport clock)
2. the message is multicasted to the members of the group (the sender included)
3. the receiver puts the message into a local queue (in timestamp order) and multicasts an acknowledgement to all group members
4. the receiver delivers the queued message to the application when it is at the head of the queue and all the acknowledgments related with it have arrived.

Show that this algorithm implements total ordering, assuming that  all bilateral connections are reliable and order preserving (e.g., TCP connections).

From the application's point of view: can the designer assume that  the messages arrive in the order they are sent? Explain!

3. Formal proof of Lamport clocks

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'

This exercise has to be returned on paper at the beginning of your exercise session.