Question 4. Distributed Data Consistency (20 points)
Part 1- 4 of this question refer to the following message sequence scenario of a Paxos instance with five agents: two proposers A and B; three acceptors X, Y and Z. 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 has two proposals, with sequence number 2 and 7 respectively. Proposer B only has one proposal with sequence number 4. A message with arrow end indicates it is correctly sent. A message with dot end indicates a lost message, aiming for the nearest agent in the message direction. There are three lost messages in the scenario: the promise(2) message sent from acceptor Y to proposer A; the accept(n=4,v=10) message sent from proposer B to acceptor X; the response message from acceptor Z to proposer A’s prepare(7) message.
Note that not all messages are shown in the scenario. Some are left for questions.
For part 4 and part 5, a textual description is preferred; if you want to use diagram, please draw the diagram using a drawing software. Hand-drawn diagram will NOT be marked.
1. [2 points] Following Paxos algorithm, will proposer A proceed with the second phase of proposal 2 by sending accept message to available acceptors? If yes, what will be the content of the message and which acceptor(s) it will send the message to; if no, explain the reason.
2. [3 points] What are the response message of each acceptor to proposer A’s prepare(7) message?
3. [3 points] Proposer A wants to propose value 5. Now assume the response message for message prepare(7) from acceptor Z is lost, will proposer A proceed with the second phase by sending accept message to available acceptors? If yes, what will be the content of the message and which acceptor(s) it will send the message to; if no explain the reason.
4. [4 points] Assume proposer A sends prepare(7) message before t2, describe a scenario that will end up with value 5 from proper A to be chosen in proposal 7.
5. [8 points] This question is related with a Chubby lock service consists of five nodes: A, B, C, D, E. A Chubby service can only have one master at any time. A master has a lease that lasts for a few seconds. Once the lease expires, the system will elect a new master with a new lease. The master’s identity and the expire time of the lease are selected(chosen) using Paxos algorithm as a tuple value: (master, expire_time). All nodes in the cluster take all three roles: proposer, acceptor and learner in any Paxos process in the system. This means any node can make a proposal, accept a proposal or try to learn the chosen value. Assume that at t1, all nodes know the current master is A and its lease expires at t5. This is achieved through an accepted proposal: (n=5, v=(A, t5)). The proposal number is 5, and chosen value is (A,t5). Now assuming at t2, which is before t5, node C loses contact with node A and believes that A is dead. C plans to make a proposal to elect itself as the new master, with a lease expire time set to t7. Assume the communication between B and C, D, E are normal and there will be no message loss.
Describe the process C will use to elect itself. You description should include all messages with sender node, receiver node and detailed content. Indicate the sequence of messages as well.
