Simulation Assignment 3 - Distributed Mutual Exclusion

Due Date

This assignment is due by 2:00 p.m. on Monday, 7 March at 2:00 p.m..

See the assignment turn-in page (last modified on 9 February 2004) for instructions on turning in your assignment.

A system administrator manages a network of n hosts (n > 1). Each host has a wireless transmitter to a beeper carried by the system administrator. Whenever any host detects an important event, it sends a brief message to the administrator's beeper.

The administrator's beeper can handle only one message at a time; if a second host begins transmitting before the first host stops transmitting, the second host's message is lost. Because the hosts have only transmitters, they do not know the state of the channel, nor can they receive transmissions from the beeper (all hosts are, however, connected by a reliable wired network).

To make sure that no transmissions are lost, the hosts coordinate among themselves using a distributed mutual exclusion algorithm that insures that at most one host is transmitting at a time. The algorithm is

Each host has the following declarations.

const unsigned N = N
const unsigned id = i
enum msg_type { request, ack, release }
struct msg { msg_type mt; unsigned ticket; unsigned sender }

unsigned ticket = 0
msg msgq[N] = { { ack, 0, 0 }, ... }

N is the total number of hosts; i is a value 0 <= i < N assigned such that each host has a value for id unique among all other host.

To transmit, a host executes the following:

broadcast(request)                                      (*)

bool waiting
do 
  waiting = false                                       (*)
  for j = 0; j < N and not waiting; j++                 (*)
    if j != id                                          (*)
      waiting = msgq[j] < msgq[id]		        (*)
while waiting                                           (*)

// Transmit the message.

broadcast(release)                                      (*)

The procedure broadcast() is

void broadcast(msg_type mt)
  msgq[id] = msg(mg, ticket, id)                        (*)
  ticket++;                                             (*)
  send(msgq[id])                                        (*)

The send(msg) procedure sends the given message to all hosts (except the sender).

The less than operator between two messages is defined as the lexicographic ordering over (ticket, sender); that is, m1 < m2 is true if and only if either

m1.ticket < m2.ticket or
m1.ticket = m2.ticket and m1.sender < m2.sender

Whenever a host receives a message from another host, it executes the following:

msg m = receive();                                      (*)
update(m)
switch m.mt of                                          (*)
  case request
    msgq[m.sender] = m                                  (*)
    send(m.sender, msg(ack, ticket, id))                (*)

  case release
    msgq[m.sender] = m                                  (*)

  case ack
    if msgq[m.sender].mt != request                     (*)
      msgq[m.sender] = m                                (*)

The procedure update() is

void update(msg m)
  if ticket < m.ticket                                  (*)
    ticket = m.ticket                                   (*)
  ticket++                                              (*)

The receive() procedure receives and returns a message sent from some other host. The send(unsigned, msg) procedure sends the given message to the host with the given id.

The switch statement is like a Java-Pascal-style statement with an implicit break at the end of each case branch; it is not like a C-C++-style statement where each case branch falls into the next

This algorithm, and the motivation behind it, are described in Time, Clocks, and the Ordering of Events in a Distributed System by Leslie Lamport, Communications of the ACM, July 1978 (vol. 21 no. 7), pages 558--565. This is possibly one of the ten - and certainly one of the twenty - most important papers in computing science.

The Problem

Determine the delay at a single host H between the time an important event occurs on H and the associated beeper message gets broadcast by H; delay is measured in ticks.

The following assumptions hold for this simulation:

The wired network connecting the hosts does not lose or corrupt messages, nor does it re-order messages sent from a single host. However, you may not assume that all hosts receive messages in the same order.
The time t in ticks between successive important events on any host is uniformly distributed between 0 and 1000, inclusive at both ends. Even though each host has the same distribution, the sequence of delays between important events will be different for each host.
Each executable statement in the protocol takes one tick; executable statements are marked with a (*). If a node is not executing the protocol code, it is sitting in a loop executing one statement per clock tick.
It takes five ticks for a message send-receive to occur, independent of the sending and receiving host and independent of broadcast or point-to-point transmission.

Input

Your simulation should accept two required command-line arguments:

$ dq-sim N T

The first argument N is the number of nodes in the system; the second argument T is the simulation duration in ticks. Assume that N > 1 and T > 49.

Your simulation may accept other inputs, but these must be optional inputs; it should be possible to run your simulation by supplying only the parameters N and T.

Output

Your simulation should write a single integer followed by a newline; the integer is the average delay between event and broadcast in ticks at one host (your choice of hosts).

If your simulation detects an illegal condition, such as invalid input parameters, it should print an error message to std-err and stop execution.

Grading

Each simulation will be graded independently of all other simulations for this assignment; there is no grade rationing.

Turn-In

You should turn-in your simulation code. You should also turn-in a brief three- or four-page report describing about your simulation. The report should describe

Your model. This is a page or so description of the problem analysis and the general structure of your simulation model.
Your experiments. This is a page or so describing the experiment inputs and parameters used, and how you varied them to conduct your experiments.
Your results. This is a page or so describing your experiment results and how you interpret them to answer the questions asked in the Problem Section above.

This report will be the basis for your presentation. The report should be in a generic format, such as plain text, PostScript, or Portable Document Format (pdf). Get in touch with me if you want to use something else.

You should include a makefile among the files you turn in, either for testing or to turn-in. Your makefile should understand two targets: go and clean. The go target should build your assignment. The clean target should delete all unnecessary files. Unnecessary files are any files generated by the makefile itself; such files include the .o files for C++, class files for Java, and any executables built by the makefile.

When you test or turn-in your project, the turn-in script runs (among other things) the following commands:

$ make clean

$ make go

You should make sure this works correctly.