CS 515 Fall 2009 Project 1

Document Version V1.2

In this project, you will implement the synchronous GHS algorithm (lets call it distMST) we described in the class to construct a minimum spanning tree (MST) in a distributed manner. The tree will be constructed among a set of processes that may run on the same or different machines. You will develop a single "network-program" that will be executed N times, on the same or on different machines. N is the number of nodes in the network. In this way N processes will be created and each one will run your same program.

The processes, all together, will implement the synch-GHS algorithm and build a minimum spanning tree.

You will use a configuration file, that will be read initially when processes are created, and that tells how many processes are there, their IDs, the links between them and their weights, and so on.

You can designate a process as the root of the spanning tree. Then, you will make sure that the constructed minimum spanning tree is rooted at the node finally.

Over the spanning tree build, you should also send some traffic. You will demostrate that as well. For example, you can broadcast information from the root node to all other nodes, using the constructed minimum spanning tree.

You can/should use TCP connections among processes/nodes. If two processes are neighbors, they need to hava TCP connection established. The design of the program is up to you. For example, you will decide on the format of the configuration file(s). What we want is a final demo that demostrates us that the distributed MST can be constructed among a set of processes (that may be created on different machines) and it can be used to do someting in the network, like broadcasting.

Note that you are using a synchronous algorithm. But network is asynchrous.

You can write your program in Java, C or C++. You will make a detailed demo. You will also a write report.

You will work in teams. Each team will have 2-3 students.

Clarifications

More items will be added here when I receive questions from you and answer them.

While implementing the distMST algoritm we have seen, you need synchronization. But you don't need to implement a general purpose synchronizer. You can just use the requirements you have learned about a synronizer, and then use that knowledge to synchronize the operations of the distMST that requires synchronization. Hence you can include the synchronization as part of your implementation of distMST.
When you establish MST with distMST algorithm, the leader of the final single component will be the root of the tree. Hence you don't know in advance who will be the root. This may not be what you want. You may want the root a specific node (a designated node that you decide in the beginning). Then, after distMST has constructed the MST with the leader of last component as root, you will modify the tree (change parent-child relationships) in a distributed manner so that the designated node will become the root.
An example network and its components are shown here: MST