Every time you send a message, transfer money, or save a document to the cloud, you're relying on a mathematical guarantee that emerged from Leslie Lamport's office in the 1990s. The Paxos consensus algorithm—named after a fictional Greek island's parliament—solves one of distributed computing's most fundamental problems: how can a group of unreliable machines agree on anything at all?

This isn't merely an academic question. Without consensus, distributed databases couldn't maintain consistency. Cloud services couldn't survive machine failures. The entire fabric of reliable networked computing would unravel. Yet Paxos remains notoriously difficult to understand, not because it's complicated, but because its simplicity emerges from deep necessity. Every message, every phase, every seemingly arbitrary rule exists because removing it would break something fundamental.

What follows is a rigorous derivation of Paxos from first principles. Rather than presenting the algorithm as a fait accompli and asking you to verify its correctness, we'll walk through why the protocol must take exactly the form it does. You'll see how the FLP impossibility result constrains our options, how each phase emerges inevitably from the requirements, and why the key invariants that guarantee safety aren't clever tricks but logical necessities. By the end, Paxos won't just be an algorithm you know—it will be an algorithm you could have invented yourself, given the same constraints and enough mathematical persistence.

Before deriving any protocol, we must specify precisely what problem we're solving. Consensus in distributed systems requires a collection of processes to agree on a single value from among the values they propose. This deceptively simple statement conceals three distinct requirements, each essential, each constraining our solution space in different ways.

Validity states that if a value is decided, it must have been proposed by some process. This seems obvious—we can't agree on values that came from nowhere—but it eliminates trivial solutions. A protocol that always decides "42" regardless of input would satisfy agreement but violate validity. This property ensures consensus has meaning: the decided value reflects actual participant input.

Agreement requires that no two correct processes decide differently. This is the core safety property. In a banking system, if one replica decides a transfer succeeded while another decides it failed, the system's consistency is destroyed. Agreement must hold unconditionally—not just when the network behaves well, but always, regardless of message delays, reorderings, or process failures.

Termination demands that every correct process eventually decides some value. This is the liveness property, and here's where distributed consensus becomes genuinely hard. The Fischer-Lynch-Paterson (FLP) impossibility theorem proves that in an asynchronous system where even one process may fail, no protocol can guarantee termination deterministically. This isn't a limitation of our cleverness—it's a mathematical impossibility.

The FLP result forces a critical design choice: we must either sacrifice safety for guaranteed liveness, sacrifice liveness for guaranteed safety, or introduce additional assumptions. Paxos takes the third path, achieving safety unconditionally while guaranteeing liveness only under partial synchrony—the assumption that the system eventually behaves synchronously for long enough to make progress. This means Paxos may stall during network partitions, but it will never produce inconsistent results. For most systems, this tradeoff is exactly right: temporary unavailability is recoverable, but data corruption is catastrophic.

Takeaway

Safety and liveness cannot both be guaranteed in asynchronous consensus—understanding this impossibility result reveals why Paxos prioritizes never producing wrong answers over always producing answers quickly.

Given our constraints, let's derive Paxos step by step. We need a process to emerge as a leader (called a proposer) that can drive a decision. But leaders can fail, so multiple processes might attempt leadership simultaneously. The protocol must handle this gracefully—and this requirement alone generates Paxos's characteristic structure.

Consider a naive approach: a proposer sends its value to all acceptors, and if a majority accepts, the value is decided. This fails immediately. If two proposers concurrently contact different majorities, we could get two different decisions. The insight that fixes this is ballot numbers—unique, ordered identifiers for proposal attempts. Acceptors track the highest ballot they've seen and reject proposals with lower ballots. This creates a logical ordering on proposal attempts.

But ballot numbers alone aren't sufficient. Suppose proposer A gets value X accepted by a majority, then fails. Proposer B, unaware of X, starts a new ballot and proposes Y. If acceptors simply accept the highest ballot, B could get Y decided, violating agreement. This is why Paxos has two phases. In Phase 1 (Prepare), a proposer announces its ballot and asks acceptors what they've already accepted. If any acceptor has accepted a value, the proposer must adopt it. In Phase 2 (Accept), the proposer sends its (possibly adopted) value to acceptors.

The two-phase structure emerges from a fundamental requirement: before proposing a new value, we must ensure no conflicting value has already been chosen. Phase 1's query accomplishes this. If a majority responds to our Prepare without having accepted anything, we're free to propose any value. If some acceptor has accepted a value, we must continue that value—because that value might already be decided if other acceptors in some majority also accepted it.

The majority quorum requirement is equally necessary. Any two majorities intersect, so if value X is accepted by a majority M1, and later proposer B queries majority M2, at least one process in M2 belongs to M1 and will report X. This intersection property is the geometric foundation of Paxos's safety. Smaller quorums would allow non-intersecting groups, breaking agreement. Larger quorums would reduce availability without improving safety. Majorities are the minimal sufficient structure for the guarantees we need.

Takeaway

Paxos's two-phase structure isn't arbitrary complexity—it's the minimal mechanism required to ensure a new leader learns about potentially-decided values before proposing alternatives that would violate agreement.

Understanding Paxos deeply requires grasping its key invariants—properties that, once established, guarantee safety holds forever. The central invariant is this: if a value v is chosen in ballot b, then for all ballots b' > b, any proposal in ballot b' must be for value v. This single statement, proven inductively, ensures agreement.

The proof proceeds by analyzing what happens when a proposer completes Phase 1 for ballot b' > b. It receives responses from some majority Q'. Since v was chosen in ballot b, some majority Q accepted (b, v). The intersection of Q and Q' is non-empty—call a process in this intersection process p. Process p accepted (b, v) and responded to the Phase 1 query for b'. Therefore, p's response includes its acceptance of v in ballot b (or a higher ballot). The proposer, following the protocol, must adopt this value.

What about progress? Here partial synchrony becomes essential. During asynchronous periods, multiple proposers might continuously preempt each other—proposer A starts ballot 1, proposer B starts ballot 2 before A finishes, A starts ballot 3 before B finishes, ad infinitum. This is the dueling proposers problem. Paxos doesn't prevent it; FLP tells us no protocol can. Instead, Paxos assumes that eventually some proposer will have enough uninterrupted time to complete both phases.

In practice, implementations add leader election mechanisms—typically using timeouts—to reduce the probability of dueling. But these are performance optimizations, not safety requirements. Even if leader election fails completely and proposers duel forever, Paxos never violates agreement. It simply stops making progress. This separation of concerns—unconditional safety, conditional liveness—is a hallmark of robust distributed algorithm design.

The final piece is understanding when a value becomes decided. A value v is chosen when a majority of acceptors have accepted (b, v) for the same ballot b. Crucially, no single process necessarily knows when this happens at the moment it happens. An acceptor might accept a value, contributing to a majority, without realizing the majority has formed. This is why Paxos requires a learning mechanism—proposers who complete Phase 2 successfully can announce the decision, or acceptors can monitor each other. The chosen instant is a distributed fact that emerges from the collective state, not an event at any single location.

Takeaway

Paxos safety reduces to one invariant: any proposal in a higher ballot must carry forward any value that might already be chosen, and majority intersection guarantees this information can never be lost.

Paxos is often called difficult, but its difficulty is the difficulty of inevitability. Once you accept the consensus specification and the FLP impossibility result, the protocol's structure becomes not merely sensible but necessary. Two phases exist because fewer would allow conflicts. Majorities exist because smaller quorums wouldn't intersect. Ballot numbers exist because concurrent proposals need ordering.

This derivation-from-first-principles approach reveals something profound about distributed systems: the best protocols aren't invented through creativity but discovered through constraint. Lamport didn't design Paxos so much as uncover it, finding the minimal mechanism that satisfies the requirements without violating the impossibilities.

When you encounter Paxos variants—Multi-Paxos, Fast Paxos, Raft—you now have the foundation to evaluate them. Ask: what invariants do they maintain? What assumptions do they add? What tradeoffs do they make? The algorithm that powers the internet isn't magic. It's mathematics, elegant and inevitable, doing exactly what the constraints demand and nothing more.