Articles 7.1-7.3 all relaxed a Multi-Paxos convenience assumption to improve latency or throughput. This article covers two variants optimizing a different axis entirely: resource cost. Lamport and Massa's Cheap Paxos (2004) asks whether you really need 2f+1 fully-provisioned nodes running all the time, or whether some of them can be much cheaper standby nodes that only activate on failure. Rodrigues, Liskov, and colleagues' Compartmentalized Paxos (2021, building on Corbett et al.'s Spanner-scale operational experience) asks a related but distinct question: does a single Paxos "role" have to be one physical process at all, or can its sub-responsibilities be split across independently-scalable components? Both are cost-engineering answers, not latency or throughput answers — genuinely useful for reading production deployment decisions in Phase 8-9 with the right lens.
Cheap Paxos: standby nodes that activate only on failure
Recall the sizing logic from article 5.2's FAQ: a crash-fault-tolerant cluster tolerating f failures needs 2f+1 nodes, all fully provisioned, all participating in every quorum decision, all the time — even though, in normal healthy operation, you only ever need f+1 of them to make progress (any majority). The other f nodes exist purely as insurance against the (hopefully rare) event of failures actually happening.
Cheap Paxos's structural fix: split the node set into f+1 full-cost, fully-provisioned main nodes that handle all normal-case operation, plus f much cheaper auxiliary nodes that sit mostly idle — not participating in the normal Phase 2 fast path at all — and only get activated, joining the active quorum, when a main node actually fails. This directly targets steady-state infrastructure cost: for the overwhelming majority of a system's operational lifetime (no failures happening), you're paying for f+1 full nodes instead of 2f+1, a substantial reduction for any reasonably large fault-tolerance target.
Fig 1 — Cheap Paxos trades a slightly slower failover (activating the auxiliary) for meaningfully lower steady-state cost.
Compartmentalized Paxos: splitting one role into scalable pieces
Compartmentalized Paxos targets a different cost dimension, motivated directly by operational experience running Paxos-based systems at genuinely large scale (the paper draws explicitly on Google Spanner-scale lessons). The observation: a "leader" or "acceptor" in the classical presentation (Phase 5) is treated as one monolithic role bundling several genuinely separable responsibilities — proposing values, persisting the log durably, broadcasting to followers, and handling client communication. At large scale, these responsibilities have very different resource profiles (log persistence is disk/IO-bound; broadcast fan-out is network-bound; client-facing request handling is CPU/connection-bound), and bundling them into one physical process means you can't scale any single bottlenecked responsibility independently of the others.
Compartmentalized Paxos's fix: decompose the traditionally-monolithic leader role into separately deployable, independently-scalable components — echoing article 5.1's original proposer/acceptor/learner role separation, but taken considerably further, splitting what Phase 5 treated as a single "leader" into multiple distinct services that can each be scaled to match its own specific bottleneck, rather than over-provisioning the whole bundled role to compensate for whichever single responsibility happens to be under the most load at a given time.
| Variant | Cost dimension optimized | Mechanism | Trade-off |
|---|---|---|---|
| Cheap Paxos | Steady-state node/infrastructure cost | f+1 full nodes + f cheap idle standbys | Slower failover while auxiliary catches up |
| Compartmentalized Paxos | Scaling bottlenecked sub-responsibilities independently | Decompose the monolithic leader role into separate scalable services | Real operational/deployment complexity — more moving parts |
FAQ
Is Cheap Paxos compatible with Flexible Paxos's asymmetric quorums (7.2)?
Conceptually, yes — both target cost/resource trade-offs from different angles (asymmetric quorum sizing vs. asymmetric node provisioning), and combining them is a reasonable direction, though it compounds the operational complexity each already introduces individually. This is a genuine, if under-explored in the original papers, combination point.
Does Compartmentalized Paxos change the underlying safety proof at all?
No — this is worth stating explicitly, echoing article 7.3's closing framing: decomposing the leader role into separate scalable services is an implementation/deployment architecture decision, not a change to the majority-overlap safety argument (article 3.3) itself. The decomposed services still collectively need to satisfy the same safety-critical invariants; they're just no longer required to live in one process.
Would a small startup ever need Cheap Paxos or Compartmentalized Paxos?
Rarely — both are optimizations that matter most at the specific scale where their targeted cost genuinely dominates (very large fault-tolerance targets for Cheap Paxos; genuinely bottlenecked sub-responsibilities at high request volume for Compartmentalized Paxos). For most deployments, the added operational complexity isn't worth it relative to standard Multi-Paxos or Raft — a useful, honest caveat this series has tried to apply consistently across every variant covered.
How does an idle auxiliary node in Cheap Paxos know when to activate?
Via the same failure-detection machinery this series built in article 2.4 — once the remaining main nodes suspect a peer has failed and needs replacement, they signal the standby auxiliary to join and begin catching up, a process directly analogous to article 4.2's leader-election trigger, just applied to bringing a previously-idle node into active participation rather than choosing a new leader among already-active nodes.
Takeaways
- Cheap Paxos (Lamport & Massa, 2004) splits nodes into
f+1full-cost mains andfcheap idle auxiliaries that only activate on failure — same fault-tolerance strength as standard Paxos, lower steady-state resource cost, at the price of slower failover. - Compartmentalized Paxos decomposes the traditionally-monolithic leader role into independently-scalable services (log persistence, broadcast, client handling) — motivated by real large-scale operational experience, letting each bottlenecked sub-responsibility scale on its own.
- Both variants optimize resource/deployment cost, a genuinely different axis from 7.1-7.3's latency/throughput focus — the modern Paxos family spans multiple, largely orthogonal optimization goals, not one single dimension.
- Neither changes the underlying majority-overlap safety proof (article 3.3) — both are cost-engineering layers on top of the same safety core every variant in this phase shares.
References & further reading
- Lamport & Massa — Cheap Paxos (2004) — the primary Cheap Paxos reference.
- Whittaker et al. — Scaling Replicated State Machines with Compartmentalization (2021) — the Compartmentalized Paxos paper.
- cvam.sight — Consensus 5.1: Paxos, History and the Problem — the original proposer/acceptor/learner role separation this article's compartmentalization extends.