Three Approaches to Reducing Consensus Latency

Three representative ways to reduce wide-area round-trip cost are distributing coordination, using clocks, and narrowing the operations that require coordination.

The wide-area round trip as a floor

Replicas spread across regions must move information physically before they can agree on a single order. When inter-region round trips take tens to hundreds of milliseconds, each round trip in the commit path adds that delay to the latency floor. Protocols where one leader fixes the order, such as Raft and Multi-Paxos, charge that cost twice to a distant client. The client round trip to the leader stacks on top of the leader round trip for majority acknowledgement.

This post groups latency-reduction designs into three branches. They distribute the coordinating role, replace part of message exchange with synchronized clocks, or narrow the operations that need synchronous coordination. The grouping is an analytical framework rather than an exhaustive lower-bound result. The figures were checked against the evaluation scope of the cited papers as of 2026-09.

flowchart TD
    A["Wide-area round trip<br/>latency floor"] --> B["Remove the leader<br/>EPaxos*, Accord, Aspen"]
    A --> C["Trust the clock<br/>leader lease, Bodega, Tiga, K2"]
    A --> D["Narrow coordination<br/>epoch-based OCC, CRDT"]
    B --> B1["Cost<br/>slow path and recovery on conflict"]
    C --> C1["Cost<br/>clock error becomes a safety assumption"]
    D --> D1["Cost<br/>re-execution, or semantic conflict"]

Removing the leader

The first approach hands ordering authority to every replica. Egalitarian Paxos (EPaxos) starts from the fact that commands which do not touch each other need no forced execution order. Any replica commits a conflict-free command in two message delays. A client sends its request to the nearest replica, which removes one round trip to the leader.

sequenceDiagram
    participant C as Client
    participant N as Nearby replica
    participant Q as Fast-path quorum
    C->>N: Submit command
    N->>Q: Propose command and dependencies
    Q-->>N: Return dependencies
    N-->>C: Commit if conflict-free

This design makes the correctness proof difficult. The 2025 paper introducing EPaxos* states that the original protocol is complex, ambiguously specified, and carries nontrivial bugs. It supplies a simpler failure-recovery algorithm together with a rigorous proof (arXiv:2511.02743, published 2025-11).

The condition for tuning the fast-path failure bound e independently from the fault tolerance f generalizes to n ≥ max{2e+f-1, 2f+1}, which the paper shows is optimal. The original protocol targeted a single combination, n = 2f+1 with e = ⌈(f+1)/2⌉.

The Accord proposal, adopted as Apache Cassandra CEP-15, moves the design axis. It drops the requirement that dependency sets in quorum responses match exactly and orders transactions by hybrid logical clock timestamps. A leaderless design can therefore combine distributed coordination with clock-based ordering.

Conflict rate as the fork

The promise of a leaderless design is conditional. When two clients submit at nearly the same moment, replicas observe different arrival orders, and even correct nodes then diverge in their logs. The Aspen paper calls this fast path extremely fragile and states that divergence triggers costly recovery (arXiv:2601.03390, published 2026-01).

Aspen responds by absorbing divergence rather than preventing it. It raises the replica count to n = 3f + 2p + 1 so that up to p diverging replicas leave the rest on the fast path. It also assigns a tentative order using loosely synchronized clocks and network delay estimates.

In geo-distributed experiments it cut median request latency by 1.1x to 3.8x against state-of-the-art Byzantine fault tolerant protocols. Throughput stayed at up to 0.75x the peak of throughput-optimized designs.

Preserving the latency gain from removing the leader required extra replicas and clock-based pre-ordering. This approach pays off most at low conflict rates. As conflicts rise, it combines with clock-based tools or falls back to the slow path.

Trusting the clock

The second approach lets a clock establish some conditions that message exchange would otherwise prove. The oldest form is the leader lease. A time condition that gives one leader exclusive write authority removes the majority check attached to every read.

LeaseGuard builds this from the guarantees Raft elections already provide, with no separate lease data structure. The communication cost of a consistent read drops from one network round trip to zero (arXiv:2512.15659, published 2025-12). The same paper reports that write throughput rose from about 1,000 to about 10,000 writes per second once contention between reads and writes disappeared.

A new leader also allowed 99% of reads instantly right after failover. I covered the details of this design in Raft Leader Leases and Linearizable Reads.

Allowing more nodes to hold leases improves read locality further. Bodega grants leases to an arbitrary set of designated responder nodes, beyond a single leader or a fixed majority set. It calls this mechanism a roster lease (arXiv:2509.07158, published 2025-09). On real wide-area clusters under moderate write interference, it served average client read requests 5.6x to 13.1x faster than previous approaches.

Clocks also reduce delay across the whole commit path. Tiga has the coordinator attach a future timestamp to a transaction, and servers wait until that time before executing. This folds concurrency control and consensus into one round.

Most commits finish within one wide-area round trip, and a failed order prediction pushes that to 1.5 or 2. The paper reports 1.3x to 7.2x higher throughput and 1.4x to 4.6x lower latency against prior work (arXiv:2509.05759, published 2025-09).

In the same year K2 narrowed the time uncertainty bound with TrueTime-style clocks. It reports an order of magnitude higher geo-distributed transaction throughput (arXiv:2504.01460, published 2025-04).

Narrowing coordination

The third approach changes the unit of coordination. It can batch many requests into one epoch or let only operations supported by a convergent data type proceed without synchronous coordination.

Epoch-based optimistic concurrency control is the first variant. Minerva executes transactions into temporary local state and batches write sets by epoch. Raft agrees on a global epoch cut before deterministic conflict re-execution, and the client waits for that global commit.

The paper reports over 3x higher throughput in scalability experiments and 2.8x in a high-latency TPC-C simulation (arXiv:2602.21566, published 2026-02). I described the mechanism in Epoch-Based Optimistic Concurrency Control.

Conflict-free replicated data types (CRDTs) remove coordination for supported operations. Their merge rules make replicas converge despite different update arrival orders. They remove synchronous coordination from the local update path, while replication and merge work remain.

Two 2026 papers treat this merge as implicit and opaque to users. One answers with explicit merges driven by semantic dependencies (arXiv:2602.19231, published 2026-02). The other answers with executable Datalog specifications (arXiv:2605.31569, published 2026-05).

Narrowing synchronous coordination transfers to the application the duty of explaining which edit won and why. The CRDT article covers the algebraic structure.

Premises and selection

The first approach is sensitive to conflict rate. As conflicts grow more frequent the fast path drops to the slow path and dependency-graph cost rises, so the advantage over a leader-based design disappears.

A correctness flaw in EPaxos, published in 2013, was identified in 2019 (arXiv:1906.10917). A corrected and simplified version of the protocol appeared only in November 2025 (arXiv:2511.02743, checked 2026-09). That gap belongs in the picture too. Implementation complexity, unlike a latency gain, does not show up in a benchmark.

The second approach rests on the clock error bound actually holding. The LeaseGuard measurements ran on AWS TimeSync with error under 50µs. The Tiga evaluation reported error by synchronization method as 16.45ms for Ntpd, 4.54ms for Chrony, and 0.012ms for Huygens.

If a typical NTP setup in a private data center stays at millisecond error, lease periods and timestamp margins must grow accordingly. That brings back the latency the design set out to remove. Violating this assumption causes undetected correctness failures, beyond a performance loss.

The third approach also depends on conflicts and consistency requirements. Minerva batches per-request WAN coordination into epoch agreement, but clients still wait for global commit and re-execution grows with conflict rate. A CRDT avoids synchronous coordination only for operations covered by the data type's convergence semantics.

The premises are not independent when the branches are combined. Aspen, for example, removes the leader while using clock-based pre-ordering. Removing the leader therefore does not remove its clock assumptions.

Environments that must tolerate Byzantine faults belong on a separate axis, because their throughput ceiling is set elsewhere. I covered that in DAG-Based BFT Consensus and Leader-Based BFT.

Selection criteria

Three questions guide the choice. How often do concurrent writes affect the same key? Can the deployment quantify its clock error bound? Can the application define its own merge rule?

The last row matters. If the clock error bound is not an observed metric and the conflict rate has never been measured, choosing any branch leaves its premise unchecked. Keeping leader-based consensus and placing the leader near the client distribution is then the conservative operational choice.

Summary

Geo-distributed consensus includes wide-area communication delay, and this post compared three approaches to reducing it. Distributed coordination and clock-based designs move cost to conflict recovery and measured error bounds, while narrower coordination leaves re-execution or semantic conflict.

A CRDT does not run the same consensus faster; it changes the consistency model so selected operations avoid synchronous consensus. Choosing among these approaches requires measurements of conflict rate and clock uncertainty together with an explicit consistency requirement. If those inputs are unknown, measure leader placement and round-trip paths first.