School of Computer Science
Computer Science 308-575A
Fundamentals of Distributed Algorithms Project #1
Description: In this project, you are asked to build a parallel queueing network simulator on the network of workstations (Linux machines), implementing the Chandy-Misra knot detection algorithm. In this simulator the nodes and links of the queu
eing network are to be distributed over the nodes (machines), and a blocking algorithm is to be used. By this we mean that each node must execute the messages waiting for service at the node in strictly increasing time-stamp order. Hence if one of the inp
ut links is empty, the node must block until a message arrives on the empty link.
The scheduling discipline at each node is first-in first-out and the service time for each message at a node is exponential. You may assume that each message in the simulated system is of constant length and that it therefore takes a fixed time to transmi
t the message. This fixed time should be included as the service time on a link. It is up to you to decide on the mean of the distribution and to assign a reasonable fixed message length. You should initialize each queue with a fixed number of messages, a
nd allow them to circulate in the network. Notice this means that you are not creating messages according to some inter-arrival distribution, i.e. we have a closed queueing network. Closed queueing networks are useful for simulating computer systems.
The knot detection algorithm has its objective knots of empty queues. Once the existence of a knot is determined, you should develop an algorithm to actually break it. The Misra's article will help you here.
The implementation should be done using Unix machines and MPI. This project is due on Friday, March 16 by 5 p.m. No extensions will be given, so don't ask. I expect completely documented code as well as a well-written description
of the simulator. Please give a hard copy including the source to Jun
Wang (your T.A.) in his office (MC 107). You will demonstrate the program
to your TA-we will create a list of times for appointments.
Jun is located at firstname.lastname@example.org.
Here are a list of tutorials on mpi which should be of some help.
[ Academic Programs
] [ SOCS HOME ]