Handling Conflicts and Preemption
What you'll learn: How Paxos resolves competition between multiple proposers trying to reach consensus at the same time.
The Problem of Competing Proposers
In Paxos, multiple proposers might simultaneously try to get different values accepted. Without a conflict resolution mechanism, the algorithm could deadlock or never converge. Paxos solves this elegantly through preemption based on proposal numbers.
How Preemption Works
Remember that each proposal has a globally unique, monotonically increasing number. When an acceptor receives a prepare request with proposal number n, it promises not to accept any proposals numbered lower than n. This is the key to conflict resolution.
Scenario: Proposer A starts with proposal number 10, while Proposer B simultaneously starts with proposal number 15.
- Acceptors receive both prepare requests
- They promise to ignore proposal 10 (the lower number)
- Proposer A's accept requests will be rejected
- Only Proposer B can proceed
If Proposer A later discovers its proposal failed, it must restart with a higher proposal number (say, 20) to preempt any ongoing proposals.
The Ordering Guarantee
Proposal numbers create a total ordering among all competing proposals. Higher numbers always win. This prevents indefinite conflicts but doesn't guarantee liveness—two proposers could keep preempting each other in a "duel" scenario (though this is rare and can be mitigated with randomized backoff).
Why This Matters
Preemption ensures safety (only one value gets chosen) while allowing the system to make progress even when proposers fail or compete. The acceptors don't need to coordinate with each other; they simply follow the rule: "always respect the highest proposal number seen."
Key Takeaway: Paxos handles conflicts through preemption: higher proposal numbers always override lower ones, ensuring that competing proposers don't cause inconsistency, though the preempted proposer must retry with a higher number.