Note 26.11.2012: The description is now complete. We have added some more specific returning instructions to weed out excessive creativity, see "standardization". :)

You may want to reuse your Homework 2 solution for this, unless it was unusable on Ukko or otherwise outside of the task specification.

Distributed decision-making (coordinator elections)

Implement an election algorithm from the book/slides on top of your checkpointing script from homework 2, so that 'number' is the assigned number of the node, and 'result' stores the current coordinator.  In other words, first run the coordinator election, then save state when the coordinator election is done.

The choices are the bully algorithm or the ring algorithm from slide 50 of chapter 3 (not to be confused with the other ring algorithms). If you're using 'nc' the ring-based algorithm may be easier to handle connection-wise (trying to listen to multiple connections from a shell script with 'nc' seems to provide extra challenge).

You are allowed to save the state at the same time as the coordinator is announced. The "right way", of course, would be to have the new coordinator tell everyone to save their state or equivalently have the coordinator start the Chandy-Lamport snapshot process (the choice of which of these different events triggers the snapshot does not affect scoring, as long as the coordinator is known at that point).

As before, the workshop tasks before homework 2 have various shell scripting examples and links that may be useful. You might also be interested in a look at the course page for Linux Fundamentals this autumn, but don't expect ready answers there either.

You need to include a document that gives the instructions on how to run your program and describes the execution process from start to completion.

Standardization

This segment provides requirements to simplify grading.

1) Configuring your script.

Nodes and ports should not be hardcoded. Your script should read four (or more; we'll test with four) Ukko nodes from a file called 'nodes' (in the current working directory). The file will have one address per line, e.g.

ukko572.hpc.cs.helsinki.fi
ukko411.hpc.cs.helsinki.fi
ukko587.hpc.cs.helsinki.fi
ukko406.hpc.cs.helsinki.fi

It should also read the port to connect to from a file called 'port' (in the current working directory), e.g. looking like this:

50001

You can return the configuration files with your answer, but we will supply our own configuration as described above and run the script with that.

It should then run the algorithm (Bully or Ring) on the specified nodes, connecting to the specified port. (If you run Bully and find out you need more ports than that, expand from this model creatively. You can consult with Ossi on the details if needed.)

To identify the numbers of the nodes, use the Ukko number. So node ukko572 has number 572, and the highest number from the list above is 587, i.e. ukko587 should end up as the coordinator in this case. (We don't care if you actually handle the Ukko numbers as numbers or if you find the largest Ukko node by alphabetical sort. As long as the largest Ukko number ends up as the coordinator.)

2) Starting your script.

We will start one script command per node, e.g. connect to the 4 Ukko nodes and run "./homework4.sh" on each of them (you can rename your script).  In other words, there will be no installation of additional software beyond what's on Ukko already, additional ssh connections, nc messages sent to the nodes etc from us - your script has to handle the rest.

3) Detailed example.

Where possible, we recommend that you follow this example, but sensible deviation from this point onwards is allowed - particularly, if you are implementing the Bully algorithm instead, some things below just do not apply.

Message format for election is E [nodes who have seen the election message] e.g.
E [ukko600.hpc.cs.helsinki.fi, ukko690.hpc.cs.helsinki.fi, ukko922.hpc.cs.helsinki.fi, ukko1008.hpc.cs.helsinki.fi]

where each node adds its name to the list.

Message format for annoucing the coordinator is C [full set of nodes] e.g.

C [ukko572.hpc.cs.helsinki.fi, ukko411.hpc.cs.helsinki.fi, ukko586.hpc.cs.helsinki.fi, ukko406.hpc.cs.helsinki.fi]

After which the node should print out the coordinator, e.g.

ukko586.hpc.cs.helsinki.fi is now the coordinator.

These are the instructions for the ring variant. Let's say we have to following configuration.

nodes
ukko572.hpc.cs.helsinki.fi
ukko411.hpc.cs.helsinki.fi
ukko586.hpc.cs.helsinki.fi
ukko406.hpc.cs.helsinki.fi

port
50001

At the beginning the programs reads the nodes and port files. As we need to form the ring all nodes will check name of the node on the next line except for the node on the last line which will check the one on the first line. Like this:

 _______      _______      _______      _______
|ukko572|--->|ukko411|--->|ukko586|--->|ukko406|
|_______|    |_______|    |_______|    |_______|
    ^                                       |
    |---------------------------------------|

The node whose name is listed on the first line starts the elections, other will wait and listen. The first node, ukko572, sends its election message with its address to next node, ukko411, e.g.

E [ukko572.hpc.cs.helsinki.fi]

When ukko411 receives the message it will add its address to the message and sends it to ukko586 and so on.
After the completion of the ring the message should look like this:

E [ukko572.hpc.cs.helsinki.fi, ukko411.hpc.cs.helsinki.fi, ukko586.hpc.cs.helsinki.fi, ukko406.hpc.cs.helsinki.fi]

When ukko572 receives the E message it will know that it has passed the full ring. It will then select the node with the largest (Ukko)number to be the new coordinator. Then it will save its state and send the coordinator message to ukko411 e.g.

C [ukko572.hpc.cs.helsinki.fi, ukko411.hpc.cs.helsinki.fi, ukko586.hpc.cs.helsinki.fi, ukko406.hpc.cs.helsinki.fi]

And print out

ukko586.hpc.cs.helsinki.fi is the new coordinator.

When ukko411 receives the message it will save its state and send the message to ukko586 and so on. The program completes when ukko572 receives the C message from ukko406, completing the circle.

The snapshot should include the E and C messages that the node has received, and it should show that it knows the coordinator so that e.g. ukko406's snaphot looks like this (note that it never received a full circle of election messages):

E="E [ukko572.hpc.cs.helsinki.fi, ukko411.hpc.cs.helsinki.fi, ukko586.hpc.cs.helsinki.fi]"
C="C [ukko572.hpc.cs.helsinki.fi, ukko411.hpc.cs.helsinki.fi, ukko586.hpc.cs.helsinki.fi, ukko406.hpc.cs.helsinki.fi]"
coordinator=ukko586.hpc.cs.helsinki.fi
hostname=ukko406
time="16:48:58 up 1 day,  3:03,  5 users,  load average: 0.66, 0.24, 0.18"

and ukko411's:

E="E [ukko572.hpc.cs.helsinki.fi]"
C="C [ukko572.hpc.cs.helsinki.fi, ukko411.hpc.cs.helsinki.fi, ukko586.hpc.cs.helsinki.fi, ukko406.hpc.cs.helsinki.fi]"
coordinator=ukko586.hpc.cs.helsinki.fi
hostname=ukko411
time="16:48:59 up 3 day,  1:05,  2 users,  load average: 0.87, 0.33, 0.11"
 

(Storing the messages is optional, but helps debugging. Also you may notice we ended up not using 'number' and 'result' exactly as is here, because we skipped straight to using Ukko numbers. But we sort of thought ahead in an attempt to minimize the need of afterward modifications to Homework 2.)