A proposer sends Prepare(5) to a majority of acceptors. Two reply with promises; one reports it previously accepted value 'blue' at ballot 3, the other reports no previous acceptance. What value must the proposer use in its Phase 2 Accept message?
AAny value the proposer chooses, since ballot 5 supersedes ballot 3
B'blue', because it must use the value from the highest-numbered previously accepted proposal it discovered
CThe value that the majority of acceptors accepted, but only one reported 'blue' so it cannot be determined
DThe proposer's own preferred value, since it has not yet been committed by a majority
This is the heart of Paxos's safety guarantee. The proposer must adopt 'blue' in Phase 2. The reason: if 'blue' was accepted by some acceptor at ballot 3, it may have already been decided by a majority in that earlier round. By forcing any new proposer to re-propose the highest-ballot value it discovers, Paxos ensures that a decided value can never be superseded by a different one. If the proposer were free to use its own value, two different values could be decided in different rounds — violating the consensus invariant.
Question 2 Multiple Choice
A Paxos cluster of 5 nodes has 3 nodes simultaneously crash. The remaining 2 nodes attempt to run a new Paxos round. What happens?
AProgress continues because 2 nodes can still communicate and agree
BThe 2 remaining nodes can decide a value since they still form a quorum for a 3-node subset
CProgress is impossible because a majority (at least 3 out of 5) of acceptors cannot be reached, so neither Phase 1 nor Phase 2 can collect enough promises or acceptances
DPaxos automatically reconfigures to treat the 2 remaining nodes as a complete cluster
Paxos requires a majority (quorum) of acceptors to respond in both phases. With 5 nodes, a majority is at least 3. With only 2 nodes reachable, no quorum can be formed, so no proposal can collect enough promises (Phase 1) or acceptances (Phase 2). The system is stuck — it cannot make progress until at least one more node recovers. This is the liveness cost of Paxos: it tolerates up to ⌊(n-1)/2⌋ failures for a cluster of n nodes. With 5 nodes, it tolerates 2 failures, not 3.
Question 3 True / False
Paxos guarantees that if a value is decided (accepted by a majority), no future round can decide a different value, even if messages are lost or delayed.
TTrue
FFalse
Answer: True
This is Paxos's safety guarantee, and it is unconditional — it holds regardless of timing, message loss, or how many proposers are competing. The mechanism is Phase 1: any proposer with a higher ballot number must first poll a majority of acceptors. If a value was previously decided by a majority, at least one acceptor in any future quorum must have accepted it and will report it in Phase 1. The new proposer is then forced to re-propose that value. Safety is preserved even in the worst asynchronous scenarios that violate liveness.
Question 4 True / False
A Paxos system with a single designated proposer (leader) is expected to typically make progress, because competing proposers can no longer issue conflicting Prepare messages.
TTrue
FFalse
Answer: False
Leader election improves liveness in practice, but it does not guarantee progress. In an asynchronous network, no algorithm can guarantee both safety and liveness (the FLP impossibility result). A leader can crash or become network-partitioned, and detecting this reliably requires eventually correct failure detectors — which themselves cannot be perfectly guaranteed in asynchronous systems. Paxos guarantees safety always; it guarantees liveness only under favorable conditions (bounded message delays, correct failure detection). A leader helps by eliminating dueling proposers, but it does not solve the fundamental asynchrony problem.
Question 5 Short Answer
In Phase 2 of Paxos, why must a proposer use the value from the highest-numbered previously accepted proposal it discovered in Phase 1, rather than proposing its own preferred value?
Think about your answer, then reveal below.
Model answer: Because that value may have already been decided in a prior round. If an earlier round reached a majority acceptance, the decided value must propagate forward — any future decision must agree with it. By requiring the proposer to adopt and re-propose the highest-ballot previously-accepted value it discovers in Phase 1, Paxos ensures that if any value was decided before this round started, it will be the value decided again. This is the invariant that prevents two different values from ever being decided. If the proposer could freely use its own value, a second decision on a different value would be possible, violating consensus.
The safety proof relies entirely on this constraint. Phase 1 acts as a 'survey': what, if anything, has already been committed? If ballot n is the highest previously accepted ballot, then a majority of acceptors accepted that value at ballot n. Any quorum used in Phase 2 of the new proposal will overlap with that majority by at least one acceptor, who will always report the previously accepted value. The proposer's adoption rule then guarantees continuity.