Agreement Protocol Program #2

OK – well, let's try this one…. Today, we looked at some aspects of "agreement protocols/algorithms" and thus I think it is fair to ask you to implement one. We will limit the network model in order to simplify the implementation. We shall assume that we have 7 networked machines (you may/should use your machine simulation designed for previous assignments) total with 1-2 "faulty/malicious" machines/processes. We will also assume that our system is logically fully-connected. That is, any machine can communicate with any other machine directly (no star or ring network model!). Your program should create 7 "machines". Prior to creating the machines, the program should determine if either 1 or 2 of them are "faulty". So, we will always have either 1 or 2 faulty machines. Why did we limit it to 1 or 2? Why not allow 3???? We will treat a faulty process as one that provides a random value to all others when asked for its "vote". The program should randomly select the 1 or 2 faulty objects/threads prior to creation. The program will then randomly select one of the 7 objects/threads to be the initiator for the "vote". Initiating Process

The initiating process will select a value of either 0 or 1 and will send it to all other processes/threads. Obviously, if it is faulty, then it should randomly select its value for each individual message sent to the others. If it is not faulty, then it should select a specific value (0 or 1) and send said value to all others. NOTE – the constructor/method for your "machines" should accept adequate arguments to know whether or not it is the initiating process and/or whether or not it is faulty. Since we are using Java and we have a fully connected network model, it is necessary that all processes have a socket connection between them. That is, there should be 6 socket connections per process to ensure that direct, logical communication is correctly simulated.  

Algorithm

We have discussed the algorithm in class and you have access to Lamport's agreement protocol algorithm in the slides, text, and web. Make sure you understand it before implementing this program. OUTPUT

The program should indicate the initiating process and the number and identity of the faulty processes prior to initiating the algorithm. Each round should be CLEARLY identified as in ROUND # and all messages exchanged in that round should be indicated with output such as : Process X is sending Y to process Z

where X and Z represent machine IDs (0-6) and Y represents the value of 0 or 1.

When the algorithm terminates (read the algorithm description below as to how many rounds are necessary), the program should generate the final "vote"/status as it deems valid for each of the 7 machines. PLEASE REMEMBER that ALL of the non-faulty processes MUST agree upon the value sent by the initiator (assuming said initiating process is non-faulty) OR they should all agree on the same value. Please make sure that the initiating process is clearly indicated in the final output and that any faulty processes are also identified. An acceptable FINAL output (not including the round and message information) is indicated below for one random execution…

Process 0 0 Process 1 0 Process 2 0

Process 3 (initiator) 0

Process 4 (FAULTY) 1 Process 5 0 Process 6 (FAULTY) 0

Obviously, an initiator CAN BE faulty as well. Be careful on this.

Please do not use proprietary information to design these tests. As can be seen, in the previous output example) Processes 4 and 6 are faulty. Process 3 was the initiating process, AND all non-faulty processes are in agreement.  

Lamport Agreement Protocol Algorithm Formal Description

m = round # (0 is the initiation round) Algorithm LAP(0) ( i.e. m = 0 )

1. The initiator sends his value to every other process. 2. Each receiving process uses the value from the initiator as their current value.

Algorithm LAP(m), , m > 0

1. Each process sends its value to every other process excluding itself and the initiator.

2. For each i, let vi = value process i receives from every other process. 
Process i acts as the initiator in Algorithm OM(m-1) to send value vi to other n - 2 processes. 3. For each i, and each j ≠ i, let vj = value process i received from process j in step 2

4. Process i uses value of majority( v1, ..., vn-1 ) as its value for next round.

Majority(x1,x2,x3,….xn) is exactly what it sounds like- the majority vote (based upon input) of the votes received. Provide hardcopy of your code along with at least 4 sample executions.