Why Paxos Is Safe, and Dueling Proposers

The safety argument in plain words

Suppose value v was chosen in ballot n, meaning a majority M1 accepted it. Any later proposer with ballot m > n must first collect promises from some majority M2. Because any two majorities intersect, at least one acceptor in M2 also accepted v in ballot n, and reports it. By induction over ballots, every proposal above n carries v, because the highest accepted ballot among the promises is always n or a later ballot that itself carried v. So once a value is chosen, every later ballot can only propose that same value: agreement holds regardless of crashes, delays or message loss. Liveness is a different story. Two proposers can keep pre-empting each other: P1 prepares ballot 1, P2 prepares 2 (so acceptors reject P1's accept), P1 retries with 3 (rejecting P2's accept), and so on forever. This duelling proposers livelock is the FLP limit appearing in practice.

Booking a meeting room by token

Each person who wants the room takes a higher token number and asks the majority of office managers to hold the room for that token. If two people keep taking higher tokens, each cancels the other's booking just before confirming. Nobody is double-booked (safe), but nobody gets the room either (no progress) until one person backs off.

The standard fix

Elect a distinguished proposer (a leader) and use randomised back-off before retrying. With one active proposer, ballots stop fighting. This is exactly the step from Basic Paxos to Multi-Paxos, and it is also why Raft builds everything around a single strong leader.

त्वरित जाँच: Which property guarantees that a later Paxos proposer discovers an already chosen value?

• Every acceptor stores every ballot ever seen
• Any two majorities of acceptors share at least one acceptor
• Ballot numbers are synchronised to wall-clock time
• Learners broadcast the chosen value to all proposers before phase 1