McGill University
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

Here are a list of tutorials on mpi which should be of some help.

Good luck.

[ Academic Programs ] [ SOCS HOME ]