Question 5. Distributed Data Consistency (20 points)
All parts of this question refer to a Paxos instance with five agents: two proposers: A and B; three acceptors:
X, Y and Z. The following message sequences show the first few messages sending from the proposers.
Assume time proceeds from top to bottom and there is no chosen value at the beginning of the scenario. Both A and B try to propose a value following Paxos algorithm.
Proposer A sends a proposal with sequence number 2 at t1. Proposer B sends a proposal with sequence number 4 at t1 as well. A message with arrow end indicates it arrives at the destination. A message with dot end indicates a lost message. There is only lost messages shown in the sequence: the prepare(4) message sent from proposer B.
Note that not all messages are shown in the scenario. Some are left for questions.
1. [5 points] How would each acceptor responds to the received prepare message? Describe the response message with a brief explanation.
2. [4 points] Proposer A sends accept(n=2, v=5) at t5. To which acceptors would A sends this message and how each of them would respond?
3. [4 points] Proposer B sends accept(n=4, v=10) at t6. To which acceptors would B sends this message and how each of them would respond?
4. [2 points] Assume all accept messages arrive their destination agents by t8, does the system have a chosen value after t8? If yes, what is the chosen value? If no, explain why.
5. [3 points] What is the destination agent of the lost message? How would the destination agent respond if the message arrives? If the destination agent would respond differently depending on the arrival time, you should discuss different scenarios. If the destination agent would respond the same, explain why.
6. [2 points] Describe a way for both proposers to learn the chosen value if there is one; or a way to propose a new value to be chosen if there is no chosen value.
