Tiga: Accelerating Geo-Distributed Transactions with Synchronized Clocks

Geo-replicated transactional databases such as Spanner split data into shards, replicate every shard across regions, and promise strictly serializable transactions on top. The usual construction stacks a concurrency control protocol (for example two-phase locking and commit) on a consensus protocol (for example Multi-Paxos), and the stack can cost several wide-area round trips (WRTTs) per commit. Earlier work that shortens it either spends CPU on dependency tracking and cycle detection, or reaches the optimum only in special cases such as commutative transactions.

This SOSP 2025 paper (Seoul), by Jinkun Geng and Shuai Mu (Stony Brook University), Anirudh Sivaraman (New York University) and Balaji Prabhakar (Stanford University), asks whether a fault-tolerant protocol can commit more transactions in 1 WRTT with less overhead. Its answer is Tiga, which orders transactions by future timestamps taken from synchronized clocks.

Four terms carry the paper. The headroom is the delay estimate added to a transaction's sending time to form its future timestamp. The fast path commits in 1 WRTT when a super quorum of replicas in every involved shard reports the same state, and the slow path adds a leader-driven log synchronization, for 1.5 to 2 WRTTs according to the abstract. Timestamp agreement is the exchange among shard leaders that settles one timestamp per transaction. Timestamp inversion is the pitfall in which timestamp ordering gives serializability but loses the real-time order that strict serializability demands.

Worth knowing first: linearizability versus strict serializability (the first is local to a shard, the second spans shards), Multi-Paxos from Paxos Made Simple, Calvin, whose deterministic ordering underlies the baseline Calvin+, and, for the network-ordering line the related work discusses, NOPaxos, Eris and Hydra. The paper's opening list of distributed OLTP systems also includes FoundationDB and TiDB. One pairing of mine, not the paper's: Raft is not cited, but it is the best-known leader-based log replication and sits close to Tiga's per-shard leaders.

• Consolidation. Concurrency control and consensus become one protocol, so a single round of messages both executes a transaction under strict serializability and replicates it. Each shard has 2f + 1 replicas, one of them the shard leader. The paper targets one-shot transactions, written as stored procedures with known read and write sets, and handles interactive ones by a decomposition technique described in its technical report.
• Proactive ordering. The coordinator stamps a transaction with its sending time plus a headroom: the largest measured one-way delay from the coordinator to a super quorum of replicas in each involved shard, plus a margin of 10 ms in the implementation. A super quorum is 1 + f + ⌈f/2⌉ replicas, the closest to the coordinator. Servers hold transactions in a priority queue and release them when the local clock passes the timestamp, so different arrival orders still yield one processing order.
• Conflict detection and execution. Two maps record, per key, the timestamp of the last released transaction, and a transaction that arrives with a smaller timestamp than a conflicting released one cannot enter the queue. A leader then raises its timestamp to its local clock, while a follower keeps it and waits for the leader's log synchronization. Leaders execute released transactions on multi-version data, and followers only append them to their log.
• The fast-path check. Fast replies carry the transaction's timestamp and an incremental XOR hash of the replica's log (160-bit SHA-1 per entry). A transaction fast-commits on a shard when the coordinator gets matching replies from a super quorum that includes the leader, and overall when all leaders used the same timestamp. As in Fast Paxos, a plain f + 1 quorum would not let a new leader tell committed from uncommitted transactions.
• Timestamp agreement. Leaders exchange their timestamps and take the maximum. If all match, it costs 0.5 WRTT. If a leader used the maximum but others did not, it waits one more 0.5 WRTT round before releasing, which avoids timestamp inversion (Figure 5 shows how three transactions break real-time order otherwise). If a leader used a smaller value, it revokes its execution, an internal undo that is not an application rollback, adopts the maximum and re-executes.
• Modes, slow path and recovery. When leaders share a region, as under full replication, agreement runs before execution (preventive) and costs only LAN latency. When no group of leaders sits within a threshold such as 10 ms, execution goes first and is checked afterwards (detective). A replicated view manager, which could be built on ZooKeeper, runs view changes and prefers co-located leaders. A new leader rebuilds its log from f + 1 replicas: the longest synchronized prefix plus entries held by ⌈f/2⌉ + 1 of them. Coordinators are stateless and checkpoints speed recovery.

Tiga is built on the Janus codebase, so the baselines share an RPC library and runtime. The authors added Tiga, Detock and Calvin+, a Calvin variant that swaps its Paxos layer for Nezha (a clock-based consensus protocol from some of the same authors, whose deadline-ordered multicast inspired Tiga) and so saves at least 1 WRTT. In total Tiga is compared with 8 baselines: 2PL+Paxos with wound-wait, OCC+Paxos, Tapir, Janus, Calvin+, Detock (changed to replicate synchronously across regions), NCC, and NCC+, which puts NCC on a Paxos layer because NCC alone tolerates no server failure. The code is open source.

MicroBench pre-populates each shard with 1 million key-value pairs, and each transaction increments 3 pairs on different shards, with keys drawn from a Zipfian distribution whose skew factor sets contention. TPC-C implements all 5 transaction types, with Payment and Order-Status as multi-shot. Experiments run on Google Cloud n2-standard-16 VMs, with data in 3 regions (South Carolina, Finland, Brazil), 2 coordinators in each, and 2 more coordinators in a remote region, Hong Kong. MicroBench uses 3 shards (9 servers) and TPC-C 6 shards (18 servers). Load is open-loop with a cap on outstanding transactions, and each test is repeated 5 times with the median reported. Further experiments sweep skew at fixed load, kill a leader, place leaders in different regions by rotating shard and replica ids, offset the headroom by up to 50 ms in either direction, and compare four clock setups: ntpd, chrony, Huygens and a deliberately unstable NTP source.

These are the authors' reported results.

• Headline, low contention. At skew factor 0.5, near each protocol's saturation, Tiga has 1.3× to 7.2× higher throughput and 1.4× to 4.6× lower median latency than all baselines. Table 1 gives maximum MicroBench throughput of 157.3K txns/s for Tiga, against 119.6K for Calvin+, 77.8K for Janus, 47.4K for NCC, 44.2K for Tapir, 34.5K for Detock, 22.9K for 2PL+Paxos and 21.8K for OCC+Paxos.
• Rising contention. With load fixed at 8K txns/s per coordinator and skew from 0.5 to 0.99, all baselines degrade except Calvin+, whose latency is 33% higher than Tiga's. For the MicroBench curves the authors blame graph computation for Janus and Detock, aborts from ordering mismatches for Tapir, and response time control for NCC.
• Remote region. In Hong Kong, where no servers are co-located, Janus, Tapir and Calvin+ need at least 2 WRTTs, while Tiga stays at 1 WRTT in both regions.
• TPC-C. Tiga reaches 21.6K txns/s, against 13.3K for Detock, 10.8K for Janus and 6.1K for Calvin+, while 2PL+Paxos, OCC+Paxos, Tapir and NCC stay between 0.86K and 2.1K. Against Detock, Janus and Calvin+ the authors report 1.6× to 3.5× higher throughput and 1.5× to 3.7× lower median latency.
• Leader failure. After a leader in one shard is killed at 80K txns/s overall, Tiga completes the global view change and returns to the same throughput in 3.8 seconds. Latency then rises because that shard has only f + 1 = 2 servers, so transactions touching it take the slow path, yet Hong Kong coordinators still beat the other protocols' latency in Figure 8.
• Separated leaders. Placing leaders in different regions lowers Tiga's maximum throughput by 9.7%, to 141.9K txns/s, and raises its median latency at that load by 34.0%. It still beats the baselines, and Calvin+ latency rises 162%. At high skew some transactions need an extra WRTT to roll back.
• Headroom. The estimated headroom is close to optimal. Smaller offsets raise rollbacks and latency, larger ones remove rollbacks but hold transactions longer, and using the sending time alone (0-Hdrm) is worst on both.
• Clocks. Reported synchronization errors are 0.012 ms for Huygens, 4.54 ms for chrony, 16.45 ms for ntpd and 62.55 ms for the unstable source, with throughput between 154.7K and 158.1K txns/s in all four. Latency is similar under chrony and Huygens, since cross-region delays run from 60 to 150 ms, higher under ntpd, and substantially higher with the unstable source.

The idea is attractive: it replaces a guess about arrival order with a guess about delay, and keeps a fallback when the guess fails. The paper concedes the following.

• Proactive ordering is best-effort. Packet loss, retransmission or clock error can make a transaction arrive after its timestamp, and the slow path then takes 1.5 to 2 WRTTs. Clocks also have no deterministic error bound (even Huygens can be arbitrarily off in theory), which is why timestamp agreement exists.
• Coordination moves rather than vanishes. Inter-leader agreement blocks conflicting transactions behind the head of the queue for 0.5 to 1 RTT, which the authors call costly when leaders are spread across regions under high contention. The separated-leaders results above show its size.
• Several refinements are open. The initial timestamp can make the fast path slower than the slow path when a simple quorum sits near the coordinator and the rest are far, so the authors suggest estimating both paths and choosing. Dynamic sharding is planned. A variant without inter-leader coordination, which needs a known clock error bound, is only sketched.

The following points are a reading of the evidence, not claims of the paper.

• The evaluated deployments favour the design. Every region holds a full copy of the data, so leaders are co-located and the preventive mode runs everywhere except the separation and headroom experiments, where leaders are moved apart by rotating ids. The partial replication assumed in the background section is not evaluated. With 3 replicas per shard (f = 1), the super quorum formula gives 3, so a fast commit needs every replica of every involved shard to answer. That is my arithmetic, not a statement of the paper.
• Failure handling is thinly measured. The one failure experiment kills one leader. A crashed or slow follower (which at f = 1 pushes its shard to the slow path), a coordinator failure, the view manager and network partitions are not measured, and the 3.8 seconds comes from that single scenario.
• "Most" and "rare" are not quantified in the text. The abstract says most transactions take the fast path, but the text gives no fast-path share, slow-path share or rollback rate. Those appear only in charts (commit rate in Figures 7 to 9, rollback rate in Figure 13), so they are not quoted here.
• The baselines are the authors' ports, with some tilt in both directions. All run in the Janus codebase, which keeps the comparison consistent, but Calvin+ (with Nezha), Detock (made synchronous), NCC+ and Tiga itself are the authors' own work. The NCC column is the variant without fault tolerance and with servers in one region, which favours NCC. The TPC-C results are also shaped by column-level conflicts from Janus's column-based storage, which the authors note and which likely hurts abort-based protocols most.
• Table 4 is a qualitative comparison. Its abort column says None for Tiga, but the related-work text says "few or no" aborts and footnote 2 limits abort-freedom to one-shot transactions with co-located leaders, while the evaluation reports rollbacks when leaders are separated. The WRTT counts are stated assumptions, and no production system such as Spanner or FoundationDB is measured, only research protocols re-implemented in one codebase.
• The correctness evidence lives outside the paper. The proofs are in a technical report and a TLA+ specification is linked, but the paper does not say what the specification checks or at what bounds. For a protocol whose subtle part is timestamp inversion, the paper itself offers the Figure 5 example and the argument of Section 3.6.
• Small inconsistencies. The introduction says blocking typically costs 0.5 WRTT, while the discussion says 0.5 to 1 RTT and Case-2 agreement takes a full WRTT, so the body figure is the safer one. Section 3.1 says Huygens errors are a few microseconds, while Table 3 reports 0.012 ms. Neither changes a conclusion.

• Dynamic sharding to turn multi-shard transactions into single-shard ones, which need no timestamp agreement, as the authors plan.
• Synchronization with a deterministic error bound, such as Spanner-style or Sundial-style hardware, which would let Tiga drop inter-leader agreement in the way the discussion sketches.
• A per-transaction choice between a super quorum and a simple quorum, based on the estimated latency of each path, as the discussion suggests.
• Measuring what the paper leaves open: partial replication with distant leaders, follower and partition failures, and the fast-path share and rollback rate under bursts and delay spikes.