CPSC 211, Sec 201-203
Spring 2004
Program 5: Discrete Event Simulation of a Distributed Algorithm in Java



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
We will focus on a particular physical system to simulate, a distributed computer system with a ring topology.

To simulate this system:

What are the rules by which processors change state and generate messages? These rules define a distributed algorithm, which specifies what the states of the processors are initially, and how they change when an event occurs (wake up or message delivery) and what messages are generated.

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, pi (1 <= i <= n), are listed below. The ids at each processor are unchanging.

State of pi:

When a wake up event occurs for pi:
   if (asleep) {          // no messages have been received yet
      status = contending;
      send id;            // to neighbor in clockwise direction
When pi receives a message containing x:
   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


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.





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