INSTRUCTIONS
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 queueWe will focus on a particular physical system to simulate, a distributed computer system with a ring topology.
To simulate this system:
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}:
if (asleep) { // no messages have been received yet status = contending; send id; // to neighbor in clockwise direction }When p_{i} 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 }
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:
IMPLEMENTATION REQUIREMENTS
Due by 10:20 AM on Friday, March 26, 2004: Postponed to Wednesday, March 31!