WorksComputer Science
Optimizing Geo-replicated Deterministic Databases
Abstract
In transactional databases, achieving active-active replication among geo-distributed replicas is challenging due to the high coordination cost in ensuring the serializability of concurrent cross-node transactions. Deterministic concurrency control (DCC) has emerged as a promising alternative: it establishes a global order for a batch of transactions before execution and thereby amortizes this coordination cost across the batch. To better understand the performance characteristics of DCC, we conduct a theoretical analysis of traditional two-phase locking and optimistic concurrency control to account for geo-replication and introduce a model for DCC. We compare the three paradigms and identify the conditions under which DCC is advantageous. Guided by the insights from this analysis, we then present Quirinus, a DCC-based geo-replicated database that optimizes transaction execution through speculative execution, transaction reordering, integration of conflict-free replicated data types (CRDTs), and fast-path commit. Even without these optimizations, Quirinus achieves up to 6.2x the TPC-C throughput of Tiga under our configuration.
Introduction
Geo-replication is essential for globally scaled databases, as it provides extremely high availability to the applications that serve global users. Commonly, a geo-replicated OLTP database consists of transaction execution nodes and replicated storage nodes distributed across different data centers (DCs) for horizontal scalability and fault tolerance.
To provide serializable isolation, databases use concurrency control protocols such as two-phase locking (2PL) and optimistic concurrency control (OCC) to resolve conflicts and establish a serial transaction order. Under geo-replication, however, these protocols incur significant coordination overhead [59] because a transaction cannot commit until its writes have been durably and consistently replicated. This guarantee is typically provided through consensus replication [25, 38], which adds cross-DC communication to the commit path [58]. Because round-trip times (RTTs) between geo-distributed DCs can reach hundreds of milliseconds [4], this coordination lengthens transaction lifetimes. Both 2PL and OCC resolve conflicts at runtime for each transaction, so longer lifetimes increase exposure to conflicts [57]: 2PL transactions hold locks longer, whereas OCC transactions are more likely to abort and retry.
The support for an active-active architecture further complicates the design of concurrency control protocols because the storage layer must now accept both reads and writes at any replica, requiring multi-leader replication [1, 32, 62] instead of routing all requests to a designated leader and only using replicas for backups. Active-active offers better redundancy in the case of leader failures or a network partition between execution nodes and storage nodes [31, 61]. However, transactions may concurrently read and update different replicas, requiring execution nodes to coordinate to ensure serializability.
Many prior studies have proposed techniques to reduce the coordination overhead, such as consolidating atomic commitment and replication [13, 27, 34], using OCC with a fast commit path [12, 29, 32, 47], or relaxing consistency guarantees [5, 14, 26, 59]. While some can reduce commit latency to as low as one RTT under ideal, conflict-free conditions, they cannot eliminate multi-node concurrency control coordination as it is not possible to determine whether a transaction conflicts with another without communication.
An alternative is to amortize the coordination cost. When multiple operations require the same fixed-cost step, such as I/O or network communication, executing that step once for a batch amortizes the cost across the operations and improves throughput [19]. Transaction processing systems already use batching for replication and validation. However, transaction ordering cannot be batched when each transaction is ordered independently at runtime.
Deterministic concurrency control (DCC) brings batching to transaction ordering. It predetermines a global order for a batch of transactions before execution, thereby removing runtime order resolution while preserving serializability [2, 10, 11, 16, 20, 21, 28, 44, 52, 53, 56]. It thus removes the need for strongly consistent replication at the storage layer; instead, the replication moves to the execution layer that replicates transaction inputs and runs the same deterministic execution at each replica. By decoupling ordering from execution, DCC amortizes the ordering coordination cost across a batch instead of paying it for each transaction. However, this design introduces two costs: (1) every transaction incurs batching delay, even without contention; and (2) execution is repeated at each replica, making execution efficiency critical.
Table 1 summarizes the concurrency control and replication paradigms of representative OLTP systems with replication in mind. We observe that OCC has become a popular choice for geo-replication, while DCC is gaining traction in recent years. Although the strengths and weaknesses of these concurrency control paradigms are intuitively clear, we need to understand their advantageous regimes and trade-offs. Thus, we conduct a theoretical analysis that models and compares the commit latency and throughput of 2PL, OCC, and DCC. DCC is found to achieve favorable performance when the network RTT dominates execution time, whereas 2PL and OCC can suffer from unbounded latency under Replication coverage. Full means that every region stores every database partition; partial means that a shard or range may be placed only in selected regions. A full logical replica may still be partitioned across multiple nodes within a region.
| System | CC protocol | Replication type | Partial vs. full | Ordering mechanism | Notes |
| Spanner [8] | 2PL+MVCC | Leader–follower | Partial / configurable | Physical Timestamp | |
| CockroachDB [49] | Timestamp Ordering + MVCC | Leader–follower | Partial / configurable | Physical Timestamp | Hybrid concurrency control using timestamps and optimistic execution |
| TAPIR [59] | OCC | Leaderless | Partial | Physical Timestamp | |
| Mako [47] | OCC | Leader–follower | Partial | Local Time | Requires RDMA |
| GeoGauss [62] | OCC | Multi-leader | Full | Local Time | |
| Starry [61] | OCC | Multi-leader | Partial | Logical Clock | |
| Tiga [13] | Timestamp Ordering + OCC | Leader–follower | Partial or full | Logical Clock | |
| Minerva [32] | OCC + Deterministic | Multi-leader | Full | Logical Clock | Deterministic only for aborted transactions |
| Calvin [53] | Deterministic | Leader–follower | Full | Local Time | |
| SLOG [45] | Deterministic | Leader–follower | Full | Log Order | |
| Detock [37] | Deterministic | Leader–follower | Hybrid; optional full materialization | Dependency Graph | |
| Aria [28] | Deterministic | CC-only design | N/A | Logical Clock | |
| Harmony [24] | Deterministic | Blockchain | Full | Logical Clock | Block-level ordering |
| Quirinus | Deterministic | Multi-leader | Full | Logical Clock |
Table 1. OLTP Systems Overview
high contention. The replication speed and deterministic execution time are still the bottleneck for DCC, which requires optimization.
Guided by this analysis, we select four techniques to optimize DCC: speculative execution, transaction reordering, conflict-free replicated data types (CRDTs) [43, 46], and fast-path commit. We implement these techniques in Quirinus, a DCC-based database designed for active-active geo-replication.1
The core idea that allows these optimizations to be realized is to synchronize replica state only at batch boundaries, creating a consistent snapshot [9] between consecutive batches. This design allows transactions within a batch to be freely reordered to reduce the total execution cost, provided that all replicas derive the same deterministic order. For example, a transaction with a read–write dependency can instead read from the snapshot, allowing it to execute concurrently with the writer.
In summary, the contributions are as follows:
We present explanatory models of 2PL, OCC, and DCC response time and saturation throughput and use them to identify qualitative regimes of contention and network delay in which each paradigm is advantageous.
We present Quirinus, a database that utilizes DCC with optimizations that reduce the execution delay of DCC.
We evaluate the three paradigms with simulated geo-distributed deployments to test the model’s bottleneck predictions. Even without these optimizations, Quirinus achieves up to 6.2× the TPC-C throughput of Tiga [13] under our configuration.
The rest of this paper is organized as follows. Section 2 introduces the main paradigms of distributed concurrency control. Section 3 models the commit latency and throughput of these paradigms under geo-replication and compares their behavior under contention. Section 4 presents the design of Quirinus. Section 5 evaluates Quirinus on geo-distributed workloads. Section 6 discusses related work.
Distributed Concurrency Control
Concurrency control protocols are well-studied in database systems [2, 51, 57]. However, distribution and replication significantly complicate their design and implementation. We discuss three common paradigms of concurrency control in the context of active-active geo-replication.
Pessimistic Concurrency Control (PCC). PCC utilizes locks, such as the classical two-phase locking (2PL), to control access to shared data [17, 40]. A transaction must acquire all necessary locks before it can commit (otherwise, any read or write operation will block on the lock acquisition), and it holds these locks until the end of the transaction. In 2PL, read operations acquire shared locks and write operations acquire exclusive locks to allow concurrent reads but serialized writes. The lock is usually implemented at the replicated storage layer if leader-based replication is used, because if transactions only attempt to acquire locks on the single leader replica, the ownership can be easily resolved locally by the leader.
In an active-active setting, the difficulty lies in establishing a global lock order among the execution nodes through some form of centralized or distributed lock authority: a replicated lock manager, or a quorum/consensus layer that makes lock ownership globally visible [6, 15], adding another consensus round in addition to the consensus used for data replication. As a result, 2PL is the most sensitive of the three paradigms to network delay across replicas, since every lock acquisition requires cross-DC communication.
Optimistic Concurrency Control (OCC). OCC splits a transaction into read, validation, and write phases. Execution is never blocked, reads are served from the locally visible copies of the data, and the transaction may expose its writes only after validation succeeds [17, 40]. Validation checks whether the execution can be serialized with previously validated transactions, and invalid transactions are aborted and retried. The validation is typically conducted via a timestamp protocol to determine whether another transaction has an update to the values that the transaction is accessing.
OCC fits naturally with geo-distributed replication, because execution can proceed locally at one replica and global coordination can be deferred until commit so that the coordination cost is paid per transaction instead of per lock [30]. Compared to 2PL, OCC has become the more common paradigm for geo-distribution as its validation phase also offers more room for optimization, such as reducing the cost of 2PC as in TAPIR [59], epoch-based validation [29], and speculative commit [47].
Aborts and retries, however, remain expensive, as each one imposes additional cost. Because the timestamp must be globally consistent, replication prolongs the time that a transaction is exposed to conflict, thus increasing the abort probability in geo-replication.
Deterministic Concurrency Control (DCC). DCC avoids the runtime order resolution required by PCC and OCC. Instead of letting transactions execute concurrently and resolving conflicts at runtime, DCC builds a dependency graph statically before execution and then executes the transactions in this predetermined order [2].
When used with geo-replication, a database that uses a DCC protocol no longer requires the storage layer to handle replication; instead, the execution layer replicates the transaction inputs such as SQL queries or parameters to execution nodes in other DCs. The database can essentially be viewed as a replicated state machine, and states are maintained by local storage [41]. An active-active architecture can be easily achieved as long as the replication protocol is a multi-leader or leaderless one [23] that accepts requests at any replica. A DCC protocol such as Calvin [53] generally follows a three-stage pipeline, as shown in Figure 1:
Batching: Transactions are collected at each replica and grouped into batches. Each transaction is assigned a globally unique sequence number. The batch size is a parameter tuned for pipeline utilization, and each batch constitutes an epoch.
Replication: Once a batch has been collected, it is replicated to all replicas using a consensus protocol.
Deterministic Execution: Each replica executes the transactions in the order given by their pre-established sequence numbers.
Figure 1 also illustrates both the case where replication takes longer than execution and the case where execution takes longer than replication. Epoch is the first case where replication is the bottleneck (slower than the execution of epoch ), so the execution of epoch must wait for its replication to finish. The execution of epoch is, in turn, longer than the replication of epoch , so the execution of epoch must wait for the execution of epoch to finish.
Figure 1. Pipeline of a DCC protocol.
The replication step is bounded by the network RTT, which is the physical limit of the system. The batch size can be tuned based on the duration of the other stages. The execution step is therefore a primary target for optimization, as it must be fast enough to reach optimal throughput, while the replication step must also be optimized to increase the overall performance ceiling of the system.
Because contention no longer grows asymptotically with network latency, the coordination delay can be amortized across a batch of transactions, which is advantageous under geo-replication.
The downside of pre-ordering and batching is that the preprocessing delay must always be paid, even if there is no contention, which adds unavoidable latency to every transaction and may prolong the response time of short transactions that have few conflicts. Another common issue is the lack of support for interactive transactions, since the read and write keys must be declared in advance for sequencing [2].
Modeling Latency and Throughput
To better quantify the performance characteristics of these paradigms, we present an analytical model of the latency and throughput of the different concurrency control protocols under active-active geo-replication. We assume full database replication (no cross-DC reads), fault tolerance through consensus, and fixed-length transactions in which each transaction accesses the same number of records.
Preliminaries and Notation. We adapt the classic analytical model of transaction processing by Yu et al. [57] for the expected transaction response time (end-to-end latency). We then extend this model in three ways: adding coordination cost via cross-datacenter network delay (), modeling DCC response time and throughput, and deriving the theoretical saturation throughput (maximum stable throughput) of all CC paradigms. Table 2 summarizes the notation used in the rest of the paper.
Yu et al. give the response time of a transaction for 2PL:
and for OCC:
We simplify some parameters to focus on the impact of the coordination delay. The CPU and I/O times are combined into a single variable , where is the average per-granule access time (i.e., an in 2PL and in OCC). Following Yu’s model, the compute resource is treated as an open queue with arrival rate , served by CPUs, where is the time to process one transaction on a CPU. The compute utilization is therefore (ignoring locks). Under the fixed-length transaction assumption, each transaction sees expected conflicts under both 2PL and OCC, given concurrent in-flight transactions (by Little’s Law) and a per-pair conflict probability of .
For 2PL and OCC, the write set must be replicated before commit, and we assume for simplicity that the local commit time is negligible compared to , so that . For DCC, all replicas execute the same replicated transactions, so no coordination time is paid at commit.
Pessimistic Concurrency Control (2PL)
Modeling Latency. For locking-based PCC, lock-wait time is the main source of latency. A “blow-up” of lock wait may occur when transactions wait for a lock that is itself blocked by another transaction, producing a cascading effect. Yu et al. show that if the average number of lock contentions per transaction exceeds , the lock wait grows unbounded. This bound is obtained by equating two expressions for : one from the definition , and one from the construction of for a single lock wait. The result is quadratic in , because depends on itself, and a real, positive solution (a finite lock wait) exists only when .
| Symbol | Meaning |
| Number of granules (data objects) in the database | |
| Granules accessed per transaction (fixed length) | |
| Transaction arrival rate★ | |
| Number of CPUs★ | |
| Mean transaction response time | |
| Mean setup time per transaction | |
| Mean execution time (compute considered) | |
| Mean commit time including results replication | |
| Mean backoff time after abort | |
| Mean granule holding time | |
| Mean lock-holding time in the execution substate | |
| Unconditional lock-acquisition time, | |
| Per-lock-request contention probability | |
| Per-transaction contention, | |
| Mean lock-waiting time given contention | |
| Sum of mean lock-holding times on all granules | |
| Per-transaction abort probability (first & re-run) | |
| Mean per-state execution time (first & re-run) | |
| Mean re-execution time on rerun, | |
| Mean delay of RTT-scaled coordination among replicas, ★ | |
| Transaction compute demand, without considering compute resources★ | |
| Pairwise conflict probability under uniform access, ★ | |
| Saturated (maximum stable) throughput★ |
Table 2. Notation used in the analytical model. ★ denotes “knob” parameters that we focus on in the analysis.
Under geo-replication, every lock request needs at least one RTT to confirm whether the lock is granted [35], so the mean unconditional lock-acquisition time for each lock is approximately one RTT in the absence of contention. We therefore define . This extra delay lengthens how long each transaction holds its locks, which in turn raises the chance that other transactions collide (). Adding , we obtain the response time formula:
Following Yu et al.’s lock wait threshold derivation, we estimate the threshold after adding :
This means that the blow-up threshold is lowered as increases. See Appendix A for the detailed derivation.
Modeling Throughput. The maximum stable throughput in 2PL is determined by both the blow-up threshold and the compute resource
The compute-bound throughput is simply under an M/M/K queueing model in the absence of contention.
For the lock-wait blow-up bound, we first get when . Then, we substitute into the formula for ( with ) to get 2:
Using the definition of and multiplying by gives the mean number of contentions per transaction:
Replacing with and solving for :
Optimistic Concurrency Control
We assume that initial attempts and reruns have the same abort probability and compute demand, so and both use 3.
Modeling Latency. For OCC, the main source of overhead is aborts and retries. Although OCC does not block, a transaction is exposed to conflicts from its first read until the end of commit, and any conflicting commit during this window causes the transaction to abort. We assume that validation and write-set replication happen in the same round. Following the realistic pure-OCC approximation of Yu et al., the coordination delay extends the commit window and thus increases the abort probability for both the first run and any rerun:
Its linearization is:
The overall response time combines the coordination round for the first attempt and each retry:
Note that OCC has no blow-up threshold: the abort probability does not depend on itself, only on the number of concurrent transactions in the system, and adding does not change this linearity.
Modeling Throughput. Since OCC is bounded only by compute resources, the throughput is determined by the number of aborts and retries. Thus, we calculate the expected number of execution attempts per transaction. With the linearized approximation for the abort probability, we define , where is the abort coefficient after adding validation and replication coordination delay. The expected number of retries is ; including the first attempt, the expected compute demand is .
We then apply the M/M/K utilization condition . Substituting gives the maximum stable throughput:
Deterministic Concurrency Control
Modeling Latency. We extend the framework of Yu et al. to DCC and model a system that uses a Calvin-like distributed concurrency control protocol [53]. As discussed in § 2, DCC consists of a three-stage pipeline: batching, replication, and execution. We combine the batching and replication stages into a single “sequencing” queue that pays for coordination, since the batch interval is a tunable parameter that directly affects the replication throughput, as we discuss shortly. Execution is a separate queue that processes replicated transactions with parallel threads and a service time of . DCC performs no post-execution write-set replication. Finally, we assume that all replicas have identical transaction execution times.
We define the commit response time as:
Here, is the fixed time interval used to seal a batch. DCC can encounter a consensus delay blow-up when , because batches then arrive at the consensus layer faster than it can replicate them, causing the sequencing queue to grow without bound. We therefore assume for a stable system, with transactions still entering the execution queue at rate . Note that we do not use to denote the execution time, as we did for 2PL and OCC, because any computational wait time is absorbed into , leaving as the unconditional compute time required for a transaction.
Next, we derive , the mean waiting time when a transaction arrives in the stable state with transactions in the execution queue. Because of determinism, must wait for all previous transactions that conflict with , as well as their predecessors, to finish execution. We need to consider the longest dependency chain of , because all transactions in the chain are executed serially.
We model this by constructing a random directed acyclic graph (DAG) over the partially ordered set of transactions to represent the dependencies among transactions. Assume there are vertices, where each vertex is a transaction labeled with a . Each pair of vertices is connected independently with the same probability , and the edge always points from the higher to the lower . When , which has the highest , is inserted into the DAG, it again connects to each existing vertex with probability .
Define as the length of the longest dependency chain of and as the set that depends on; then we get:
Defining and , we apply a mean-field approximation [55] to obtain a closed-form expression. We replace each random inside the maximum by its mean to obtain a closed-form length. This approximation treats the longest path as the longest of the mean path lengths and assumes that the highest-index child is the most likely to lie on the longest path:
Then, for any transactions and any transaction with , we have:
Solving this mean-field recurrence gives (see Appendix § 10 for the detailed derivation):
Finally, the wait time is the maximum of the execution queue wait (the computation bound) and the dependency chain wait (the contention bound):
In the stable state, is in turn determined by Little’s Law as .
Modeling Throughput. Since DCC has neither reruns nor lock waits, its throughput is bounded only by the speeds of the sequencing queue and the execution queue. As noted above, if the batch interval is shorter than the replication delay, the sequencing throughput is ; otherwise, the sequencing queue is not a bottleneck and .
For the execution queue, we can reverse-engineer the stable . First, define , then:
A finite, positive pool requires a positive denominator, that is, . The saturated rate of the execution stage is therefore:
Finally, the overall saturated throughput is the minimum over the sequencing and execution stages:
Comparisons
In this section, we compare the advantageous regimes for coordination delays and contention levels among the three paradigms with respect to saturated throughput. We treat the other parameters as constants and focus on and only.
To compare throughput, we standardize the contention parameter to , as in § 3.3, and simplify the compute demand to for all paradigms (ignoring the slowdown in the execution queue beyond full utilization, since we are only interested in the throughput ceiling). This gives , and for OCC , , and . Substituting these into the throughput expressions gives:
For 2PL.
For large , using in the leading factor gives:
For OCC.
Next, we compare each pair of the paradigms.
OCC vs. DCC. When DCC is compute-bound:
whose only solutions are and . For contention-bound DCC,
Solving for gives:
For contention-bound DCC, OCC achieves higher saturated throughput only when ; the two tie at equality. For large , this threshold approaches from below. Thus, OCC wins only when , i.e., when the coordination delay is shorter than half the transaction’s compute time. When contention is low (), DCC achieves higher saturated throughput because it avoids retry work; their throughput limits coincide at . These comparisons assume that sequencing does not limit DCC throughput.
2PL vs. DCC. When DCC is compute-bound:
Taking the positive root for gives:
When , 2PL ties with DCC if . Otherwise, 2PL can reach the lock wait blow-up threshold even at , so DCC always wins.
When DCC is contention-bound:
Since cancels out and , we cannot find a non-negative that satisfies the equation. This means that 2PL is again always lower than DCC in the contention-bound regime, and the gap grows as increases.
2PL vs. OCC. Let:
Setting reduces this equation to the traditional comparison between 2PL and OCC: 2PL performs better when contention is low, while OCC performs better when contention is high, matching the results of Yu et al.
With a large , the vs. scaling means that OCC eventually outperforms 2PL for any fixed . The product is the useful regime parameter because it approximates the number of direct conflicts a transaction sees when the system tries to run transactions in parallel.
Summary. Figure 2 shows the theoretical saturated throughput and response times of the three paradigms. 2PL is sensitive to coordination delay because each lock acquisition requires cross-replica communication. OCC offers the lowest response time at low load, when queueing and retries are negligible, because it avoids DCC’s batching delay. When sequencing does not limit throughput, DCC achieves higher saturated throughput than OCC under low but nonzero contention. DCC also outperforms both OCC and 2PL when contention and coordination delay are high.

Figure 2. Analytical comparisons of CC paradigms with , , and negligible local commit time relative to cross-DC delay. We nondimensionalize and by to show the relative impact of coordination delay and contention. For DCC, we show only the execution-stage bound and set the batch interval to , the smallest value satisfying the stability requirement .
An important caveat is that, although we assume is the same for all paradigms, in practice is not a constant cost but depends heavily on the coordination protocol. This motivates the design of Quirinus, which optimizes replication and execution to minimize both the sequencing time and the execution delay.
Quirinus Design
To explore optimization opportunities for DCC based on the insights, we present Quirinus, a deterministic database that targets active-active, geo-replicated deployments. We highlight the following design features:
Lightweight Synchronization: Replica state is materialized only at consistent snapshots rather than at individual transactions, using a single synchronization barrier at the batch level. At the serializable isolation level, this guarantees serializable execution and identical snapshots across replicas for each completed batch. Synchronous coordination occurs only once on the critical path of a transaction, so that the coordination latency is amortized across the batch.
Speculative Execution: We show that the throughput of DCC can be bounded by compute power for both dependency-chain and non-conflicting transactions. By allowing transactions to execute speculatively against the snapshot before commit, we reduce the effective execution time , which improves throughput under low contention and reduces commit latency.
Conflict Avoidance: Because the dependency chain is another main constraint in DCC, we adopt conflict-avoidance techniques, such as adjustable isolation levels, commutative operators with CRDTs, and transaction reordering, to further reduce contention overhead.
Fast-path Commit: To further reduce commit latency for non-conflicting transactions, we allow some transactions, such as read-only transactions, to respond as successful without waiting for the synchronization barrier, provided that they are guaranteed to be valid.
Design Overview
Quirinus’s architecture is shown in Figure 3. The system is composed of multiple DCs; each DC contains disaggregated storage nodes and execution nodes. We consider a DC/executor to be a replica, rather than the storage nodes. Clients can submit transactions to any DC. We consider transactions to be stored procedures, and the replicated content consists of parameters. Once the consensus commits the batch, replicas execute transactions in the batch in the same deterministic order. A transaction is committed and its result is returned to the client as soon as it finishes execution on one of the replicas. By the guarantees of a fault-tolerant consensus protocol, if a batch is committed on one replica, it is guaranteed to be committed on all replicas, and the execution order is also guaranteed to be the same across replicas.
Figure 3. System architecture. Each DC is a replica with execution nodes and partitioned storage; clients submit transactions to any DC.
Quirinus is built upon our previous work Minerva [32], an epoch-based optimistic concurrency control protocol with a highly efficient asynchronous fault-tolerant replication protocol. The main difference between Quirinus and Minerva is that Minerva uses optimistic concurrency control as the primary ordering mechanism, whereas only aborted transactions use a deterministic re-execution path. In contrast, Quirinus’s deterministic ordering takes priority, and many of the optimizations aim to generate an order with fewer conflicts.
The workflow of Quirinus roughly follows the process of the DCC protocol described in § 2: when a transaction is submitted to a DC, it is placed into the current global batch using a leaderless, asynchronous replication protocol as in Minerva. The batch is sealed at fixed time intervals and replicated to all DCs.
To achieve active-active replication, Quirinus synchronizes replicas by aligning the batch and epoch boundaries with the deterministic execution order. The execution of each batch creates a snapshot of the database that is consistent across replicas, and the transactions in the next batch are always executed against the snapshot of the previous batch. Deterministic sequencing of transactions is achieved by two mechanisms. The first is the logical ordering across batches, which is provided by the consensus protocol used for replication, since consensus ensures a total order. The second is the internal ordering of transactions within a batch, for which we use a locally generated sequence number at each replica together with a predefined replica priority to ensure coordination-free ordering. Figure 4 illustrates the workflow.
Figure 4. Workflow of Quirinus, viewed as a state machine over snapshots. For each transaction: ① submitted to its local replica, ② executed speculatively and batched for replication, ③ replicated by consensus, ④ executed in deterministic order, and ⑤ returned to the client once the transaction is committed on a replica.
Within the epoch boundaries, there is a large optimization space. Inside a deterministic batch, we no longer need to account for the interleaving of transactions across batches, so we can reorder transactions freely to reduce conflicts during the execution, since no coordination is needed as long as the process remains deterministic. We next describe the key design features.
Speculative Execution
We first discuss the optimization during the batching phase, where transactions are executed speculatively against the latest snapshot as they arrive at the local replica. Building on the OCC execution of Minerva, we introduce a Silo-based protocol [54], which provides a local sequencing mechanism that serves as the deterministic order in the later execution phase rather than Minerva’s local sequence numbers. The result (the write set) of each speculative execution is stored in a per-epoch buffer and treated as tentative.
Speculative execution must be validated at the end of the batch against cross-replica read and write conflicts to ensure that the results are consistent with the deterministic execution order. This is done by building a conflict graph during the execution phase, where each speculatively executed transaction is a vertex and the edges represent read-write or write-write conflicts that cannot be serialized. When a conflict is detected, the buffered results of the affected transaction and all of its successors are discarded. During the final execution phase, the validated results are then used directly, which skips re-execution of those transactions. An example conflict graph is shown in Figure 5.
Figure 5. (a) Before replication, replicas execute transactions speculatively against the latest snapshot. (b) Dependencies during deterministic validation: (replica 1) and (replica 2) conflict; since replica 1 has priority, commits directly, while and its dependent successors, and , are discarded and rerun.
Speculative execution reduces the unavoidable final execution time before commit and improves the utilization of the execution queue when contention is low. This is effective only when compute is not the bottleneck, since the added re-execution overhead may otherwise offset the gain.
Variable Isolation Levels
During the execution phase, Quirinus supports four isolation levels [3]: Serializable (SER), Snapshot Isolation (SI), Read Committed (RC), and Read Uncommitted (RU). Each transaction declares its desired isolation level at submission time. A weaker isolation level has two benefits. First, it reduces the depth of the dependency chain, which improves throughput by increasing concurrency. Second, it allows more speculative results to remain valid, because the conflict graph contains fewer conflict edges.
We achieve this by relaxing read dependencies during both the cross-replica conflict edge construction and the deterministic dependency chain construction, and by reordering transactions. For each pair of transactions in the batch, Quirinus decides whether to add a conflict edge based on the stronger of the two isolation levels: a write-write edge is added only if at least one transaction requires SI or stronger, and a read-write edge is added only if the reading transaction requires SER. SI transactions are reordered to read from the snapshot rather than the write buffer, which effectively gives them an earlier order. For a write conflict between two SI transactions, the standard first-committer-wins rule is applied, which orders the transaction with the smaller sequence number first.
Because Quirinus only truly commits at epoch boundaries, RC transactions also read from the same snapshot; however, write-write conflicts are resolved by last-write-wins rather than by re-running the entire transaction, since RC allows the lost-update anomaly. Finally, RU transactions may read any value in the write buffer or the snapshot, and write conflicts between two RU transactions are likewise resolved by last-write-wins to establish a consistent final state. Algorithm 1 summarizes the rules for dependency edge construction with variable isolation levels.
Algorithm 1 Dependency Edge Construction with Variable Isolation Levels
Isolation strength: SER SI RC RU
Each carries an isolation level , read-set , write-set , and sequence number
function BuildDependencyEdges
for all ordered pairs in with do
if then
if or then
else
resolve by last-write-wins
if then
if then
else
reads from the snapshot
return
Transaction Reordering
In addition to the SI transactions that are reordered naturally, we can also reorder some SER transactions. We apply a second type of reordering based on the optimal validation scheme of Minerva.
In Minerva, because of the epoch-based commitment, the validation process of its OCC execution is also performed on a batch of transactions. To reduce the number of transactions that need to be aborted, it constructs a conflict graph to track the read-write and write-write conflicts among transactions and then applies a maximum-weight independent set (MWIS) search on the graph to find the minimal number of conflicting transactions to abort.
We adopt this mechanism and combine dependency-order determination with moving the optimal non-conflicting transaction set to the beginning of the batch, so that their speculative execution results can be used directly. This means that we reorder the transactions that do not have conflicts in the speculative execution so that they run earlier, maximizing the number of successful speculative transactions while still maintaining a deterministic execution order.
Figure 6 shows an example using the same conflict as in Figure 5. Under the default replica priority, on replica 1 is kept while on replica 2 loses the conflict, which discards its entire speculative subtree . This is wasteful, because is a leaf in the dependency graph, whereas is the root of a three-transaction subtree. Instead of always honoring replica priority, we reorder the transactions deterministically based on the number of dependent transactions. As shown in Figure 6, we can keep the group of (weight three) over (weight one).
Figure 6. Final dependency graph after reordering.
CRDTs Integration
CRDTs are a class of specially designed data structures that support commutative operations on data items [46]. By exposing CRDTs as a primitive data type in Quirinus, we allow transactions to use CRDT operations to reduce write conflicts and enable fast-path commits.
When a transaction accesses a CRDT item, it applies a CRDT operation to the item rather than reading or writing the value directly. CRDT operations are designed so that they can be applied in any order and still converge to the same final state across replicas. As a result, no write-write conflict edges are created among transactions that only write to CRDT items.
When implementing a transaction with a CRDT, we replace the read–modify–write pattern with blind CRDT updates and remove the corresponding read–write and write–write dependency edges between these transactions. Our implementation currently restricts CRDT transactions to SER for simplicity, although CRDTs can be combined with weaker isolation levels by adjusting the conflict-edge construction rules in Algorithm 1.
Algorithm 2 Counter update transaction with and without a CRDT.
Interface PN-Counter:
Increment(c, n) add n to counter c
Decrement(c, n) subtract n from counter c
Value(c) read the converged value of c
1: function TxWithoutCrdt(key, δ) read–modify–write
2: v ← Read(key) creates a wr-dependency on key
3: Write(key, v + δ) creates a ww-conflict on key
4: function TxWithCrdt(key, δ) blind, commutative update
5: if δ ≥ 0 then
6: Increment(key, δ)
7: else
8: Decrement(key, −δ)
Algorithm 2 shows an example of the difference between a transaction using a conventional counter update and a -Counter (Positive–Negative Counter) update. The PN-Counter is a CRDT for integer values that supports both increments and decrements. It maintains two grow-only vectors, one for increments and the other for decrements. The value is the difference between the sums of the vectors. Each operation adds to the corresponding counter at the designated replica index, so operations issued at different replicas commute and produce the same result in any order.
TxWithoutCrdt reads the current value, adjusts it, and writes it back. This read–modify–write sequence creates a read–write dependency and a write–write conflict on . In contrast, TxWithCrdt issues a blind Increment or Decrement operation, both of which are commutative. A transaction with no other conflicts can therefore use the fast-path commit described in Section 4.6.
Fast-path Commit
Certain transactions can respond to the clients eagerly as soon as they are consistently replicated, without waiting for the deterministic execution phase to complete, because it is impossible for them to be aborted. This optimization further reduces the response time for qualifying transactions. Note that fast-path commit does not change the execution semantics, since the transaction is still executed deterministically during the final execution phase; it only reduces the end-to-end response latency. We identify the following categories of transactions as eligible for fast-path commit:
Read-only transactions A read-only transaction whose reads are served entirely from the snapshot has an empty write set and can be serialized before the current batch’s writers. Since the snapshot is immutable and already available locally, its speculative read results can be reused. We call this read-only optimization Snapshot Read. It is evaluated separately from FastPath, which enables early client acknowledgment.
CRDT-only transactions Suppose a transaction performs all of its writes as CRDT operations and serves all of its reads from the snapshot. Because CRDT operations are commutative and have no write-write conflicts by construction and snapshot reads produce deterministic results, the outcome of the transaction is fully determined at replication time. Such transactions can therefore be committed eagerly.
RU transactions A transaction running at Read Uncommitted isolation imposes no constraint on which versions it may read: any version is acceptable. Reads under RU therefore cannot cause validation failures, regardless of concurrent writes, and lost updates are permitted, so the transaction can be committed eagerly.
Evaluation
We first evaluate 2PL/OCC/DCC to test whether our model’s qualitative sensitivities and bottlenecks persist in an actual implementation; then we measure the effectiveness of Quirinus’s optimizations and its end-to-end behavior.
Implementation and Setup
We build Quirinus on top of Minerva, a transactional key-value database that implements transaction processing, replication, and benchmarks, extending it to support the additional features. The cluster is deployed on 5 VMs on the cloud infrastructure of the Digital Research Alliance of Canada, where each VM is treated as a DC containing a replica of the database. Each VM has 4 vCPUs (Intel Xeon Skylake) and 48 GB of RAM and runs Ubuntu 24.04. Client threads run on a separate 16-core VM.
We implement 2PL and OCC using the same network and execution framework. We do not use consensus to implement actual distributed locking or OCC validation; instead, we use broadcast-based synchronization to simulate the coordination delay for a fair comparison.
Benchmarks and Metrics. We measure performance using the TPC-C and YCSB benchmarks. For TPC-C, we use 100 warehouses and a transaction mix of 50% payment and 50% new-order. For YCSB, we use the YCSB-A workload, where each transaction performs 50% reads and 50% blind writes with a Zipfian-distributed key-access pattern over a key space of keys with a 1 KB value size. The Zipfian factor (skew) determines the contention level, where higher values mean more key accesses are concentrated on a smaller set of hot keys, which increases contention. The transactions are implemented as stored procedures where clients only send parameters to the database.
We report the end-to-end latency (in ms) and throughput (in txn/s), measured at the client side over all successful transactions. The peak sustainable throughput is obtained by probing the system with an increasing number of clients until the commit throughput plateaus, which corresponds to the saturated throughput in the theoretical model. Each experiment runs for 30 seconds, and we sample client throughput every second. We report either the average throughput, after dropping the lowest 10% of samples to remove the warm-up period, or the peak sustainable throughput. For selected experiments, we introduce artificial cross-DC latency using Linux’s tc tool to simulate WAN conditions.
We use a Zipfian distribution instead of a uniform distribution as the models suggest to demonstrate that model-implied sensitivities and bottlenecks persist beyond the simplifying assumptions. We therefore compare trend direction and bottleneck order, rather than calibrating the model or comparing predicted and measured point values.
DCC vs. OCC and 2PL
We compare the performance of DCC with OCC and 2PL under different cross-DC latency and contention settings using the YCSB-A benchmark. For DCC, we disable the optimizations in Quirinus described above for a cleaner comparison with the theoretical model. We also disable Raft consensus to match the coordination costs of 2PL and OCC.
Figure 7 compares the average saturated throughput at different contention levels. Under this matched simulated-coordination setting, which isolates the paradigm effect from implementation differences, our DCC implementation in Quirinus outperforms 2PL and OCC in absolute throughput, confirming the caveat mentioned in Section 3.4 that the protocol design itself still significantly affects actual performance. For DCC, latency still significantly affects absolute throughput because, to maintain a reasonable batch interval (10 ms) for response time, the replication protocol again becomes the bottleneck, showing the necessity of optimizing the replication protocol in Quirinus.
Figure 7. Saturated throughput vs. contention level at different cross-DC latency settings. Bars represent the absolute throughput, while lines represent the relative degradation compared to the zero-contention case.
Relative throughput degradation, rather than absolute throughput, is the appropriate comparison with the model, and its direction is consistent with the model-implied sensitivities. Note that, because of Zipfian skew, the skew parameter does not correspond one-to-one to the homogeneous conflict probability used in the model. In the experiment, increasing skew concentrates conflicts on a small set of hot keys. As a result, the measured curves are expected to drop earlier and more sharply than the smooth theoretical curves, although the relative trend remains the same. The performance of both OCC and 2PL degrades as soon as contention is set to 0.3, while DCC maintains the throughput level until 0.7. Higher latency also amplifies the degradation of 2PL and OCC, but DCC is relatively unaffected, and OCC beats 2PL when latency is higher, as expected.
Figure 8 illustrates the measured throughput vs. median response time; we gradually increase the number of clients until the systems saturate, and we report the median commit latency at the corresponding commit throughput. The measured curves are also consistent with the model’s qualitative latency ordering: OCC offers better latency when load is low but degrades much more sharply than DCC as load increases, while 2PL suffers greatly in any case. When contention is higher, both OCC and 2PL also saturate almost immediately at very low input throughput, and throughput degrades as latency increases.
Figure 8. Throughput vs. median response time at different cross-DC latency settings and contention levels. OCC cannot sustain stable throughput at cross-DC latency settings of ms and .
Optimization Effectiveness
Figure 9. Ablation of optimizations at different cross-DC latency settings and contention levels. Speculative execution is enabled throughout. Bars show throughput, and lines show the percentage change in throughput relative to each panel’s baseline. YCSB configurations exclude CRDT.
Figure 10. Saturated throughput and moderate-load latency under different isolation levels for YCSB with skew=0.3.
We evaluate the throughput and latency effects of the optimizations in Section 4. Speculative execution (Section 4.2) is enabled in every ablation configuration and defines Base. Reorder adds transaction reordering (Section 4.4). Snapshot Read adds the read-only snapshot optimization, and FastPath adds early acknowledgment (both in Section 4.6). CRDT adds CRDT integration (Section 4.5). All combines the applicable optimizations.
The YCSB configurations exclude CRDT, including from All. In the lower-right panel, CRDT is enabled in every configuration, and Base + CRDT is the reference.
Figure 9 illustrates the effectiveness of the individual optimization techniques. All transactions run under SER isolation, and CRDT integration is evaluated only for TPC-C. The YCSB results are shown in the two left panels. In YCSB, enabling all optimizations improves throughput by approximately 25% to 30% under high contention (Zipf skew of 1.5), but by less than 10% under low contention (skew of 0.3), at both network-delay settings.
Among the individual optimizations, transaction reordering provides the largest improvement, increasing throughput by 20% to 25% under high contention; snapshot read-only execution and fast-path commit provide smaller gains of roughly 10% to 20%. An interesting observation is that the gains are not additive, as the combined configuration improves throughput only slightly more than reordering alone. We hypothesize that these techniques often optimize the same transactions and overlapping portions of the critical path. The similar relative gains with and without cross-DC delay further suggest that the improvements primarily reduce contention and execution overhead rather than network coordination.
TPC-C results are shown in the upper-right panel. Unlike YCSB, the overall improvement is much more significant, but each optimization on its own is less effective, with individual techniques showing similar gains. Yet CRDT integration on its own reduces performance rather than improving it, especially in the higher-latency case (50 ms and 10 ms jitter), where adding CRDTs alone lowers throughput by approximately 35%. This is likely caused by the overhead of replicating larger CRDT operations rather than only result values.
However, when combined with other optimizations, CRDTs substantially improve throughput, as shown in the bottom-right panel. In particular, combining CRDT integration with fast-path commit increases throughput by approximately 45%, accounting for nearly all of the gain from enabling every optimization. CRDTs alone eliminate hot write-write conflicts but leave read dependencies and execution waits, whereas the other techniques alone remain limited by the hot updates. Once CRDTs remove these update conflicts, snapshot reads remove the remaining read dependencies, reordering preserves more speculative results, and fast-path commit becomes available to update-heavy TPC-C transactions. Each technique therefore leaves a different bottleneck in place when used alone, but together they shorten the critical dependency chain enough for their benefits to outweigh their overheads.
Figure 10 compares mean saturated throughput and moderate-load latency for the YCSB-A workload when all transactions are executed under the same isolation level. The experiment uses a Zipfian skew of 0.3 and no added cross-DC delay, which isolates the effect of dependency relaxation from network coordination. For throughput, SI and RC provide small gains over SER, while RU reaches the highest throughput, roughly 10% above SER. The latency results are measured at a moderate load of 500 total clients, highlighting the benefits of weaker isolation levels. The median latency drops from SER/SI to RC/RU by about 30%, and the p99 latency falls more substantially, from about 230 ms under SER to about 180 ms under RC/RU.
End-to-End Comparisons
Finally, we compare Quirinus with Tiga [13] and Detock [37], two state-of-the-art geo-distributed databases. Tiga is an OCC-based protocol that uses timestamp ordering and Paxos to agree on the commit order of transactions, and Detock uses a dependency graph and deterministic conflict resolution optimized for cross-shard operations. This experiment asks whether a fully replicated active-active database can sustain high throughput against sharded databases.
Since neither supports active-active replication, we deploy them in a sharded configuration across the 5 nodes and set the replication factor to 5 to match the full replication of Quirinus. For Detock, the cross-shard transactions are set to 50%. For Quirinus, we use SER isolation without optimizations enabled for a fair SER comparison. We report the peak throughput here, which is the maximum sustainable throughput during the 30-second experiment runs.
Figure 11 shows the peak throughput of the three systems and exposes the trade-off between their replication and execution strategies. On TPC-C, Quirinus achieves up to 6.2× the peak throughput of Tiga and remains the highest-throughput design as cross-DC delay increases, although its throughput gradually declines. On YCSB, Quirinus leads without cross-DC delay, but Tiga degrades more gradually and becomes the highest-throughput system once delay is introduced, while Detock’s throughput drops sharply. Tiga uses synchronized clocks to place most transactions on a lightweight one-RTT path [13], and only shard leaders execute transactions while followers record them in their logs. This reduces coordination and replica-side computation, but does not provide active-active access. Quirinus remains competitive without cross-DC delay but falls behind Tiga on YCSB as delay increases, reflecting the cost of active-active multi-replica execution.
Figure 11. Peak sustainable throughput vs. cross-DC latency.
Figure 12 shows that transaction latency generally increases with cross-DC delay, while Detock retains a low median for its local single-home transactions and Tiga benefits from its one-RTT fast path. In contrast, Quirinus’s mean and median latency track the cross-DC delay more closely, and its p99 latency reaches approximately 1.2 to 1.4 s at 200 ms. This is the cost of Quirinus’s DCC design: every transaction must wait for batch formation, replication, and deterministic execution, even when it has no conflicts, and the system therefore trades per-transaction latency for throughput.
Figure 12. Transaction latency (response time) vs. cross-DC latency.
Related Work
Performance Modeling of OLTP Databases Prior research dating back to the 1980s has developed analytical models of concurrency control, replication, and disk and network costs in transactional databases [7, 22, 36, 39, 42, 48, 50, 51]. However, modeling the performance trade-offs among concurrency control paradigms has received comparatively little attention, particularly under geo-replication. Recent work such as DBSeer [33] focuses on resource prediction for specific systems rather than providing general insights. Haubenschild and Leis [18] study the cost of cloud OLTP architectures, and GeoTP [63] studies lock-based geo-distributed databases.
Geo-replicated Databases Geo-distributed and replicated databases have been an active research direction over the past decades [9, 12, 13, 20, 26, 32, 35, 45, 47, 49, 59, 60, 61, 62]. However, active-active replication remains rare. Mako [47] presents an OCC-based protocol that uses leader replication; it reduces the time transactions wait on replication by making results speculatively visible before replication succeeds. However, its dependency tracking is local (on the leader shard) and therefore cannot address active-active replication; in addition, it relies on RDMA. GeoGauss [62] provides active-active multi-master replication, also using OCC, but it relies on a synchronous global execution barrier for each batch of transactions as an epoch. Detock [37] eliminates global ordering for multi-region transactions by having participating regions independently construct the same dependency graph and resolve deadlocks deterministically; however, it retains a single home region for each item and asynchronously propagates regional logs to other regions. Starry [61] supports multi-master transaction processing through a semi-leader protocol that commits non-conflicting transactions at any replica on a decentralized fast path, while routing conflicts to a centralized sequencer for reordering.
Deterministic Concurrency Control After Calvin [53], one of the pioneering deterministic databases, SLOG [45] extends Calvin with locality awareness, allowing single-region transactions to commit without cross-region coordination. BOHM [10] and Caracal [44] adapt DCC to multi-version databases. Aria [28] uses a similar snapshot approach, and Gria [56] improves Aria with adaptive batch sizing. We also note that DCC protocols rarely view themselves as state-machine replication protocols, although they are inherently similar. Only in some blockchain systems, such as Harmony [24], which applies the same snapshot-per-block model to private blockchains, can we view determinism as part of the replication protocol. Thus, we build Quirinus with replication as part of the integrated design, which gives us a larger optimization space.
Conclusion
Deterministic concurrency control is a promising approach for geo-replicated databases, but its performance under high contention and coordination delay has not been well understood. In this paper, we present a theoretical model that captures the trade-offs of DCC relative to 2PL and OCC. We also design Quirinus, a deterministic database optimized for active-active replication, with features such as speculative execution, transaction reordering, conflict-free data type integration, and fast-path commit. Our evaluation shows that Quirinus achieves high throughput on TPC-C but falls behind Tiga on YCSB as cross-DC delay increases.
References
A Derivation of Blow-up Threshold under 2PL with Geo-replication
This appendix derives the lock contention threshold in 2PL. The derivation follows Yu et al.’s high-contention 2PL approximation [57] as an asymptotic threshold for the lock-wait fixed point.
The Quantity Being Solved
Yu’s fixed-length 2PL model splits each lock stage into two pieces. In substate , the transaction already holds locks and executes the -th access with mean time . In substate , the transaction is trying to acquire lock while still holding the previous locks.
Let be the probability that a lock request is blocked, and let be the mean lock-wait time conditional on such a block. In Yu’s original model, the unconditional waiting cost per lock stage is . With geo-replication, every lock acquisition also pays one coordination round-trip, even if the lock is free. We therefore use
to represent that every request pays , and only the contended fraction pays the extra queueing wait .
The threshold is stated in terms of Yu’s per-transaction contention measure
This is the average number of lock contentions a transaction sees over the later lock requests. The first lock has no earlier locks to hold while waiting, so Yu’s blow-up calculation is naturally written with .
Yu’s High-contention Wait Approximation
Yu’s blow-up threshold is obtained from the high-contention limit of the lock-wait equation: is large, lock waiting dominates commit time, and we use Yu’s default residual-life correction, , for the remaining lock-holding time seen by a blocked requester. Under this assumption, Yu’s eq:3.19 reduces to
This is the feedback step. If a transaction spends longer in each stage, then it holds its previous locks longer; a new requester is more likely to meet a holder with a long remaining chain of work; therefore, the conditional wait grows with .
The final replicated-commit round is still required by 2PL. It extends the period for which all locks are held and is included in the lock-exposure aggregate used by the throughput calculation in the body. It does not appear in the reduced threshold equation below because this Yu-style high-contention limit drops commit-time constants relative to lock waiting.
Closing the Fixed Point
(1) gives another expression for the same conditional wait:
Equating (4) and (3) gives
Multiplying by and using :
This is the self-consistency equation. The left side says that more per-transaction contention makes the lock holder’s remaining work more expensive. The right side says that the only part of that can be explained by queueing is the amount above the unavoidable round-trip .
Now make the equation dimensionless:
Substitute this into (6):
After dividing by and rearranging, we get the quadratic
This is the quadratic used in the body of the paper. When , it reduces to Yu’s original form .
Reading the Threshold from the Discriminant
The quadratic (9) has coefficients
A finite real fixed point requires real roots, so the discriminant must be non-negative:
Solving for gives
Thus the blow-up boundary is
Solving (9) gives
At the blow-up boundary, the discriminant is zero and the two roots coincide. Substituting gives
Using , the corresponding per-lock acquisition stage cost is
Below this threshold, the quadratic has two roots. The minus branch is the relevant low-load solution because it continuously approaches the no-contention case: as , it gives . This means the queueing wait disappears, while each lock request still pays the coordination round-trip. The plus branch has no meaningful solution in this limit.
Intuition. The coordination delay does two things at once. First, it increases the per-lock stage cost from to . Second, that higher stage cost increases Yu’s wait equation, because lock holders keep their earlier locks longer. This feedback appears as the larger constant term in (9). A larger constant makes the discriminant disappear at a smaller value of , so the system tolerates less contention before the lock-wait fixed point is unstable.
Lock Exposure at the Lock-Wait Blow-up Boundary
is the total time for which a transaction holds locks in Yu et al.’s paper, summed across all of its locks. With geo-replication, we use because each serialized lock-acquisition stage pays . The transaction holds an increasing number of locks as it executes, holds its earlier locks while acquiring each later lock, and holds all locks during commit. Therefore,
At the blow-up boundary, . Neglecting local commit work gives . Substituting both values into (17):
The term is the exposure caused by the lock-acquisition rounds while earlier locks remain held. The final term is the additional exposure from the replicated-commit round, during which all locks remain held. If local commit work is retained, the result becomes .
Derivation of the Longest Dependency Chain Length
This section derives a closed form using the mean-field recurrence for , which is the expected length of the longest dependency chain for a newly arrived transaction given a pool of in-flight transactions ahead of it. We show that the linear ansatz is an exact solution of the recurrence and that the slope is forced to be , yielding .
The Recurrence
From the model in § 3.3, conditioning on (the highest-id out-neighbour of , with when has no out-edges) and applying the mean-field substitution gives
The branch contributes 0 to the expectation, so it does not appear in the sum. Reindexing with and writing for brevity,
Linear Ansatz
We try a linear solution with unknown slope :
which is consistent with the boundary condition . Substituting (21) into (20) splits the right-hand side into two sums:
We evaluate and in closed form below. For , the exponents run from down to 0, so the sum is geometric:
using , which is the probability that has at least one out-neighbour in the pool of .
For , make the dependence on the upper limit explicit:
We write rather than just to compare the same weighted sum at consecutive upper limits, express the larger sum using the smaller one plus the new final term, and then verify the closed form by induction. The expression for the upper limit differs from the expression for by one new final term, :
The base case is , because the only term has . We claim the closed form
Verification by induction: (25) gives , matching the base case. For the step, assume (25) holds at and substitute into (24):
The target value at is . The two agree iff , which rearranges to — true by definition. Hence (25) holds for all .
Consistency Condition
Substituting (23) and (25) into (22),
The terms cancel on both sides, leaving
For any the factor is strictly positive, so (28) forces
The linear ansatz is therefore an exact solution of the mean-field recurrence (20): no -dependent residual survives, and the slope is uniquely pinned.
Closed form. Combining (21) and (29),
Specialising to the in-flight pool size gives , which is the expression fed back into the wait-time bound in the body.
Intuition. Walk down the longest chain from one hop at a time. The id-gap from a vertex of id-rank to its highest-id out-neighbour is geometric with parameter on , so each hop drops the working id by about on average. Starting from the back of a pool of size leaves room for roughly hops before the chain hits the bottom.
References
- [1]2025. Active-Active Geo-Distributed Redis. https://redis.io/docs/latest/operate/rs/databases/active-active/
- [2]Daniel J. Abadi and Jose M. Faleiro. 2018. An overview of deterministic database systems. Commun. ACM 61, 9 (Aug. 2018), 78–88. https://doi.org/10.1145/3181853
- [3]A. Adya, B. Liskov, and P. O’Neil. 2000. Generalized isolation level definitions. In Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073), 67–78. https://doi.org/10.1109/ICDE.2000.839388
- [4]Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2013. Highly available transactions: virtues and limitations. Proc. VLDB Endow. 7, 3 (Nov. 2013), 181–192. https://doi.org/10.14778/2732232.2732237
- [5]Peter Bailis, Alan Fekete, Michael J Franklin, Ali Ghodsi, Joseph M Hellerstein, and Ion Stoica. 2014. Coordination avoidance in database systems. Proceedings of the VLDB Endowment 8, 3 (2014), 185–196.DOI
- [6]Philip A. Bernstein and Nathan Goodman. 1981. Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13, 2 (June 1981), 185–221. https://doi.org/10.1145/356842.356846
- [7]E.G. Coffman, E. Gelenbe, and B. Plateau. 1981. Optimization of the Number of Copies in a Distributed Data Base. IEEE Transactions on Software Engineering SE-7, 1 (1981), 78–84. https://doi.org/10.1109/TSE.1981.234510
- [8]James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. 2013. Spanner: Google’s Globally Distributed Database. ACM Trans. Comput. Syst. 31, 3, Article 8 (Aug. 2013), 22 pages. https://doi.org/10.1145/2491245
- [9]Tamer Eldeb, Xinchen Xie, Philip A. Bernstein, Asaf Cidon, and Junfeng Yang. 2023. Chardonnay: Fast and General Datacenter Transactions for On-Disk Databases, 343–360. https://www.usenix.org/conference/osdi23/presentation/eldeeb
- [10]Jose M. Faleiro and Daniel J. Abadi. 2015. Rethinking serializable multiversion concurrency control. Proc. VLDB Endow. 8, 11 (July 2015), 1190–1201. https://doi.org/10.14778/2809974.2809981
- [11]Jose M. Faleiro, Daniel J. Abadi, and Joseph M. Hellerstein. 2017. High performance transactions via early write visibility. Proceedings of the VLDB Endowment 10, 5 (Jan. 2017), 613–624. https://doi.org/10.14778/3055553.3055553
- [12]Hua Fan and Wojciech Golab. 2019. Ocean Vista: Gossip-Based Visibility Control for Speedy Geo-Distributed Transactions. Proceedings of the VLDB Endowment 12, 11 (July 2019), 1471–1484. https://doi.org/10.14778/3342623.3342627
- [13]Jinkun Geng, Shuai Mu, Anirudh Sivaraman, and Balaji Prabhakar. 2020. Tiga: Accelerating Geo-Distributed Transactions with Synchronized Clocks. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles (SOSP ’25). Association for Computing Machinery, New York, NY, USA, 555–571. https://doi.org/10.1145/3731569.3764854
- [14]Alexey Gotsman, Hongseok Yang, Carla Ferreira, Mahsa Najafzadeh, and Marc Shapiro. 2016. ’Cause I’m strong enough: Reasoning about consistency choices in distributed systems. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, St. Petersburg FL USA, 371–384. https://doi.org/10.1145/2837614.2837625
- [15]Jim Gray, Pat Helland, Patrick O’Neil, and Dennis Shasha. 1996. The dangers of replication and a solution. SIGMOD Rec. 25, 2 (June 1996), 173–182. https://doi.org/10.1145/235968.233330
- [16]Zhibo Han, Zeshun Peng, Gang Wang, Minghe Yu, Xiaohua Li, Yanfeng Zhang, and Ge Yu. 2025. An optimized deterministic concurrency control approach for geo-distributed transaction processing on permissioned blockchains. Scientific Reports 15, 1 (2025), 19238.
- [17]Rachael Harding, Dana Van Aken, Andrew Pavlo, and Michael Stonebraker. 2017. An evaluation of distributed concurrency control. Proceedings of the VLDB Endowment 10, 5 (2017), 553–564.DOI
- [18]Michael Haubenschil and Viktor Leis. 2025. OLTP in the cloud: architectures, tradeoffs, and cost. The VLDB Journal 34, 4 (2025), 42.
- [19]Pat Helland, Harald Sammer, Jim Lyon, Richard Carr, Phil Garrett, and Andreas Reuter. 1989. Group commit timers and high volume transaction systems. In High Performance Transaction Systems, Dieter Gawlick, Mark Haynie, and Andreas Reuter (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 301–329.DOI
- [20]Joshua Hildred, Michael Abebe, and Khuzaima Daudjee. 2023. Caerus: Low-Latency Distributed Transactions for Geo-Replicated Systems. Proc. VLDB Endow. 17, 3 (Nov. 2023), 469–482. https://doi.org/10.14778/3632093.3632109
- [21]Yinhao Hong, Hongyao Zhao, Wei Lu, Xiaoyong Du, Yixing Chen, Anpan Pan, and Lixiong Zheng. 2025. A Hybrid Approach to Integrating Deterministic and Non-Deterministic Concurrency Control in Database Systems. Proceedings of the VLDB Endowment 18, 5 (Jan. 2025), 1376–1389. https://doi.org/10.14778/3718057.3718066
- [22]San-Yih Hwang, Keith K. S. Lee, and Y. H. Chin. 1996. Data replication in a distributed system: A performance study. In Database and Expert Systems Applications, Roland R. Wagner and Helmut Thoma (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 708–717.
- [23]Martin Kleppmann. 2016. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O’Reilly.
- [24]Ziliang Lai, Chris Liu, and Eric Lo. 2023. When Private Blockchain Meets Deterministic Database. Proc. ACM Manag. Data 1, 1, Article 98 (May 2023), 28 pages. https://doi.org/10.1145/3588952
- [25]Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) (Dec. 2001), 51–58.
- [26]Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno M. Preguiça, and Rodrigo Rodrigues. 2012. Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012, Chandu Thekkath and Amin Vahdat (Eds.). USENIX Association, 265–278. https://www.usenix.org/conference/osdi12/technical-sessions/presentation/li
- [27]Haonan Lu, Christopher Hodsdon, Khiem Ngo, Shuai Mu, and Wyatt Lloyd. 2016. The SNOW Theorem and Latency-Optimal Read-Only Transactions. 135–150. https://www.usenix.org/conference/osdi16/technical-sessions/presentation/lu
- [28]Yi Lu, Xiangyao Yu, Lei Cao, and Samuel Madden. 2020. FaaST: A Fast and Practical Deterministic OLTP Database. Proceedings of the VLDB Endowment 13, 12 (Aug. 2020), 2047–2060. https://doi.org/10.14778/3476312.3470808
- [29]Yi Lu, Xiangyao Yu, Lei Cao, and Samuel Madden. 2021. Epoch-Based Commit and Replication in Distributed OLTP Databases. Proceedings of the VLDB Endowment 14, 5 (Jan. 2021), 743–756. https://doi.org/10.14778/3446095.3446098
- [30]Hatem A Mahmoud, Vaibhav Arora, Faisal Nawab, Divyakant Agrawal, and Amr El Abbadi. 2014. Maat: Effective and scalable coordination of distributed transactions in the cloud. Proceedings of the VLDB Endowment 7, 5 (2014), 329–340.
- [31]Yaser Mansouri, Adel Nadjaran Toosi, and Rajkumar Buyya. 2017. Data storage management in cloud environments: Taxonomy, survey, and future directions. ACM Computing Surveys (CSUR) 50, 6 (2017), 1–51.
- [32]Yunhao Mao, Harunari Takata, Michail Bachras, Yuqiu Zhang, Shiquan Zhang, Zhengru Zhang, and Hans-Arno Jacobsen. 2026. Epoch-based Optimistic Concurrency Control in Geo-replicated Databases. arXiv:2602.21566 [cs.DB] https://arxiv.org/abs/2602.21566
- [33]Barzan Mozaffari, Carlo Curino, Alekh Jindal, and Samuel Madden. 2013. Performance and resource modeling in highly-concurrent OLTP workloads. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (New York, New York, USA) (SIGMOD ’13). Association for Computing Machinery, New York, NY, USA, 301–312. https://doi.org/10.1145/2463676.2467800
- [34]Shuai Mu, Lamont Nelson, Wyatt Lloyd, and Jinyang Li. 2016. Validating Conflict-free Replicated Data Types. In Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data, 517–532. https://www.usenix.org/conference/osdi16/technical-sessions/presentation/mu
- [35]Faisal Nawab, Vaibhav Arora, Divyakant Agrawal, and Amr El Abbadi. 2015. Minimizing Commit Latency of Transactions in Geo-Replicated Data Stores. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD ’15). Association for Computing Machinery, New York, NY, USA, 1279–1294. https://doi.org/10.1145/2723372.2723729
- [36]Randolph D. Nelson and Balakrishna R. Iyer. 1985. Analysis of a replicated data base. Performance Evaluation 5, 3 (Aug. 1985), 133–148. https://doi.org/10.1016/0166-5316(85)90008-2
- [37]Cuong D. T. Nguyen, Johann K. Miller, and Daniel J. Abadi. 2023. Detock: High Performance Multi-region Transactions at Scale. Proc. ACM Manag. Data 1, 2, Article 148 (June 2023), 27 pages. https://doi.org/10.1145/3589293
- [38]Diego Ongaro and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In 2014 USENIX Annual Technical Conference (USENIX ATC 14). USENIX Association, Philadelphia, PA, 305–319. https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro
- [39]Rasha Osman and William J. Knottenbelt. 2012. Database system performance evaluation models: A survey. Performance Evaluation 69, 10 (2012), 471–493. https://doi.org/10.1016/j.peva.2012.05.006
- [40]M. Tamer Özsu and Patrick Valduriez. 2020. Principles of Distributed Database Systems (fourth edition ed.). Springer, Cham, Switzerland.
- [41]Fernando Pedone, Rachid Guerraoui, and André Schiper. 2003. The database state machine approach. Distributed and Parallel Databases 14, 1 (2003), 71–98.DOI
- [42]D. Potier and Ph. Leblanc. 1980. Analysis of locking policies in database management systems. Commun. ACM 23, 10 (Oct. 1980), 584–593. https://doi.org/10.1145/359015.359021
- [43]Nuno Rodrigues, 2018. Conflict-free Replicated Data Types: An Overview. arXiv:1806.10254 [cs.DC] https://arxiv.org/abs/1806.10254
- [44]Dai Qin, Angela Demke Brown, and Ashvin Goel. 2021. Caracal: Contention Management with Deterministic Concurrency Control. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP ’21). Association for Computing Machinery, New York, NY, USA, 180–194. https://doi.org/10.1145/3477132.3483591
- [45]Kun Ren, Dennis Li, and Daniel J. Abadi. 2019. SLOG: serializable, low-latency, geo-replicated transactions. Proc. VLDB Endow. 12, 11 (July 2019), 1747–1761. https://doi.org/10.14778/3342263.3342647
- [46]Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. Conflict-Free Replicated Data Types. In 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (Grenoble, France) (SSS 2011). Springer, 386–400.
- [47]Weihai Shen, Yang Cui, Siddhartha Sen, Sebastian Angel, and Shuai Mu. 2025. Mako: Speculative Distributed Transactions with Geo-Replication. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25). 129–152.
- [48]A.P. Sheth, A. Singhal, and M.T. Liu. 1985. An Analysis of the Effect of Network Parameters on the Performance of Distributed Database Systems. IEEE Transactions on Software Engineering SE-11, 10 (1985), 1174–1184. https://doi.org/10.1109/TSE.1985.231865
- [49]Rebecca Taft, Irfan Sharif, Andrej Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Dernall, Bram Gruneir, Justin Jaffray, Lucy Zhang, and Peter Mattis. 2020. CockroachDB: The Resilient Geo-Distributed SQL Database. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD ’20). Association for Computing Machinery, New York, NY, USA, 1493–1509. https://doi.org/10.1145/3318464.3386134
- [50]Alexander Thomasian. 1993. Two-phase locking performance and its thrashing behavior. ACM Trans. Database Syst. 18, 4 (Dec. 1993), 579–625. https://doi.org/10.1145/169725.169720
- [51]Alexander Thomasian. 1998. Concurrency control: methods, performance, and analysis. ACM Comput. Surv. 30, 1 (March 1998), 70–119. https://doi.org/10.1145/274440.274443
- [52]Alexander Thomson and Daniel J. Abadi. 2010. The case for determinism in database systems. Proc. VLDB Endow. 3, 1 (2010), 70–80. https://doi.org/10.14778/1938541.920855
- [53]Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J. Abadi. 2012. Calvin: Fast Distributed Transactions for Partitioned Database Systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM, Scottsdale Arizona USA, 1–12. https://doi.org/10.1145/2213836.2213838
- [54]Stephen Tu, Buning Zheng Cheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. 2013. Speedy transactions in multicore in-memory databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. ACM, Farmington, Pennsylvania, USA, 18–32. https://doi.org/10.1145/2517349.2522713
- [55]Martin J. Wainwright and Michael I. Jordan. 2008. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends in Machine Learning 1, 1–2 (2008), 1–305. https://doi.org/10.1561/2200000001
- [56]Xinyuan Wang, Yun Peng, and Hejiao Huang. 2023. Gria: an efficient deterministic concurrency control protocol. Frontier of Computer Science 18, 4 (Dec. 2023), 184204. https://doi.org/10.1007/s11704-023-2605-z
- [57]Philip S. Yu, Daniel M. Dias, and Stephen S. Lavenberg. 1993. On the analytical modeling of database concurrency control. J. ACM 40, 4 (Sept. 1993), 831–872. https://doi.org/10.1145/13724.153733
- [58]Gengrui Zhang, Fei Pan, Yuhao Mao, Sofia Tijanıc, Michael Dang’ana, Shashank Motepalli, Shiquan Zhang, and Hans-Arno Jacobsen. 2024. Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus Algorithms. Comput. Surveys 56, 5, Article 134 (Jan. 2024).arxiv.org/abs/2204.03181
- [59]Irene Zhang, Naveen Kr. Sharma, Adrian Székereş, Arvind Krishnamurthy, and Dan R. K. Ports. 2018. Building Consistent Transactions with Inconsistent Replication. ACM Trans. Comput. Syst. 35, 4 (Dec. 2018), 12:1–12:37. https://doi.org/10.1145/3269981
- [60]Zihao Zhang, Huiqi Hu, Xuan Zhou, Yaofeng Tu, Weining Qian, and Aoying Zhou. 2024. Fast Commitment for Geo-Distributed Transactions via Decentralized Co-Coordinators. Proc. VLDB Endow. 17, 10 (June 2024), 2555–2567. https://doi.org/10.14778/3675034.3675046
- [61]Zihao Zhang, Huiqi Hu, Xuan Zhou, and Jiang Wang. 2022. Starry: multi-master transaction processing on semi-leader architecture. Proceedings of the VLDB Endowment 16, 1 (2022), 77–89.
- [62]Weixing Zhou, Qi Peng, Zijie Zhang, Yanfeng Zhang, Yang Ren, Sihao Li, Guo Fu, Yulong Cui, Qiang Li, Caiyi Wu, Shangjun Han, Shengyi Wang, Guoliang Li, and Ge Yu. 2023. GeoGauss: Strongly Consistent and Light-Coordinated OLTP for Geo-Replicated SQL Databases. Proc. ACM Manag. Data 1, 1 (2023), 1–27. https://doi.org/10.1145/3588916
- [63]Qiyu Zhuang, Xinyue Shi, Shuang Liu, Wei Lu, Zhanmao Zhao, Yuxing Chen, Tong Li, Anquan Pan, and Xiaoyang Du. 2025. GeoTP: Latency-Aware Geo-Distributed Transaction Processing in Database Middlewares. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). 433–445. https://doi.org/10.1109/ICDE65448.2025.00039 ISSN: 2375-026X.










