EPaxos (7.1) established leaderless consensus is achievable, but its fast-quorum size — larger than a simple majority, article 7.1's honest trade-off — has a real practical cost that becomes more painful as cluster sizes grow, precisely mirroring article 7.2's Flexible Paxos observation that Multi-Paxos's own quorum requirements were stronger than necessary. Enrique Fynn, Alexey Bessani, and colleagues' Atlas (2018) applies Flexible Paxos's exact quorum-shrinking insight to the leaderless, dependency-graph setting EPaxos pioneered — combining two of this phase's earlier ideas (7.1's leaderlessness, 7.2's quorum flexibility) into a system that fixes a specific, well-documented weakness in EPaxos at larger cluster sizes.
The specific gap Atlas targets
EPaxos's fast quorum requirement (article 7.1: ⌊N/2⌋ + ⌊(f+1)/2⌋) grows relative to a simple majority as the cluster size increases — at larger N, the gap between EPaxos's fast-quorum size and a plain majority becomes proportionally more significant, meaning more of the cluster must be reachable and responsive for the fast path to succeed at all. This directly undercuts one of EPaxos's own selling points: at larger deployments (exactly where you'd most want the throughput and locality benefits article 7.1 described), the larger quorum requirement makes the fast path less resilient to node slowness or unavailability than Multi-Paxos's plain-majority fast path would be.
Atlas's fix: apply Flexible Paxos's insight to the leaderless setting
Atlas's core move: rather than accepting EPaxos's larger fast-quorum requirement as a fixed cost of leaderlessness, apply article 7.2's exact insight — quorums only need to guarantee the right intersection properties, not be maximally conservative majorities — to redesign the fast-quorum size specifically for the dependency-graph ordering setting. The result is a fast quorum close to a simple majority (rather than EPaxos's larger requirement), while still preserving the conflict-detection guarantee EPaxos's larger quorum existed to provide, by being more precise about exactly what intersection property is actually needed for safe dependency-set computation, rather than using EPaxos's more conservative, one-size-fits-all sizing.
Fig 1 — Atlas is a direct, explicit synthesis of two ideas already covered separately in this phase.
The synchronization mechanism: closing the gap safely
Shrinking the fast quorum reintroduces some risk of the exact scenario article 7.1 flagged — replicas with incomplete knowledge of recent conflicting commands, now with a smaller quorum less likely to collectively "know everything." Atlas compensates with an explicit background synchronization mechanism that periodically reconciles replicas' dependency knowledge, reducing the odds that a genuinely conflicting command gets missed by a too-small fast quorum, without requiring the larger EPaxos-style quorum on every single operation. This is a real, deliberate engineering trade — accept slightly more background reconciliation traffic, in exchange for smaller, more available fast quorums on the hot path.
FAQ
Does Atlas's synchronization mechanism add a new single point of failure?
No — the synchronization traffic is itself distributed across replicas (not routed through any one coordinator), consistent with EPaxos's original leaderless design goal; it's additional background communication, not a new centralized dependency.
Is Atlas strictly better than EPaxos?
At larger cluster sizes, generally yes on the specific dimension it targets (fast-quorum availability), but it adds the real complexity of the synchronization mechanism — consistent with this whole phase's pattern of genuine trade-offs rather than free upgrades. For small clusters where EPaxos's larger quorum isn't much bigger than a plain majority anyway, the benefit is correspondingly smaller.
Could Atlas's synchronization idea be applied back to plain EPaxos without the Flexible-Paxos quorum shrinking?
In principle, background reconciliation could reduce EPaxos's own slow-path frequency somewhat, but the quorum-shrinking is what delivers Atlas's primary, most significant benefit (fast-quorum availability at scale) — the synchronization mechanism exists specifically to make that shrinking safe, not as an independently valuable addition.
Takeaways
- Atlas (Fynn, Bessani et al., 2018) targets a specific, documented EPaxos weakness: fast-quorum size grows less favorably relative to a plain majority as cluster size increases.
- Its fix directly applies Flexible Paxos's quorum-intersection insight (7.2) to EPaxos's leaderless dependency-graph setting (7.1) — near-majority fast quorums instead of EPaxos's larger requirement.
- A background synchronization mechanism compensates for the shrunk quorum's higher risk of missing conflict information, trading some background traffic for better hot-path quorum availability.
- Atlas is the clearest example in this phase of modern Paxos ideas composing deliberately, rather than accumulating as isolated, unrelated variants.
References & further reading
- Enes, Fynn, Bessani et al. — State-Machine Replication for Planet-Scale Systems (Atlas, 2020 EuroSys) — the primary Atlas reference.
- cvam.sight — Consensus 7.1: EPaxos, Leaderless Consensus — the fast-quorum weakness Atlas addresses.
- cvam.sight — Consensus 7.2: Flexible Paxos — the quorum-intersection insight Atlas applies.