EPaxos (7.1) and Atlas (7.5) both detect conflicts reactively — a command leader proposes a dependency set, and the fast quorum's replies either confirm it or reveal it was incomplete, triggering the slow path. Balegas, Duarte, and colleagues' Caesar (2017) asks whether ordering can be handled more proactively instead: rather than detecting after the fact that a proposed dependency set was wrong, have replicas explicitly reason about and agree on a proposed relative order before committing, reducing how often the expensive slow path actually triggers in practice, especially under higher contention (more commands genuinely conflicting with each other) than EPaxos's design was optimized for.
Ordering certificates: agree on order, not just conflicts
Caesar's mechanism centers on what the paper's lineage of ideas frames as an ordering certificate — when a command leader proposes a command, it also proposes a specific timestamp-like ordering value relative to recently-seen commands. Replicas, rather than simply confirming or expanding a dependency set (EPaxos's reactive approach), actively vote on whether that proposed ordering is acceptable given what they know, explicitly reasoning about relative order as a first-class part of the fast-path vote itself. This front-loads the ordering decision into the same round that would otherwise only be checking for missed conflicts, aiming to reduce how often a second round (the slow path) is genuinely needed.
Fig 1 — Caesar front-loads ordering reasoning into the fast-path vote, aiming to shrink the slow-path trigger rate under contention.
FAQ
Does Caesar still need EPaxos's larger fast-quorum size?
Caesar's quorum requirements are analyzed independently in its own paper rather than directly inheriting EPaxos's specific bound, but the underlying need — enough overlap to reliably vote on ordering — follows the same majority-overlap-derived logic (article 3.3) this entire phase traces back to, just computed for Caesar's specific certificate-voting mechanism rather than EPaxos's dependency-set mechanism.
Is Caesar strictly better than EPaxos under contention?
Better on the specific metric of slow-path trigger frequency under contention, at the cost of more per-vote work on every fast-path attempt (even ones that wouldn't have needed the slow path anyway) — the same "it depends on your workload" caveat this phase has applied consistently to every variant since article 7.2.
How does Caesar relate to Atlas — are they solving the same problem?
Related but distinct problems within EPaxos's design space: Atlas (7.5) shrinks the fast-quorum size (a Flexible-Paxos-style optimization); Caesar changes what information is exchanged and voted on within a quorum of whatever size, targeting the slow-path trigger rate specifically. In principle, the two ideas could be combined, though neither paper explicitly does so.
Takeaways
- Caesar (Balegas, Duarte et al., 2017) makes ordering decisions proactive rather than EPaxos's reactive conflict-detection — replicas vote on a proposed ordering certificate directly within the fast-path round.
- This targets a different metric than Atlas (7.5): not fast-quorum size, but slow-path trigger frequency under contention.
- The trade-off is workload-dependent: helps under higher contention (fewer slow-path fallbacks), adds overhead under low contention where EPaxos's simpler reactive check would have sufficed.
- Caesar and Atlas address related but distinct weaknesses in EPaxos's original design — a further illustration of this phase's composable, workload-specific optimization landscape.
References & further reading
- Arun, Peluso, Palmieri, Losa & Ravindran — Speeding Up Consensus by Chasing Fast Decisions (Caesar, 2017) — the primary Caesar reference.
- cvam.sight — Consensus 7.1: EPaxos, Leaderless Consensus — the reactive conflict-detection baseline Caesar makes proactive.
- cvam.sight — Consensus 7.5: Atlas — the related but distinct fast-quorum-size optimization.