INSTRUCTIONS

• Be sure to follow the programming style guide.
• Also follow the testing guide!
• All code, documentation, test plans, etc. must be your own original work. You must also turn in a filled-out copy of the assignment cover page.

PURPOSE

This assignment is to simulate a distributed leader election algorithm. It will give you practice in programming a FIFO Queue and in developing a discrete event simulator, as well as exposure to distributed algorithms.

BACKGROUND One application of a FIFO Queue is in a discrete event simulator. A discrete event simulator simulates some physical system in which events happen at discrete times. The queue holds the future events to be simulated, in increasing order of their scheduled times of occurrence.

The simulator operates like this:

   Initialize the event queue with some initial events.
   As long as the event queue is not empty
        Get next event by dequeueing the event queue
        Handle event (change state of system appropriately)
        Enqueue newly generated events onto the event queue

To simulate this system:

• The events initially inserted into the list are wake up events, one per processor.

• When an event is chosen to be simulated, the state of that processor can change according to some rule (described below), and some message might be generated, also according to some rule (described below). The delivery of that message is an event that must be enqueued onto the event queue.

The particular algorithm we will simulate is a leader election algorithm. An intuitive description of the algorithm can be found here. At the end of the algorithm, exactly one processor knows it's the "leader". The transitions which take place at each processor, p_i (1 <= i <= n), are listed below. The ids at each processor are unchanging.

State of p_i:

• id = i
• status = {asleep, contending, won, lost}. Initially, status = asleep
• maxId, holds an id. Initially, maxId = i

   if (asleep) {          // no messages have been received yet
      status = contending;
      send id;            // to neighbor in clockwise direction
   }

   if (asleep) {          // no messages have been received yet
      status =  lost;
      maxId = x;
      send maxId;         // to neighbor in clockwise direction
   }
   else {
      if (x > maxId) {
         status =  lost;  // this processor is not the leader
         maxId = x;
         send maxId;      // to neighbor in clockwise direction
      }
      ELSE if (x == maxId) // correction:  ELSE added 3/24    
         status =  won;   // this processor is the leader
   }

PROGRAM REQUIREMENTS

You are to write a Java program that implements a discrete event simulator of this leader election algorithm on a ring. Your program should be modular and follow the principles of object oriented programming. Your simulator should not be aware of the algorithm it is simulating and should just process events as they are removed from the list.

Input:

• The number of processors in the ring, n.
• The distribution of the ids to the processors, given as a permutation of {1,2,...,n}.

• (If you want to implement an applet with a GUI, you are welcome to do so, but command line and text are also fine.) After each event is simulated, output a concise, yet human-friendly, description of the current state of the system (values of the status and maxId variables for each processor and the messages in transit on each communication link). You design the format for this.

IMPLEMENTATION REQUIREMENTS

• Implement the FIFO Queue with a dynamic array.
• Be sure your program runs on the CS department's Unix machines under jdk!

Due by 10:20 AM on Friday, March 26, 2004: Postponed to Wednesday, March 31!

• Turn in your code using the "turnin" program in the CS department Unix machines. (Turnin instructions available here.)
• Turn in the paper testing documentation and cover sheet.