School of Computer Science Dr. Ying Zhou
COMP5349: Cloud Computing Sem. 1/2020
Week 13: Paxos Algorithm
Question 1: Paxos Concurrent Proposals and No Message Loss
28.05.2020
We use the same Paxos agents as in lecture 11: two proposers A and B, three acceptors X, Y and Z and a learner L. The message sequence between various agents is shown in 1.
Figure 1: Concurrent Proposal from Proposer A and B
a) How would acceptor X and Y respond to the accept message from proposer A
b) How would acceptor X respond to the prepare message from Proposer B? c) What would be the value in Proposal B¡¯s accept message?
d) How would all acceptors respond to proposer B¡¯s accept message?
1
Question 2: Paxos Concurrent Proposal with Message Loss
Again, we use the same Paxos agents as in lecture 11: two proposers A and B, three ac- ceptors X, Y and Z and a learner L. Assume that both proposers have completed phase 1 as described in lecture 11. The accept message sent from proposer A arrived success- fully in all acceptors. The accept message sent from proposer B with proposal:n=4,v=10, only reached acceptor X, the other two messages are lost. The message sequence is shown in Figure 2. The sequence also includes a second prepare message as described in part b).
Figure 2: Paxos with Concurrent Proposal and Mesage Loss
a) Does the system have any value chosen at this moment?
b) Now proposer A wants to make a new proposal with value 15. It chooses a proposal number 9 and sends a prepare message to all acceptors. How would each acceptor respond (not respond)?
c) Assuming all responses arrive at proposer A; following the algorithm, would the pro- poser continue with phase 2 by sending out an accept message? If so, what would be the proposal it requests to accept in this phase?
d) Assuming no message loss in phase 2, will there be a chosen value and what would be the chosen value?
2