ECE428- Homework 3 Solved

This assignment has 5 questions. The solutions must be typed, and submitted via Blackboard. However, the diagrams can be hand-drawn. You must acknowledge any sources used to arrive at your solutions, other than the course materials and textbook. All homework assignments are expected to be an individual work, so no collaborations are allowed

Question 1: Bully Algorithm
 

Consider the following modification of Bully algorithm: The initiating node (which is assumed not to fail) sends Election message only to the process with the highest id. If it does not get a response within a timeout, it sends Election message to the process with the second highest id. If after another timeout there is no response, it tries the process with the third highest id, and so on. If no higher numbered processes finally respond, it sends Coordinator message to all the lower-numbered processes.

 Complete the receive_message function (pseudocode is OK).
For the following parts, consider a distributed system with 8 processes that use a modified Bully algorithm for the leader election (including your solution to part (a)). The processes are called { P1, … ,P8 } with Pi having the PID i. Initially, all 8 processes are alive and P8 is the leader. Then, P8 fails, and P4 detects this, and initiates a new leader election. Assume the one-way message transmission time is T, and the timeout is set using knowledge of T.

(2 points) If no other node fails during the election run, how many total messages will be sent by all the processes in this election run?
(2 points) If no other node fails during the election run, how long will it take for the election to finish?
(2 points) Now assume that immediately after P4 detects P8’s failure, and initiates the election while P7 How many total messages will be sent by all processes in this election run?
(2 points) For the above scenario (where P7 fails right after P4 initiates the election upon detecting P8’s failure), how long will it take for the election to finish?
(4 points) What are the best and the worst-case turnaround times for Bully algorithm?
Question 2: Leader Election in a Ring
Consider a system of N processes, { P1,…, PN } arranged in a ring. Each process can only communicate to its ring successor, i.e., Pi can only send messages to Pi+1, and PN can only send messages to P1. We assume that each message is a pair of two 16-bit signed integers, i.e., they can take on values from –32768 to +32767. Assume that N ≤ 1000, and that there are no failures, and the communication channel delivers all messages correctly and exactly once.

(6 points) In this problem, each process has a 16-bit signed integer zinput xk (−32768 ≤ xk ≤ 32767), and an output variable yk, initialized to None (meaning undecided). A consensus algorithm is designed to calculate the maximum of all the input variables. In other words, at any point, the safety condition is, yk is either None, or yk = max i{1,...,N } xi . We will adapt the (first version of) ring-based election algorithm for this problem.A process Pi initiates the algorithm by sending (0, xi) to its ring successor (the 0 indicates this is a proposal message).
When a process Pj receives (0, x) from its ring predecessor:if x > xj, it forwards (0, x) to its successor.
if x < xj, it sends while replacing x with xj ,i.e., send (0, xj) to its successor.
if x = xj, it concludes that x = xj is the minimum value, sets yj = x and sends       (1, x) to its successor (the 1 indicating it is a decided message).
When a process Pj receives (1, x) and its yj is None, it sets yj = x and forwards (1, x) to its successor. If yj is not None, it ignores any received messages.
Note that multiple processes may initiate the algorithm simultaneously. Here is a Python implementation:

Does the algorithm described above guarantee safety condition for this problem? If yes, prove how. If not, (i) describe a scenario where safety is violated, and (ii) suggest any modifications to the algorithm that would guarantee the safety condition. You do not need to submit the code but you should have enough details in your modified algorithm for the grader to be able to implement the modification.

 

(4 points) In this problem, the inputs xk are all either 0 or 1. In this case, the output variable should be set to represent the majority value. In other words, if yk is not None, it must be 1 if the majority of processes have input 1, and 0 if the majority of processes have input 0, and 2 if there is a tie. Describe the algorithm for solving this problem (using either Python or a pseudocode). Assume that multiple processes may initiate your algorithm simultaneously.
Question 3: Consensus in Synchronous Systems
Consider the following algorithm:

A process Pi initiates the consensus by multicasting a Query message to the group.
Each process Pj unicasts a reply to Pi with message Value(xj) that includes its input.
After receiving replies from everyone or a timeout, Pi computes the minimum of all received values (including its own) yi = min xj and multicasts Decision(yi) to the group.
Assume that we operate in a synchronous system with the maximum one-way delay T for unicast message transmissions including any message processing times. Assume also that unicast channels are reliable.

(3 points) For the multicast of Query message, should R-multicast or B-multicast be            used, and why?
(2 points) What should the timeout value be?
(3 points) For the multicast of Decision message, should R-multicast or B-multicast be      used, and why?
(2 points) Assuming no failures, how long will the algorithm take to complete?
(3 points) This algorithm can lead to a safety failure while trying to achieve consensus.
                   Explain how it could happen. (For this part, consider possibility of processes failure.)       

Question 4: Understanding Paxos 
Consider a system implementing Paxos with two proposers, P1 and P2, and three acceptors, A1, A2, and A3. Assume that the input value for P1 is 1, and the input value for P2 is 2. Answer the following sub-question. (Both sub-questions are unrelated.)

( a)

Refer to the figure above. It shows the Prepare messages sent by P1 and P2. The responses ( if any) are not shown. Assume that no other proposals are initiated.

(1 point) Which processes will reply back to P1’s Prepare messages? ii. (1 point) Which processes will reply back to P2’s Prepare messages?
(2 points) Assuming each Promise message take exactly 2 time units, at what time will P1 send Accept messages? At what time will      P2 send Accept messages?
(2 points) Assuming each Accept message takes at least 1 time unit, and, as above, the Promise messages take exactly 2 time units, is it possible for the Proposal #1 to be accepted by a majority of acceptors? If no, explain why not. If yes, explain how.
(b) 

Refer to the figure above. P1 send Prepare messages at time 1, receives a Promise from all the acceptors, and sends Accept messages at time 6. Meanwhile, P2 sends Prepare message for         the proposal #2 at time 7.

(1 point) Which processes will reply to P2’s Prepare message?
(1 point) Which processes will accept P1’s proposal?
(1 point) Assuming each Promise response for P2’s Prepare message takes exactly 2 units, when will          P2 send Accept messages?
(1 point) Assuming P2 sends messages at the time stated in the previous parts, which processes will accept    P2’s proposal?
(1 point) What will be the value in P2’s proposal?
 

(3 points) Come up with a scenario where the consensus value changes by switching the arrival time of one message. Complete the diagram showing the timing of the promise messages from the acceptors to P2 and the accept messages from P2 back to the acceptors. (For this subpart any messages not shown on the original diagram must take at least one time unit, but have no other constraints.)
Question 5: Understanding Raft [14 points]
Consider a system of 5 processes, { P1, P2, P3, P4, P5 }, implementing the Raft’s algorithm for leader election. The one-way delay between each process is specified in the figure below. Assume that processing times can be ignored. Each of the question parts below assumes an independent scenario.

(1 point) Which server is the most likely to be elected leader in any term? No justification is necessary.
(4 points) Suppose P1 is the leader in term 1. It sends its last heartbeat at time 0 and then fails. Suppose, upon receiving the heartbeat, P2, P3, P4, and P5 set their timeout values to 50, 75, 100, and 150 ms, respectively. Who will each process vote for as the leader in term 2?
(2 points) Suppose now that P2, P3, P4, P5 set their timeout values to 150, 100, 75, and 50 ms, respectively. Who will each process vote for as the leader in term 2?
(2 points) Consider the processes logs below, where the number n denotes events logged in term n. Order the servers from the least up-to-date to the most up-to-date.
P1  1, 1, 1, 2, 2, 3, 3, 6

P2  1, 1, 1, 2, 2, 3, 3, 3, 4

P3  1, 1, 1, 2, 2, 3, 3, 3, 4, 4

P4  1, 1, 1, 2, 2, 3, 3, 6, 6

P5  1, 1, 1, 2, 2, 3, 3, 3, 4, 5