betaFeedback

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.

SystemCC protocolReplication typePartial vs. fullOrdering mechanismNotes
Spanner [8]2PL+MVCCLeader–followerPartial / configurablePhysical Timestamp
CockroachDB [49]Timestamp Ordering + MVCCLeader–followerPartial / configurablePhysical TimestampHybrid concurrency control using timestamps and optimistic execution
TAPIR [59]OCCLeaderlessPartialPhysical Timestamp
Mako [47]OCCLeader–followerPartialLocal TimeRequires RDMA
GeoGauss [62]OCCMulti-leaderFullLocal Time
Starry [61]OCCMulti-leaderPartialLogical Clock
Tiga [13]Timestamp Ordering + OCCLeader–followerPartial or fullLogical Clock
Minerva [32]OCC + DeterministicMulti-leaderFullLogical ClockDeterministic only for aborted transactions
Calvin [53]DeterministicLeader–followerFullLocal Time
SLOG [45]DeterministicLeader–followerFullLog Order
Detock [37]DeterministicLeader–followerHybrid; optional full materializationDependency Graph
Aria [28]DeterministicCC-only designN/ALogical Clock
Harmony [24]DeterministicBlockchainFullLogical ClockBlock-level ordering
QuirinusDeterministicMulti-leaderFullLogical 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:

  1. 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.

  2. We present Quirinus, a database that utilizes DCC with optimizations that reduce the execution delay of DCC.

  3. 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:

  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.

  2. Replication: Once a batch has been collected, it is replicated to all replicas using a consensus protocol.

  3. 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 i−1i-1 is the first case where replication is the bottleneck (slower than the execution of epoch i−2i-2), so the execution of epoch i−1i-1 must wait for its replication to finish. The execution of epoch i−1i-1 is, in turn, longer than the replication of epoch ii, so the execution of epoch ii must wait for the execution of epoch i−1i-1 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 (τ\tau), 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:

R2PL=RINPL+RE+NLPWRW+TCommit.R_{2PL}=R_{\mathrm{INPL}}+R_{\mathrm{E}}+N_{\mathrm{L}}P_{\mathrm{W}}R_{\mathrm{W}}+T_{\mathrm{Commit}}.

and for OCC:

ROCC=RINPL+RE+PA1−PA(TBackoff+RE′)+TCommit.R_{\mathrm{OCC}}=R_{\mathrm{INPL}}+R_{\mathrm{E}}+\frac{P_{\mathrm{A}}}{1-P_{\mathrm{A}}}\left(T_{\mathrm{Backoff}}+R_{\mathrm{E}}^{\prime}\right)+T_{\mathrm{Commit}}.

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 D=RINPL+NLR0D=R_{\mathrm{INPL}}+N_{\mathrm{L}}R_{0}, where R0R_{0} is the average per-granule access time (i.e., an LL in 2PL and R^\hat{R} in OCC). Following Yu’s model, the compute resource is treated as an open queue with arrival rate λ\lambda, served by KK CPUs, where DD is the time to process one transaction on a CPU. The compute utilization is therefore ρ=λD/K\rho=\lambda D/K (ignoring locks). Under the fixed-length transaction assumption, each transaction sees λNL2TH/L\lambda N_{\mathrm{L}}^{2}T_{\mathrm{H}}/L expected conflicts under both 2PL and OCC, given λTH\lambda T_{\mathrm{H}} concurrent in-flight transactions (by Little’s Law) and a per-pair conflict probability of pc≈NL2/Lp_{\mathrm{c}}\approx N_{\mathrm{L}}^{2}/L.

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 τ\tau, so that TCommit=TCommitlocal+τ≈τT_{\mathrm{Commit}}=T_{\mathrm{Commit}}^{\mathrm{local}}+\tau\approx\tau. 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 PWT≈0.75P_{\mathrm{W}}^{T}\approx0.75, the lock wait grows unbounded. This bound is obtained by equating two expressions for RWR_W: one from the definition b=PWRWb=P_W R_W, and one from the construction of RWR_W for a single lock wait. The result is quadratic in bb, because RWR_W depends on itself, and a real, positive solution (a finite lock wait) exists only when PWT≤0.75P_W^T\leq0.75.

SymbolMeaning
LLNumber of granules (data objects) in the database
NLN_LGranules accessed per transaction (fixed length)
λ\lambdaTransaction arrival rate★
KKNumber of CPUs★
RRMean transaction response time
RINPLR_{\mathrm{INPL}}Mean setup time per transaction
RER_EMean execution time (compute considered)
TCommitT_{\mathrm{Commit}}Mean commit time including results replication
TBackoffT_{\mathrm{Backoff}}Mean backoff time after abort
THT_HMean granule holding time
aaMean lock-holding time in the execution substate
bbUnconditional lock-acquisition time, b=PWRWb=P_W R_W
PWP_WPer-lock-request contention probability
PWTP_W^TPer-transaction contention, PWT=PW(NL−1)P_W^T=P_W(N_L-1)
RWR_WMean lock-waiting time given contention
GGSum of mean lock-holding times on all granules
PA,PA′P_A,P_A'Per-transaction abort probability (first & re-run)
R^,R′\hat{R},R'Mean per-state execution time (first & re-run)
RE′R_E'Mean re-execution time on rerun, RE′=NLR′R_E'=N_LR'
τ\tauMean delay of RTT-scaled coordination among replicas, O(RTT)O(\mathit{RTT})★
DDTransaction compute demand, without considering compute resources★
pcp_cPairwise conflict probability under uniform access, pc≈NL2/Lp_c\approx N_L^2/L★
λ∗\lambda^*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 b′=τ+PWRWb'=\tau+P_W R_W. This extra delay lengthens how long each transaction holds its locks, which in turn raises the chance that other transactions collide (PWP_W). Adding τ\tau, we obtain the response time formula:

R2PL=RINPL+NLa+NLb′+TCommit≈RINPL+NLa+NL(τ+PWRW)+τ=RINPL+NLa+NLPWRW+(NL+1)τ.\begin{aligned} R_{\mathrm{2PL}}&=R_{\mathrm{INPL}}+N_La+N_Lb'+T_{\mathrm{Commit}}\\ &\approx R_{\mathrm{INPL}}+N_La+N_L(\tau+P_WR_W)+\tau\\ &=R_{\mathrm{INPL}}+N_La+N_LP_WR_W+(N_L+1)\tau. \end{aligned}

Following Yu et al.’s lock wait threshold derivation, we estimate the threshold after adding τ\tau:

PW,MAXT=0.751+τ/a.P_{W,\mathrm{MAX}}^T=\frac{0.75}{1+\tau/a}.

This means that the blow-up threshold is lowered as τ\tau 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

λ2PL∗=min⁡(λCPU∗,λCont∗).\lambda^*_{\mathrm{2PL}}=\min\left(\lambda^*_{\mathrm{CPU}},\lambda^*_{\mathrm{Cont}}\right).

The compute-bound throughput is simply λCPU∗=KD\lambda^*_{\mathrm{CPU}}=\frac{K}{D} under an M/M/K queueing model in the absence of contention.

For the lock-wait blow-up bound, we first get bCont′=a+2τb'_{\mathrm{Cont}}=a+2\tau when PWT=0.75/(1+τ/a)P_W^T=0.75/(1+\tau/a). Then, we substitute bCont′b'_{\mathrm{Cont}} into the formula for G′G' (GG with b′b') to get GCont′G'_{\mathrm{Cont}}2:

GCont′=NL(NL+1)2a+NL(NL−1)2(a+2τ)+NLτ=NL2(a+τ).G'_{\mathrm{Cont}}=\frac{N_L(N_L+1)}{2}a+\frac{N_L(N_L-1)}{2}(a+2\tau)+N_L\tau=N_L^2(a+\tau).

Using the definition of PWTP_W^T and multiplying by (NL−1)(N_L-1) gives the mean number of contentions per transaction:

PWT=PW(NL−1)=λ(NL−1)G′L.P_W^T=P_W(N_L-1)=\lambda(N_L-1)\frac{G'}{L}.

Replacing G′G' with GCont′G'_{\mathrm{Cont}} and solving for λCont∗\lambda^*_{\mathrm{Cont}}:

λCont∗(NL−1)GCont′L=0.751+τ/a.\lambda^*_{\mathrm{Cont}}(N_L-1)\frac{G'_{\mathrm{Cont}}}{L}=\frac{0.75}{1+\tau/a}.
λCont∗=0.75LaNL2(NL−1)(a+τ)2.\lambda^*_{\mathrm{Cont}}=\frac{0.75La}{N_L^2(N_L-1)(a+\tau)^2}.

Optimistic Concurrency Control

We assume that initial attempts and reruns have the same abort probability and compute demand, so PA′=PAP_A'=P_A and both use DD3.

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 τ\tau 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:

PA≈1−exp⁡(−λNL2TH/L)(1−λNLτL)NL.P_A\approx1-\exp\left(-\lambda N_L^2T_H/L\right)\left(1-\frac{\lambda N_L\tau}{L}\right)^{N_L}.

Its O(1/L)O(1/L) linearization is:

PA≈λNL2(TH+τ)L.P_A\approx\frac{\lambda N_L^2(T_H+\tau)}{L}.

The overall response time combines the coordination round for the first attempt and each retry:

ROCC=RINPL+NLR+τ+PA1−PA(TBackoff+NLR′+τ).R_{\mathrm{OCC}}=R_{\mathrm{INPL}}+N_LR+\tau+\frac{P_A}{1-P_A}(T_{\mathrm{Backoff}}+N_LR'+\tau).

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 τ\tau 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 O(1/L)O(1/L) linearized approximation for the abort probability, we define PA≈λxP_A \approx\lambda x, where x=NL2(TH+τ)/Lx = N_L^2(T_H+\tau)/L is the abort coefficient after adding validation and replication coordination delay. The expected number of retries is λx1−λx\frac{\lambda x}{1-\lambda x}; including the first attempt, the expected compute demand is D1−λx\frac{D}{1-\lambda x}.

We then apply the M/M/K utilization condition ρ=λDK(1−λx)<1\rho= \frac{\lambda D}{K(1-\lambda x)} < 1. Substituting xx gives the maximum stable throughput:

λOCC∗=KD+Kx=KD+KNL2(TH+τ)/L=KLLD+KNL2(TH+τ).\lambda_{\mathrm{OCC}}^*=\frac{K}{D+Kx}=\frac{K}{D+KN_L^2(T_H+\tau)/L}=\frac{KL}{LD+KN_L^2(T_H+\tau)}.

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 τ\tau 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 KK parallel threads and a service time of DD. 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:

R=ΔB/2⏟batch wait+τ⏟replication time+WE⏟exec wait+D⏟own exec.R=\underbrace{\Delta_B/2}_{\text{batch wait}}+\underbrace{\tau}_{\text{replication time}}+\underbrace{W_E}_{\text{exec wait}}+\underbrace{D}_{\text{own exec}}.

Here, ΔB\Delta_B is the fixed time interval used to seal a batch. DCC can encounter a consensus delay blow-up when ΔB<τ\Delta_B < \tau, 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 ΔB≥τ\Delta_B \ge\tau for a stable system, with transactions still entering the execution queue at rate λ\lambda. Note that we do not use RER_E to denote the execution time, as we did for 2PL and OCC, because any computational wait time is absorbed into WEW_E, leaving DD as the unconditional compute time required for a transaction.

Next, we derive WEW_E, the mean waiting time when a transaction TT arrives in the stable state with NEN_E transactions in the execution queue. Because of determinism, TT must wait for all previous transactions that conflict with TT, as well as their predecessors, to finish execution. We need to consider the longest dependency chain of TT, 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 NEN_E vertices, where each vertex is a transaction labeled with a tidtid. Each pair of vertices is connected independently with the same probability pcp_c, and the edge always points from the higher tidtid to the lower tidtid. When TT, which has the highest tidtid, is inserted into the DAG, it again connects to each existing vertex with probability pcp_c.

Define II as the length of the longest dependency chain of TT and SS as the set that TT depends on; then we get:

I={0,S=∅,1+max⁡i∈STi,S≠∅.I = \begin{cases} 0, & S=\varnothing,\\ 1+\max_{i\in S}T_i, & S\ne\varnothing. \end{cases}

Defining ℓ(i−1)=E[Ii]\ell(i-1)=E[I_i] and M=max⁡{i:T→Ti}M=\max\{i:T\to T_i\}, we apply a mean-field approximation [55] to obtain a closed-form expression. We replace each random ITiI_{T_i} inside the maximum by its mean ℓ(i−1)\ell(i-1) 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:

E[max⁡i:T→TiITi]≈max⁡i:T→Tiℓ(i−1)=ℓ(M−1).E\left[\max_{i:T\to T_i} I_{T_i}\right]\approx\max_{i:T\to T_i}\ell(i-1)=\ell(M-1).

Then, for any NN transactions and any transaction TmT_m with m≤Nm\le N, we have:

Pr⁡(M=m)=pc(1−pc)N−m,Pr⁡(M=0)=(1−pc)N;\Pr(M=m)=p_c(1-p_c)^{N-m},\qquad\Pr(M=0)=(1-p_c)^N;
ℓ(N)=∑m=1Npc(1−pc)N−m(1+ℓ(m−1)).\ell(N)=\sum_{m=1}^{N}p_c(1-p_c)^{N-m}(1+\ell(m-1)).

Solving this mean-field recurrence gives (see Appendix § 10 for the detailed derivation):

ℓ(N)=pcNℓ(NE)=NEpc.\ell(N)=p_cN\qquad\ell(N_E)=N_Ep_c.

Finally, the wait time is the maximum of the execution queue wait (the computation bound) and the dependency chain wait (the contention bound):

WE=max⁡(NEDK,pcNED)=NED⋅max⁡(1/K,pc).W_E=\max\left(\frac{N_ED}{K},p_cN_ED\right)=N_ED\cdot\max(1/K,p_c).

In the stable state, NEN_E is in turn determined by Little’s Law as NE=λ(WE+D)N_E=\lambda(W_E+D).

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 λseq=λΔBτ\lambda_{\mathrm{seq}}=\frac{\lambda\Delta_B}{\tau}; otherwise, the sequencing queue is not a bottleneck and λseq=λ\lambda_{\mathrm{seq}}=\lambda.

For the execution queue, we can reverse-engineer the stable NEN_E. First, define Keff≡min⁡(K,1pc)K_{\mathrm{eff}}\equiv\min(K,\frac{1}{p_c}), then:

NE=λD(NEKeff+1);NE∗=λD1−λD/Keff.N_E=\lambda D\left(\frac{N_E}{K_{\mathrm{eff}}}+1\right);\qquad N_E^*=\frac{\lambda D}{1-\lambda D/K_{\mathrm{eff}}}.

A finite, positive pool requires a positive denominator, that is, λD/Keff<1\lambda D/K_{\mathrm{eff}}<1. The saturated rate of the execution stage is therefore:

λexec∗=KeffD=min⁡(K,1/pc)D=min⁡(KD,1Dpc).\lambda_{\mathrm{exec}}^*=\frac{K_{\mathrm{eff}}}{D}=\frac{\min(K,1/p_c)}{D}=\min\left(\frac{K}{D},\frac{1}{Dp_c}\right).

Finally, the overall saturated throughput is the minimum over the sequencing and execution stages:

λDCC∗=min⁡(λseq,λexec∗)=min⁡(λΔBτ,min⁡(K,1/pc)D).\lambda_{\mathrm{DCC}}^*=\min(\lambda_{\mathrm{seq}},\lambda_{\mathrm{exec}}^*)=\min\left(\frac{\lambda\Delta_B}{\tau},\frac{\min(K,1/p_c)}{D}\right).

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 τ\tau and pcp_c only.

To compare throughput, we standardize the contention parameter to pcp_c, as in § 3.3, and simplify the compute demand to DD for all paradigms (ignoring the slowdown in the execution queue beyond full utilization, since we are only interested in the throughput ceiling). This gives a≈D/NLa \approx D/N_L, and for OCC R^≈D/NL\hat{R} \approx D/N_L, TH=(NL+1)R^/2≈D/2T_H=(N_L+1)\hat{R}/2\approx D/2, and x=NL2(TH+τ)/L=pc(TH+τ)x=N_L^2(T_H+\tau)/L=p_c(T_H+\tau). Substituting these into the throughput expressions gives:

For 2PL.

λlock∗=0.75NLDpc(NL−1)(D+NLτ)2.\lambda^*_{\mathrm{lock}}=\frac{0.75N_LD}{p_c(N_L-1)(D+N_L\tau)^2}.

For large NLN_L, using (NL−1)≈NL(N_L-1)\approx N_L in the leading factor gives:

λlock∗≈0.75Dpc(D+NLτ)2.\lambda^*_{\mathrm{lock}}\approx\frac{0.75D}{p_c(D+N_L\tau)^2}.

For OCC.

λOCC∗(τ,pc)=KD+Kpc(D/2+τ).\lambda^*_{\mathrm{OCC}}(\tau,p_c)=\frac{K}{D+Kp_c(D/2+\tau)}.

Next, we compare each pair of the paradigms.

OCC vs. DCC. When DCC is compute-bound:

KD+Kpc(D/2+τ)=KD,\frac{K}{D+Kp_c(D/2+\tau)}=\frac{K}{D},

whose only solutions are pc=0p_c=0 and τ=−D/2\tau=-D/2. For contention-bound DCC,

KD+Kpc(D/2+τ)=1pcD.\frac{K}{D+Kp_c(D/2+\tau)}=\frac{1}{p_cD}.

Solving for τ\tau gives:

τO/D=D(1−1Kpc)−D2=D(12−1Kpc).\tau^{\mathrm{O/D}}=D\left(1-\frac{1}{Kp_c}\right)-\frac{D}{2}=D\left(\frac{1}{2}-\frac{1}{Kp_c}\right).

For contention-bound DCC, OCC achieves higher saturated throughput only when τ<τO/D\tau<\tau^{\mathrm{O/D}}; the two tie at equality. For large KpcKp_c, this threshold approaches D/2D/2 from below. Thus, OCC wins only when τ<D/2\tau<D/2, i.e., when the coordination delay is shorter than half the transaction’s compute time. When contention is low (0<pc≤1/K0<p_c\le1/K), DCC achieves higher saturated throughput because it avoids retry work; their throughput limits coincide at pc=0p_c=0. These comparisons assume that sequencing does not limit DCC throughput.

2PL vs. DCC. When DCC is compute-bound:

0.75Dpc(D+NLτ)2=KD.\frac{0.75D}{p_c(D+N_L\tau)^2}=\frac{K}{D}.

Taking the positive root for τ\tau gives:

τ2/D=DNL(0.75Kpc−1).\tau^{2/\mathrm{D}}=\frac{D}{N_L}\left(\sqrt{\frac{0.75}{Kp_c}}-1\right).

When Kpc<0.75Kp_c<0.75, 2PL ties with DCC if τ<τ2/D\tau<\tau^{2/\mathrm{D}}. Otherwise, 2PL can reach the lock wait blow-up threshold even at τ=0\tau=0, so DCC always wins.

When DCC is contention-bound:

0.75Dpc(D+NLτ)2=1pcD,\frac{0.75D}{p_c(D+N_L\tau)^2}=\frac{1}{p_cD},
D+NLτ=0.75D.D+N_L\tau=\sqrt{0.75}D.

Since pcp_c cancels out and 0.75<1\sqrt{0.75}<1, we cannot find a non-negative τ\tau that satisfies the equation. This means that 2PL is again always lower than DCC in the contention-bound regime, and the gap grows as τ\tau increases.

2PL vs. OCC. Let:

0.75Dpc(D+NLτ)2=KD+Kpc(D/2+τ).\frac{0.75D}{p_c(D+N_L\tau)^2}=\frac{K}{D+Kp_c(D/2+\tau)}.

Setting τ=0\tau=0 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 τ\tau, the 1/τ1/\tau vs. 1/τ21/\tau^2 scaling means that OCC eventually outperforms 2PL for any fixed pc>0p_c>0. The product KpcKp_c is the useful regime parameter because it approximates the number of direct conflicts a transaction sees when the system tries to run KK 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.

Analytical comparisons of concurrency-control paradigms

Figure 2. Analytical comparisons of CC paradigms with K=8K = 8, NL=10N_L = 10, and negligible local commit time relative to cross-DC delay. We nondimensionalize τ\tau and λ\lambda by DD 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 ΔB=τ\Delta_B = \tau, the smallest value satisfying the stability requirement ΔB≥τ\Delta_B \ge\tau.

An important caveat is that, although we assume τ\tau is the same for all paradigms, in practice τ\tau 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 DD, 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: T4T_4 (replica 1) and T5T_5 (replica 2) conflict; since replica 1 has priority, T4T_4 commits directly, while T5T_5 and its dependent successors, T6T_6 and T8T_8, 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

  1. Isolation strength: SER >> SI >> RC >> RU

  2. Each TT carries an isolation level T.isoT.\mathit{iso}, read-set T.RT.R, write-set T.WT.W, and sequence number T.seqT.\mathit{seq}

  3. function BuildDependencyEdges(batch)(batch)

  4. E←∅E \leftarrow\varnothing

  5. for all ordered pairs (Ti,Tj)(T_i,T_j) in batchbatch with Ti.seq<Tj.seqT_i.\mathit{seq}<T_j.\mathit{seq} do

  6. &nbsp;&nbsp;if Ti.W∩Tj.W≠∅T_i.W \cap T_j.W \ne\varnothing then

  7. &nbsp;&nbsp;&nbsp;&nbsp;if Ti.iso≥SIT_i.\mathit{iso}\ge\mathrm{SI} or Tj.iso≥SIT_j.\mathit{iso}\ge\mathrm{SI} then

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;E←E∪{Ti→wwTj}E \leftarrow E \cup\{T_i \xrightarrow{\mathrm{ww}} T_j\}

  9. &nbsp;&nbsp;&nbsp;&nbsp;else

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;resolve by last-write-wins

  11. &nbsp;&nbsp;if Tj.R∩Ti.W≠∅T_j.R \cap T_i.W \ne\varnothing then

  12. &nbsp;&nbsp;&nbsp;&nbsp;if Tj.iso=SERT_j.\mathit{iso}=\mathrm{SER} then

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;E←E∪{Ti→rwTj}E \leftarrow E \cup\{T_i \xrightarrow{\mathrm{rw}} T_j\}

  14. &nbsp;&nbsp;&nbsp;&nbsp;else

  15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TjT_j reads from the snapshot

  16. return EE

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, T4T_4 on replica 1 is kept while T5T_5 on replica 2 loses the conflict, which discards its entire speculative subtree {T5,T6,T8}\{T_5,T_6,T_8\}. This is wasteful, because T4T_4 is a leaf in the dependency graph, whereas T5T_5 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 T5T_5 (weight three) over T4T_4 (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 PNPN-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 keykey. 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 τ\tau 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 10710^7 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 pcp_c 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 ≥150\geq150 ms and skew=1.5skew=1.5.

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 PW,MAXT=0.75/(1+τ/a)P^{T}_{W,\mathrm{MAX}} = 0.75/(1+\tau/a) 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 i^\hat{i}, the transaction already holds ii locks and executes the ii-th access with mean time aa. In substate i~\tilde{i}, the transaction is trying to acquire lock ii while still holding the previous i−1i-1 locks.

Let PWP_W be the probability that a lock request is blocked, and let RWR_W be the mean lock-wait time conditional on such a block. In Yu’s original model, the unconditional waiting cost per lock stage is b=PWRWb=P_WR_W. With geo-replication, every lock acquisition also pays one coordination round-trip, even if the lock is free. We therefore use

b′=τ+PWRW(1)b'=\tau+P_WR_W \tag*{(1)}

to represent that every request pays τ\tau, and only the contended fraction pays the extra queueing wait RWR_W.

The threshold is stated in terms of Yu’s per-transaction contention measure

PWT≡PW(NL−1).(2)P^{T}_W \equiv P_W(N_L-1). \tag*{(2)}

This is the average number of lock contentions a transaction sees over the NL−1N_L-1 later lock requests. The first lock has no earlier locks to hold while waiting, so Yu’s blow-up calculation is naturally written with NL−1N_L-1.

Yu’s High-contention Wait Approximation

Yu’s blow-up threshold is obtained from the high-contention limit of the lock-wait equation: NLN_L is large, lock waiting dominates commit time, and we use Yu’s default residual-life correction, f1=1f_1=1, for the remaining lock-holding time seen by a blocked requester. Under this assumption, Yu’s eq:3.19 reduces to

RW≈(a+b′)2(NL−1)3a.(3)R_W \approx\frac{(a+b')^2(N_L-1)}{3a}. \tag*{(3)}

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 RWR_W grows with (a+b′)2(a+b')^2.

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 G′G' 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:

RW=b′−τPW.(4)R_W=\frac{b'-\tau}{P_W}. \tag*{(4)}

Equating (4) and (3) gives

b′−τPW=(a+b′)2(NL−1)3a.(5)\frac{b'-\tau}{P_W}=\frac{(a+b')^2(N_L-1)}{3a}. \tag*{(5)}

Multiplying by PWP_W and using PWT=PW(NL−1)P^{T}_W=P_W(N_L-1):

PWT(a+b′)2=3a(b′−τ).(6)P^{T}_W(a+b')^2=3a(b'-\tau). \tag*{(6)}

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 b′b' that can be explained by queueing is the amount above the unavoidable round-trip τ\tau.

Now make the equation dimensionless:

u≡a+b′a,b′=a(u−1).(7)u\equiv\frac{a+b'}{a},\qquad b'=a(u-1). \tag*{(7)}

Substitute this into (6):

PWT(au)2=3a(a(u−1)−τ).(8)P^{T}_W(au)^2=3a\bigl(a(u-1)-\tau\bigr). \tag*{(8)}

After dividing by a2a^2 and rearranging, we get the quadratic

PWTu2−3u+3(1+τa)=0.(9)P^{T}_Wu^2-3u+3\left(1+\frac{\tau}{a}\right)=0. \tag*{(9)}

This is the quadratic used in the body of the paper. When τ=0\tau=0, it reduces to Yu’s original form PWTu2−3u+3=0P^{T}_Wu^2-3u+3=0.

Reading the Threshold from the Discriminant

The quadratic (9) has coefficients

A=PWT,B=−3,C=3(1+τa).(10)A=P^{T}_W,\qquad B=-3,\qquad C=3\left(1+\frac{\tau}{a}\right). \tag*{(10)}

A finite real fixed point requires real roots, so the discriminant must be non-negative:

B2−4AC=9−12PWT(1+τa)≥0.(11)B^2-4AC=9-12P^{T}_W\left(1+\frac{\tau}{a}\right)\ge0. \tag*{(11)}

Solving for PWTP^{T}_W gives

PWT≤912(1+τ/a)=0.751+τ/a.(12)P^{T}_W\le\frac{9}{12(1+\tau/a)}=\frac{0.75}{1+\tau/a}. \tag*{(12)}

Thus the blow-up boundary is

PW,MAXT=0.751+τ/a.(13)P^{T}_{W,\mathrm{MAX}}=\frac{0.75}{1+\tau/a}. \tag*{(13)}

Solving (9) gives

u=3±9−12PWT(1+τ/a)2PWT.(14)u=\frac{3\pm\sqrt{9-12P^{T}_W(1+\tau/a)}}{2P^{T}_W}. \tag*{(14)}

At the blow-up boundary, the discriminant is zero and the two roots coincide. Substituting PW,MAXT=0.75/(1+τ/a)P^{T}_{W,\mathrm{MAX}}=0.75/(1+\tau/a) gives

uCont=32PW,MAXT=2(1+τa).(15)u_{\mathrm{Cont}}=\frac{3}{2P^{T}_{W,\mathrm{MAX}}}=2\left(1+\frac{\tau}{a}\right). \tag*{(15)}

Using b′=a(u−1)b'=a(u-1), the corresponding per-lock acquisition stage cost is

bCont′=a(uCont−1)=a+2τ.(16)b'_{\mathrm{Cont}}=a(u_{\mathrm{Cont}}-1)=a+2\tau. \tag*{(16)}

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 PWT→0P^{T}_W\to0, it gives b′→τb'\to\tau. 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 bb to b′=τ+PWRWb'=\tau+P_WR_W. 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 3(1+τ/a)3(1+\tau/a) in (9). A larger constant makes the discriminant disappear at a smaller value of PWTP^{T}_W, so the system tolerates less contention before the lock-wait fixed point is unstable.

Lock Exposure at the Lock-Wait Blow-up Boundary

GG 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 G′G' because each serialized lock-acquisition stage pays b′b'. The transaction holds an increasing number of locks as it executes, holds its earlier locks while acquiring each later lock, and holds all NLN_L locks during commit. Therefore,

G′=∑i=1NLia+∑i=1NL−1ib′+NLTCommit=NL(NL+1)2a+NL(NL−1)2b′+NLTCommit.(17)G'=\sum_{i=1}^{N_L}ia+\sum_{i=1}^{N_L-1}ib'+N_LT_{\mathrm{Commit}} =\frac{N_L(N_L+1)}{2}a+\frac{N_L(N_L-1)}{2}b'+N_LT_{\mathrm{Commit}}. \tag*{(17)}

At the blow-up boundary, bCont′=a+2τb'_{\mathrm{Cont}}=a+2\tau. Neglecting local commit work gives TCommit=TCommitlocal+τ≈τT_{\mathrm{Commit}}=T_{\mathrm{Commit}}^{\mathrm{local}}+\tau\approx\tau. Substituting both values into (17):

GCont′=NL(NL+1)2a+NL(NL−1)2(a+2τ)+NLτ=NL2a+NL(NL−1)τ+NLτ=NL2(a+τ).(18)G'_{\mathrm{Cont}}=\frac{N_L(N_L+1)}{2}a+\frac{N_L(N_L-1)}{2}(a+2\tau)+N_L\tau =N_L^2a+N_L(N_L-1)\tau+N_L\tau =N_L^2(a+\tau). \tag*{(18)}

The NL(NL−1)τN_L(N_L-1)\tau term is the exposure caused by the lock-acquisition rounds while earlier locks remain held. The final NLτN_L\tau term is the additional exposure from the replicated-commit round, during which all NLN_L locks remain held. If local commit work is retained, the result becomes GCont′=NL2(a+τ)+NLTCommitlocalG'_{\mathrm{Cont}}=N_L^2(a+\tau)+N_LT_{\mathrm{Commit}}^{\mathrm{local}}.

Derivation of the Longest Dependency Chain Length

This section derives a closed form using the mean-field recurrence for ℓ(N)\ell(N), which is the expected length of the longest dependency chain for a newly arrived transaction TT given a pool of NN in-flight transactions ahead of it. We show that the linear ansatz ℓ(N)=AN\ell(N)=AN is an exact solution of the recurrence and that the slope is forced to be A=pcA=p_c, yielding ℓ(N)=pcN\ell(N)=p_cN.

The Recurrence

From the model in § 3.3, conditioning on M≡max⁡{i:T→Ti}M\equiv\max\{i:T\to T_i\} (the highest-id out-neighbour of TT, with M=0M=0 when TT has no out-edges) and applying the mean-field substitution ITi→ℓ(i−1)I_{T_i}\to\ell(i-1) gives

ℓ(N)=∑m=1Npc(1−pc)N−m(1+ℓ(m−1)),ℓ(0)=0.(19)\ell(N)=\sum_{m=1}^{N}p_c(1-p_c)^{N-m}(1+\ell(m-1)),\qquad\ell(0)=0. \tag*{(19)}

The m=0m=0 branch contributes 0 to the expectation, so it does not appear in the sum. Reindexing with k≡m−1k\equiv m-1 and writing q≡1−pcq\equiv1-p_c for brevity,

ℓ(N)=∑k=0N−1pcqN−1−k(1+ℓ(k)).(20)\ell(N)=\sum_{k=0}^{N-1}p_cq^{N-1-k}(1+\ell(k)). \tag*{(20)}

Linear Ansatz

We try a linear solution with unknown slope AA:

ℓ(N)=AN,(21)\ell(N)=AN, \tag*{(21)}

which is consistent with the boundary condition ℓ(0)=0\ell(0)=0. Substituting (21) into (20) splits the right-hand side into two sums:

AN=∑k=0N−1pcqN−1−k⏟S1+A∑k=0N−1pcqN−1−kk⏟S2.(22)AN=\underbrace{\sum_{k=0}^{N-1}p_cq^{N-1-k}}_{S_1}+A\underbrace{\sum_{k=0}^{N-1}p_cq^{N-1-k}k}_{S_2}. \tag*{(22)}

We evaluate S1S_1 and S2S_2 in closed form below. For S1S_1, the exponents run from N−1N-1 down to 0, so the sum is geometric:

S1=pc∑k=0N−1qN−1−k=pc∑k=0N−1qk=pc1−qN1−q=1−qN(23)S_1=p_c\sum_{k=0}^{N-1}q^{N-1-k}=p_c\sum_{k=0}^{N-1}q^k=p_c\frac{1-q^N}{1-q}=1-q^N \tag*{(23)}

using 1−q=pc1-q=p_c, which is the probability that TT has at least one out-neighbour in the pool of NN.

For S2S_2, make the dependence on the upper limit explicit:

S2(N)≡∑k=0N−1pcqN−1−kk.S_2(N)\equiv\sum_{k=0}^{N-1}p_cq^{N-1-k}k.

We write S2(N)S_2(N) rather than just S2S_2 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 N+1N+1 differs from the expression for NN by one new final term, k=Nk=N:

S2(N+1)=∑k=0NpcqN−kk=∑k=0N−1pcqN−kk+pcN=q∑k=0N−1pcqN−1−kk+pcN=qS2(N)+pcN.(24)S_2(N+1)=\sum_{k=0}^{N}p_cq^{N-k}k =\sum_{k=0}^{N-1}p_cq^{N-k}k+p_cN =q\sum_{k=0}^{N-1}p_cq^{N-1-k}k+p_cN =qS_2(N)+p_cN. \tag*{(24)}

The base case is S2(1)=0S_2(1)=0, because the only term has k=0k=0. We claim the closed form

S2(N)=N−1−qNpc.(25)S_2(N)=N-\frac{1-q^N}{p_c}. \tag*{(25)}

Verification by induction: (25) gives S2(1)=1−(1−q)/pc=1−1=0S_2(1)=1-(1-q)/p_c=1-1=0, matching the base case. For the step, assume (25) holds at NN and substitute into (24):

qS2(N)+pcN=q(N−1−qNpc)+pcN=(q+pc)N−q−qN+1pc=N−q−qN+1pc.(26)qS_2(N)+p_cN=q\left(N-\frac{1-q^N}{p_c}\right)+p_cN =(q+p_c)N-\frac{q-q^{N+1}}{p_c} =N-\frac{q-q^{N+1}}{p_c}. \tag*{(26)}

The target value at N+1N+1 is (N+1)−(1−qN+1)/pc(N+1)-(1-q^{N+1})/p_c. The two agree iff 1−(1−qN+1)/pc=−(q−qN+1)/pc1-(1-q^{N+1})/p_c=-(q-q^{N+1})/p_c, which rearranges to pc=1−qp_c=1-q — true by definition. Hence (25) holds for all N≥1N\ge1.

Consistency Condition

Substituting (23) and (25) into (22),

AN=(1−qN)+A(N−1−qNpc)=AN+(1−qN)(1−Apc).(27)AN=(1-q^N)+A\left(N-\frac{1-q^N}{p_c}\right)=AN+(1-q^N)\left(1-\frac{A}{p_c}\right). \tag*{(27)}

The ANAN terms cancel on both sides, leaving

(1−qN)(1−Apc)=0for every N≥1.(28)(1-q^N)\left(1-\frac{A}{p_c}\right)=0\qquad\text{for every }N\ge1. \tag*{(28)}

For any pc∈(0,1]p_c \in(0,1] the factor 1−qN1-q^N is strictly positive, so (28) forces

A=pc(29)A=p_c \tag*{(29)}

The linear ansatz is therefore an exact solution of the mean-field recurrence (20): no NN-dependent residual survives, and the slope is uniquely pinned.

Closed form. Combining (21) and (29),

ℓ(N)=pcN(30)\ell(N)=p_cN \tag*{(30)}

Specialising to the in-flight pool size NEN_E gives ℓ(NE)=pcNE\ell(N_E)=p_cN_E, which is the expression fed back into the wait-time bound in the body.

Intuition. Walk down the longest chain from TT one hop at a time. The id-gap from a vertex of id-rank NN to its highest-id out-neighbour is geometric with parameter pcp_c on {0,1,…,N−1}\{0,1,\ldots,N-1\}, so each hop drops the working id by about 1/pc1/p_c on average. Starting from the back of a pool of size NN leaves room for roughly N/(1/pc)=pcNN/(1/p_c)=p_cN hops before the chain hits the bottom.

References

  1. [1]2025. Active-Active Geo-Distributed Redis. https://redis.io/docs/latest/operate/rs/databases/active-active/
  2. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [18]Michael Haubenschil and Viktor Leis. 2025. OLTP in the cloud: architectures, tradeoffs, and cost. The VLDB Journal 34, 4 (2025), 42.
  19. [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. [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. [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. [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. [23]Martin Kleppmann. 2016. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O’Reilly.
  24. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [40]M. Tamer Özsu and Patrick Valduriez. 2020. Principles of Distributed Database Systems (fourth edition ed.). Springer, Cham, Switzerland.
  41. [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. [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. [43]Nuno Rodrigues, 2018. Conflict-free Replicated Data Types: An Overview. arXiv:1806.10254 [cs.DC] https://arxiv.org/abs/1806.10254
  44. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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.

Paper details

vlnc:W_uuedndhh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents