Paxos Safety and Liveness Properties
You'll learn: How Paxos guarantees that consensus is always correct (safety) while also making progress under favorable conditions (liveness).
Core Guarantees
Paxos provides two fundamental types of guarantees about its behavior:
Safety means "nothing bad ever happens." In Paxos, safety guarantees that:
- Only a single value may be chosen (consensus)
- No two acceptors learn different chosen values
- A learner only learns values that were actually proposed
These properties hold under all conditions — even with network partitions, message loss, node crashes, or arbitrary message delays. Safety is never compromised, no matter how chaotic the system becomes.
Liveness means "something good eventually happens." In Paxos, liveness means the protocol eventually reaches consensus and terminates.
However, liveness requires synchrony assumptions: bounded message delays and nodes staying responsive. Without these, competing proposers can duel indefinitely—each interrupting the other's prepare phase before it completes acceptance. Think of two people trying to speak simultaneously, each stopping when the other starts, in an endless cycle.
The Trade-off
Paxos prioritizes safety over liveness. It's designed to never violate consensus correctness, even if that means sometimes making no progress at all. This aligns with the FLP impossibility result you've seen: no deterministic consensus algorithm can guarantee termination in a fully asynchronous system with even one crash failure.
In practice, systems using Paxos add mechanisms like leader election and timeouts to improve liveness, accepting that under extreme network conditions, progress might stall—but safety remains intact.
Key Takeaway: Paxos guarantees consensus safety unconditionally (never choosing multiple values) but only guarantees liveness (eventual progress) under synchrony assumptions—prioritizing correctness over availability when conditions deteriorate.