Programming Assignment VII

Due on Friday, April 16, 2004 @ 11pm

60 points

Leader Election in a Ring Network

In a distributed system, processes running on different networked computers must coordinate with each other to carry out some tasks. However, some programming tasks such as system initialization can only be done by exactly one process. One might dedicate a specific process to do this unique task; however, we also prefer to have a "uniform" structure so that every involved process would be essentially "identical." If this is the case, when that unique task is needed, all involved processes must elect a leader and let the leader perform the unique task. This is the concept of Leader Election or simply Election. This programming assignment tells you how a leader can be elected easily if all involved processes are run in a ring network and communicate with asynchronous channels.

An unidirectional ring network consists of n processes P₀, P₁, ..., P_n-1, and a channel from P_i and P_i+1 for 0 <= i < n-1 and a channel from P_n-1 to P₀ as shown below. Furthermore, suppose process P_i has a user identifier UID_i. The way of electing a leader from these n processes is actually very simple. We just elect the process with the largest UID! The problem is that each process only knows its own UID and its two neighbors. Thus, message passing is needed to find out if a process has the largest UID and let it continue with the unique task.

When the leader election procedure starts, every process sends its UID to its neighbor (i.e., from P_i to P_i+1 for 0 <= i < n-1, and from P_n-1 to P₀). Upon receiving a message, process P_i examines the content of the message:

If the message is larger than P_i's UID, P_i sends the received message to its neighbor.
If the message is smaller than P_i's UID, P_i does nothing and the message is ignored since it will not be circulated.
If the message is equal to P_i's UID, then P_i is the leader.

P_i repeats the above steps until it is blocked by the message wait operation because no more message is circulated. Otherwise, P_i is the leader.

Program Specification

Please note the following specifications. Without observing these rules, you will risk lower grades.

Each process is simulated with a thread like the following:
```
send its own UID; 
while (not done) {
     receive a message;
     compare the incoming message;
     kill it, or pass it to neighbor;
     or, announce "I am the leader" and I am done
}
```
Once a process finds out it is the leader, it starts to circulate the END message. Each non-leader process exits upon receiving this END message. When the END message comes back to the leader, the leader exits! Since process indices and UID's are all non-negative integers, you may choose -1 for the END message.
You program should not use any global variable, because in a distributed system there is no global data. More precisely, when a thread is created, it has all needed information as local data and should not access any global data (if there is any -- perhaps created by the main program). If you use any global variables in your program, you will receive no credit.
Between receiving an incoming message and sending it to a neighbor, you should use the Delay() method to generate a random delay.
In your program, you should only use asynchronous channels for building the communication links between threads.
Your programs should use 0, 1, 2, 3, ..., n-1 as user defined IDs for channel building. However, n should not be known by any thread. The UID of a process should be a random integer that is only known to a single thread, initially.
When it is created, a thread should receive i (the index in P_i), UID (a random integer generated and passed by the main program), its incoming channel, and its outgoing channel. All channels are built before threads are created. It is not difficult for process P_i to know the process IDs of its predecessor and successor. Since ThreadMentor channels are bi-directional, P_i can send its process ID to its neighbors, and, as a result, you do not have problem in printing out i-1 and i+1. After this information has been communicated with its neighbors, P_i starts the leader election computation.

Input and Output

There is no input file. The number of processes in a ring network should be taken from a command line argument. Name the executable of your program as prog7. It accepts one command line argument n, indicating the number of processes. You can assume the value of n is always larger than or equal to 3. If there is no command line argument, the default value is 5.

The output is very simple. The following is a sample.

Process 0 (UID 7369) started
    Process 2 (UID 3469) started
  Process 1 (UID 9742) started
     ..........
  Process 1 (UID 9742) sends 9742 to process 2
    Process 2 (UID 3469) sends 3469 to process 3
     ..........
  Process 1 (UID 9742) receives 7369 from process 0
    Process 2 (UID 3469) receives 9742 from process 1
     ..........
  Process 1 (UID 9742) kills incoming message 7369
    Process 2 (UID 3469) passes 9742 to process 1
     ..........
  Process 1 (UID 9742) receives 9742 from process 0
        ..........
  Process 1 (UID 9742) is the leader!
  Process 1 (UID 9742) starts to circulate END
     ..........
Process 0 (UID 7369) receives END and terminates
     ..........
  Process 1 (UID 9742) receives END and terminates
     ..........
FROM MAIN: Leader Election done.

Here are some notes:

Output from process i has an indentation of 2i spaces.
After a process receives an incoming message, the content of this message must be shown as follows:
```
Process 1 (UID 9742) receives 7369 from process 0
```
This shows process 1 with UID 9742 receives a message 7369 from process 0.
After a process sends a message to its neighbor, the following must be displayed:
```
Process 2 (UID 3469) sends 3469 to process 3
```
This shows process 2 with UID 3469 sends a message 3469 to its neighbor process 3.
A process may kill an incoming message:
```
Process 1 (UID 9742) kills incoming message 7369
```
This shows process 1 with UID 9741 kills the incoming message 7369.
Finally, once a leader is elected, your program must report this event as follows:
```
Process 1 (UID 9742) is the leader!
```
This shows process 1 is the leader.
Just a reminder: The UIDs must be generated within your program using random number generator. They cannot be part of the input or fixed in your program.

Submission Guidelines

All programs must be written in ANSI C or C++ using ThreadMentor.
Use the submit command to submit your work. You can submit as many times as you want, but only the last one will be graded. A makefile is required. Name your executable prog7.
I will use the following approach to compile and test your programs:
```
make              <-- make your program
prog7  10         <-- test your program
```
I may repeat the above procedure several times to see if your program performs correctly.
Your implementation should fulfill the program specification as stated. Any deviation from the specification will cause you to receive zero point.
You should aim for maximum parallelism. That is, implement the solution as stated and make sure all required threads will execute simultaneously. Without doing so, you risk very low grade.
No late submission will be graded.
My rule of grading is deduction based. I assume you always receive 100%. If you missed something, some points will be taken off based on the following rules. Read these rules carefully. Otherwise, you could receive low or very low grade. Click here to see how your program will be graded.
- Your programs must contain enough comments. Programs without comments or with insufficient comments will cost you 30%.
- For each program, the first piece should be a program header to identify yourself like this:
```
// ----------------------------------------------------------- 
// NAME : John Smith                         User ID: xxxxxxxx 
// DUE DATE : mm/dd/yyyy                                       
// PROGRAM ASSIGNMENT #                                        
// FILE NAME : xxxx.yyyy.zzzz (your unix file name)            
// PROGRAM PURPOSE :                                           
//    A couple of lines describing your program briefly        
// ----------------------------------------------------------- 
```
  For each function in your program, include a simple description like this:
```
// ----------------------------------------------------------- 
// FUNCTION  xxyyzz : (function name)                          
//     the purpose of this function                            
// PARAMETER USAGE :                                           
//    a list of all parameters and their meaning               
// FUNCTION CALLED :                                           
//    a list of functions that are called by this one          
// ----------------------------------------------------------- 
```
  Bad programming style and missing headers will cost you 30%.
- Submit a one-page description of your solution, discussing the following issues:
  - The logic of your program
  - Explain why your channel implementation works.
  - Show that this implementation is deadlock free.
  - Answer this following questions with convincing arguments:
    1. Why is the process, who receives a message that is equal to its UID, the leader?
    2. Why is the leader unique?
    3. Can we solve this problem using synchronous channels? In other words, does this algorithm work if all channels are synchronous? Prove your claim with a convincing argument. Or, provide a counter-example if it does not work.
  Name this file README rather than readme or Readme. Spell check this file; otherwise, you may risk lower grade.
  Missing README costs you 50%, poorly written README costs you 30%, and submitting a non-text file costs you 30%.
- Not-compile programs receive 0 point. By not-compile, I mean any reason that could cause an unsuccessful compilation, including missing files, incorrect filenames, syntax errors in your programs, incorrect makefile and so on. Double check your files before you submit, since I will not change your program to make it work.
- Compile-but-not-run programs receive no more than 50%.
  Compile-but-not-run means you have attempted to solve the problem to certain extent but you failed to make it working properly. A meaningless or vague program receives no credit even though it compiles successfully. Another common problem is that your makefile could successfully process your source files (i.e., compiled successfully); but, your makefile does not generate an executable file with the desired filename (i.e., prog7 in this assignment). If this happens, I will consider your submission as compile-but-not-run.
- Programs delivering incorrect result, incomplete result, or incompatible output receive no more than 70%.
- Use asynchronous channels only. You will receive no credit if you use any other synchronization primitives (i.e., mutex locks, semaphores and monitors).
- You will receive no credit if (1) you use global variables, (2) do not use random number generator to assign UIDs, and (3) process P_i knows more than the value of i and its UID.
- Each race condition, busy waiting, and deadlock costs you 10%.
- All deductions mentioned above are cumulative! This means that even though you have turned in a correct program, you could get very low grade. For example, if your submission does not have the necessary program and function headings (30% off), does not have enough comments (30% off), compiles but not runs correctly (30% off), and contains a race condition, then you will receive 80×(100-30-30-30-10)%=0 points.
- Programs submitted to wrong class and/or wrong sections will not be graded.
- Your submission should include the following files:
  1. File thread.h that contains all class definitions of your threads.
  2. File thread.cpp contains all class implementations of your threads.
  3. File thread-main.cpp contains the main program.
  4. File Makefile is a makefile that compiles the above three files to an executable file prog7. Since we will use Solaris to grade your programs, your makefile should make sure all paths are correct. Note also that without following this file structure your program is likely to fall into the compile-but-not-run category, and, as a result, you may get low grade. So, before submission, check if you have the proper file structure and correct makefile. Note that your Makefile should not activate the visualization system.
  5. File README.
- Always start early, because I will not grant any extension if your home machine, your phone line or the department machine crashes in the last minute.
Since the rules are all clearly stated above, no leniency will be given. So, if you have anything in doubt, please ask for clarifications.