Ditto: Generalized Reconfigurable Linearizable Reads

Ditto: Generalized Reconfigurable Linearizable Reads Aleksey Panas aleksey.panas@alumni.utoronto.ca University of Toronto Toronto, Ontario, Canada

arXiv:2610.00702v1 [cs.DC] 30 Sep 2026

Abstract Linearizability gives developers the illusion that operations on a distributed datastore execute sequentially on a single machine. Providing it is expensive, so numerous specialized reads algorithms have been proposed to make reads significantly faster without sacrificing linearizability, which matters because most workloads are read-dominant by orders of magnitude. Yet, none of these algorithms is the best choice for every deployment. We show why with a framework that classifies these algorithms into a generalized space together with a mathematical analysis of their latencies as a function of this generalization. The analysis exposes two fundamental tradeoffs, one between read and write latency and one between read and write tolerance to network variance, which together leave the best algorithm dependent on network and workload conditions that vary over time. It also exposes a gap: there is a way to minimize the delay a read incurs when it overlaps a concurrent write, at no cost to writes, yet existing algorithms can apply it only for a subset of the tradeoff space, forcing any deployment that needs the full space to settle for a strictly worse solution. We close this gap with a new algorithm, Pairwise Quorums, and build a second, Ditto, that reconfigures across the space at runtime as conditions change. Together they subsume every existing algorithm under our model: against each, the combination is either strictly better, or reconfigures to match it where a genuine tradeoff applies.

1

Figure 1: Decreasing the size of read quorums increases size of write quorums

[52], dictating which processes a read contacts, and consequently which a write must contact so that no read misses a completed write. The second is how a read behaves when it executes concurrently with a write, which is called the stamping mechanism. Taking the quorum system first, this choice encodes two fundamental tradeoffs. The first is read-write latency. To preserve linearizability, a read must observe every write that completed before it began, which requires contacting at least one process aware of each such write. Formally, every write quorum (the processes contacted for a write) must intersect every read quorum (the processes contacted for a read) [52]. Shrinking read quorums to lower read latency therefore forces write quorums to grow, and vice versa. PQR [8], for example, lets any replica serve a read by contacting a simple majority making read latency high, but leaving writes unaffected since they already contact a majority under standard SMR. Pairwise [45] sits at the opposite extreme, serving fully local reads at every replica at the cost of requiring writes to contact all processes (Figure 1). The second tradeoff is tolerance to network variance, that is, variance in the latency of inter-process links. Consider a system running Pairwise when a process becomes fail-slow, exhibiting a prolonged latency increase [17]. Because the leader must contact every process on every write, write progress degrades until a costly recovery is triggered. PQR instead gives the leader a choice of which processes to contact to satisfy quorum intersection, tolerating such variance, but at the price of higher read latency. As a consequence of these tradeoffs, the best quorum system configuration depends on workload and network conditions. A read-heavy system over good links wants small read quorums, while a write-heavy or flaky one wants large ones. Worse, a single system wants different settings at different times. It may be readdominant by day, when users are active, and write-dominant by night, as new content lands, and its links may degrade and recover throughout. A system should be able to move along this space as conditions change, but no current algorithm concretely provides this. The choice of stamping mechanism tells a different story. When a read occurs concurrently with an in-progress write, the process serving it determines whether to stamp with that write,

Introduction

Linearizable datastores such as Spanner [10], CockroachDB [43], and YugabyteDB are now widely deployed in industry. Linearizability [19] is desirable because it gives applications the illusion of a single, sequential machine, letting developers build geo-distributed, fault-tolerant systems without reasoning about concurrency. To provide it, these systems run a state machine replication (SMR) protocol such as MultiPaxos [49] or Raft [40], which exposes an interface for executing read and write operations on replicated application state. Unfortunately, executing an operation in SMR is expensive, requiring rounds of communication to reach consensus, and a single elected leader to sequence operations. To escape this cost, developers often fall back to weaker models such as eventual consistency, trading strong guarantees for performance. However, the non-mutating property of read operations has led to the development of numerous specialized reads algorithms which significantly improve read performance without sacrificing linearizability. These algorithms are of particular importance as most workloads are read-dominant. For example, Google reported that in their ads workload, read operations outnumber write operations by three orders of magnitude [10]. Today’s existing specialized reads algorithms include Leader Reads [6], PQL [34], PQR [8], EdgePQR [16], CHT [7], and Pairwise [45]. In this paper, we show that none of these reads algorithms is the best choice for every deployment by presenting a framework that decomposes each algorithm into a combination of two independent choices. The first is the read-write quorum system 1

forcing the read to wait for that write to finish, or to stamp with an older write and return the read sooner. This decision is tied to correctness, since stamping incorrectly may cause a read to miss a completed write, violating linearizability. This period of waiting for the write the read incurs is called read blockage time [4], and the stamping mechanism is what controls it. Here one option, delayed stamping, is best. It gives the lowest read blockage time at no cost to writes. However, existing reads algorithms that implement delayed stamping are only capable of quorum system configurations involving local readers, that is, read quorums of size one. A system that wants a quorum-based setting, say to tolerate network variance for writes, is forced onto a worse stamping mechanism and pays blockage time it should not have to. Put together, the two choices explain why there is no clear winner. Each algorithm is beaten wherever its quorum configuration is wrong for the current network and workload conditions, or its stamping mechanism is not the best one available. Winning everywhere means getting both choices right at once. Today, this is not possible. To address the issue, we contribute two novel algorithms. The first, Pairwise Quorums, extends delayed stamping to support any quorum system configuration, forever removing the need to sacrifice read blockage time in exchange for more extensive quorum system support. The second algorithm, Ditto, provides a black box at-runtime quorum system reconfiguration solution, allowing the system to dynamically adapt to the current deployment conditions and always maintain the optimal configuration. The collective combination of Ditto and Pairwise Quorums is an algorithm which subsumes all existing algorithms under our model. This paper extends our earlier preprint [46], which proposed switching among read-write quorum systems at runtime. Of course, Ditto’s reconfiguration ability on its own does not answer the question of when reconfiguration should happen. In order to provide clarity within the quorum system configuration space, we provide a mathematical analysis of write latency, best case read latency, worst case read latency, and network variance as a function of the quorum configuration, motivating our two algorithms and serving as a precise tool for the developer to determine the performance of a system a priori under given conditions and configuration. The paper proceeds as follows. Section 2 covers background and introduces every existing linearizable reads algorithm. Section 3 places them in our framework, analyzes them, and identifies the gap in stamping mechanisms. Section 4 presents and analyzes Pairwise-Quorums. Section 5 presents Ditto and reconfiguration. Section 6 validates the analysis experimentally and shows the performance gains of Pairwise-Quorums and Ditto. Section 7 presents related work and section 8 concludes and discusses future work.

2

A lease must be granted correctly, that is, the granter must perceive the lease as expired only after the holder does, in real time. This requires assuming either synchronized clocks with bounded skew [15] or hardware clocks with bounded drift [28].

2.2

2.3

Local Read Algorithms

Figure 2: A write contacts any simple majority AND all local readers. The two conditions may overlap, as seen in all three cases above. Local Reads algorithms, including PQL [34], CHT [7], Leader Reads [6], and Pairwise [45], designate a subset of processes as local readers. A local reader serves reads without contacting any other process; every other process forwards its reads to the closest local reader. To ensure reads observe every completed write, the leader must then contact all local readers on each write, in addition to a majority. Figure 2 shows how each algorithm places its local readers and the resulting quorums. Since writes wait on specific local readers, the failure of one would stall write progress. To prevent this, a local reader serves reads only while holding a read lease [15, 34]. If a local reader fails, the leader invalidates its lease by contacting a majority, or waits for it to expire, and proceeds without it; a recovered reader can later re-establish its lease safely. A local reader 𝑝 serves a read by assigning it an index 𝑖 of some RMW, called stamping with 𝑖. Correctness requires 𝑖 to be at least the index of the latest completed RMW. The stamped read may then be returned by any process that has committed every write up to and including 𝑖, not necessarily 𝑝 itself. This

Background

In this section, we discuss the system model, state machine replication, existing algorithms for linearizable reads, and their relationship to read-write quorum systems.

2.1

State Machine Replication

State machine replication (SMR) is the de facto standard for linearizable, fault-tolerant replication of client operations across a set of processes. Linearizability totally orders operations in a way that respects their real-time order: if 𝑜 1 completes before 𝑜 2 begins, then 𝑜 1 is ordered before 𝑜 2 [19]. Each process holds a replica of the application state, and replicas are deterministic in that applying the same sequence of operations to any replica yields the same state [42]. Clients submit operations to a process, which runs the read or write procedure and returns the result. To order writes, SMR relies on a distinguished leader that proceeds in two phases. In the prepare phase, the leader proposes assigning a write 𝑤 to index 𝑖 of the log; the phase completes, and 𝑖 is decided, once a majority accept. The leader then commits 𝑤, and a process applies 𝑤 to its replica once it has applied every write up to index 𝑖. A read can be served naively as a no-op write. Since SMR writes are read-modify-writes (RMW), this returns the latest state without changing it, but at the cost of a full write. Of course, this is inefficient and the specialized reads algorithms we discuss next avoid this.

Model

We assume an asynchronous system of 𝑛 processes, of which at most 𝑓 < 𝑛2 may crash. Messages may be arbitrarily delayed, reordered, or lost. We additionally require that processes can grant leases to tolerate failures without sacrificing liveness [15]. 2

makes reads and RMWs linearizable by completion order: RMW 𝑖 completes, then all reads stamped with 𝑖, then RMW 𝑖 + 1, and so on. Existing local read algorithms use one of three stamping mechanisms to assign 𝑖: Invalidation, Eager Stamping, and Delayed Stamping. We compare them using stop and go events [45]. A stop event for index 𝑖 is the point on 𝑝’s clock after which 𝑝 must stamp reads with indices ≥ 𝑖; intuitively, 𝑝 has learned of a write 𝑖 whose completion is uncertain and must conservatively include it. The go event for 𝑖 is the earliest point at which 𝑝 may return state through index 𝑖, once 𝑖 is committed. For correctness, the stop event for 𝑖 on every local reader must precede write 𝑖’s completion at the leader and the go event must follow it. Reads stamped with 𝑖 block during the interval between the two events; we call its length the read blockage time, and minimizing it is desirable. We now describe the three mechanisms, summarized in Figure 3.

quorum intersects every read quorum [52]. A write completes once the leader hears from a full write quorum, and a read completes once it contacts a full read quorum. In practice it suffices to define the read quorums alone. A valid write quorum is then any majority containing at least one process from every read quorum. For example, with processes {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}, leader 𝐴, and read quorums {{𝐴, 𝐵}, {𝐷, 𝐸}}, the set {𝐵, 𝐶, 𝐷} is a valid write quorum. Then, Local Reads algorithms are those with read quorums of size one.

2.5

Quorum Read Algorithms

Quorum Reads algorithms are ones that use read quorums larger than one and include PQR [8] and EdgePQR [16]. In PQR, a process 𝑝 serves a read by contacting any majority to retrieve their latest prepare indexes, stamping with the maximum index 𝑖 max , and returning state through 𝑖 max once committed on 𝑝. PQR’s read quorums are thus any majority, and it uses a quorum-generalized variant of Eager Stamping. EdgePQR instead takes an explicitly defined read quorum set 𝑄 𝑅 . 𝑝 contacts any 𝑄 ∈ 𝑄 𝑅 and follows PQR’s procedure, with write quorums adjusted to intersect every read quorum. Like local reads, EdgePQR’s smaller-than-majority quorums reduce fault tolerance, which is addressed with a read lease mechanism extended to arbitrary-sized quorums.

2.6

Pairwise

Figure 3: In the worst case, Invalidation blocks for multiple possibly infinite writes, Eager blocks for one write, and Delayed often blocks for less than one write

2.3.1 Invalidation. Used by PQL [34], Invalidation places the stop event for 𝑖 when 𝑝 receives the prepare for 𝑖, and the go event when 𝑝’s latest committed index equals its latest received prepare index. If writes are proposed continuously, the latest prepare index keeps outpacing the latest committed index, so the go event may never fire and reads can block indefinitely.

Figure 4: Leader ℓ uses marker mechanism to schedule stop and go events before and after promise time 𝑡 + 𝛼 on local reader 𝑟 1 and 𝑟 2. Read blockage time tends to 0 with proximity to leader

2.3.2 Eager Stamping. Used by CHT [7], Eager Stamping keeps Invalidation’s stop event but sets the go event when 𝑝 receives the commit for 𝑖. The go event is now fixed, so read blockage is finite. In the worst case a read blocks for the full duration of the write.

We now describe how Pairwise [45] achieves delayed stamping, assuming no clock drift for concision. At startup, the leader ℓ establishes markers with every local reader 𝑝: ℓ records a timestamp 𝑚𝑝ℓ and messages 𝑝, which ′ . To process records 𝑚𝑝 and replies, after which ℓ records 𝑚𝑝ℓ write 𝑖, ℓ takes the current time 𝑡, and sets the promise time 𝑡 + 𝛼, promising not to commit before it. ℓ then attaches 𝛿𝑠𝑡𝑜𝑝 = ′ and 𝛿 𝑡 + 𝛼 − 𝑚𝑝ℓ 𝑔𝑜 = 𝑡 + 𝛼 − 𝑚𝑝ℓ to each prepare, and on receipt 𝑝 computes 𝑠𝑡𝑜𝑝𝑖 = 𝑚𝑝 + 𝛿𝑠𝑡𝑜𝑝 and 𝑔𝑜𝑖 = 𝑚𝑝 + 𝛿𝑔𝑜 as points on its own clock. The stop event for 𝑖 is then the later of 𝑠𝑡𝑜𝑝𝑖 and the time 𝑝 receives the prepare for 𝑖, and the go event the later of 𝑔𝑜𝑖 and the time 𝑝 receives the commit for 𝑖. The markers guarantee that every stop event elapses on its reader before the promise time elapses at the leader, and every go event after, so reads correctly observe completed writes. 𝛼 does not affect correctness. Pairwise shows its ideal value is the RTT from ℓ to the furthest process ℓ must await on a write, so that 𝑡 + 𝛼 elapses exactly when the necessary replies arrive and the write incurs no extra latency. As Figure 4 illustrates, the

2.3.3 Delayed Stamping. Used by Pairwise [45] and Leader Reads [6], Delayed Stamping has the leader assign each write 𝑖 a future promise time 𝑡 + 𝛼 and promise not to commit 𝑖 before it, attaching this promise to prepare messages. A local reader then schedules its stop event for the latest time it can be sure 𝑡 + 𝛼 has not yet elapsed on the leader’s clock, and its go event for the earliest time it can be sure it has. Under perfect clock synchronization the two coincide at 𝑡 + 𝛼, giving zero read blockage. Otherwise, only the leader achieves zero, and uncertainty grows with distance from it. We detail this mechanism for Pairwise in Section 2.6.

2.4

Read-Write Quorum Systems

Guaranteeing that reads observe all completed writes requires read-write quorum intersection. A read-write quorum system is a set of read quorums and write quorums in which every write 3

(5) For 𝑝 ∈ Π, its closest process or quorum is the one with smallest RTT by 𝛿, i.e. the first to reply if 𝑝 broadcasts to everyone. (6) Let ℓ ∈ Π be the leader, and 𝑀 the closest simple majority to ℓ. (7) If the algorithm is a local reads algorithm, 𝑄 𝑅 is a set of size-one read quorums; let 𝐿 be its set of local readers.

worst-case blockage time at a local reader 𝑝 is then the RTT from ′ −𝑚 . ℓ to 𝑝, namely 𝑚 ℓ𝑝 ℓ𝑝

3

The Space of Linearizable Reads

As a function of 𝑁 , we derive write latency (Δ𝑤 (𝑁 )), best case read latency (𝐵𝐶 (Δ𝑟 (𝑁 ))), and worst case read latency under write contention (𝑊 𝐶 (Δ𝑟 (𝑁 ))). For this part of the analysis 𝛿 is fixed during an operation meaning the network is static; we treat network variance separately afterward. We measure write latency from when ℓ broadcasts prepares to just before it broadcasts commits, and read latency from when a process 𝑝 receives a read request to when it is about to return the read state. The gap between best and worst case read latency is exactly the read blockage time. The best case has no concurrent write occurring and has zero blockage, while the worst case has writes proposed continuously, so a read waits the maximum possible time for a concurrent write to commit. Throughout, we assume reads use a full broadcast approach as mentioned in the general read procedure 3.0.2. That is, 𝑝 contacts every process and proceeds once a read quorum has replied. The closest quorum replies first and thus dictates the latency. We now give each metric’s expression per stamping mechanism, each followed by a short justification.

Figure 5: High level classification of existing algorithms shows gaps in the space of delayed stamping and invalidation We now present our framework for classifying and analyzing all specialized read algorithms. As introduced in Section 1, every algorithm is a combination of a stamping mechanism and a set of supported read-write quorum systems, summarized in Figure 5. For example, PQR uses eager stamping with a single choice of setting read quorums to be every simple majority, while PQL uses invalidation with read quorums configurable to any group of local readers.

3.1

Eager Stamping Analysis

We begin with Eager Stamping, which covers all quorum systems and so gives the most general expressions in terms of 𝑄 𝑅 .

3.0.1 General Write Procedure. In every algorithm, the write procedure sends prepares to all processes, waits for acknowledgments from a majority that intersects every read quorum, and broadcasts a commit.

3.1.1

Write Latency. Δ𝑤 (𝑁 ) = max( max {min (𝛿 ℓ𝑞 + 𝛿𝑞ℓ )}, 𝛿 ℓ𝑀ℓ ) 𝑄 ∈𝑄 𝑅 𝑞 ∈𝑄

3.0.2 General Read Procedure. Conversely, the read procedure at process 𝑝 (1) broadcasts and waits for replies from a full read quorum, the closest one to 𝑝 determining the latency, (2) collects stop event information from the replies, (3) computes a stamp index 𝑖 as some aggregation over the replies, and (4) returns state through 𝑖 once 𝑖 is committed at 𝑝 and 𝑝’s go event for 𝑖 has elapsed. Step 3 is trivial for local reads, where each read quorum is a single reader that hands 𝑝 the index directly. As previewed in the introduction and shown in Figure 5, there are gaps in the quorum systems supported by invalidation and delayed stamping, confining them to local reads. Since delayed stamping dominates the other mechanisms in read blockage time, only its gap is worth filling. We also exclude read quorums larger than a majority since base SMR already prevents write quorums from shrinking below a majority, so enlarging read quorums past that point only worsens reads with no gain for writes. The analysis that follows derives key metrics and then traces their trends, confirming that delayed stamping is best and exposing the quorum system’s two core tradeoff axes, which leave no single configuration optimal as the network and workload conditions change. We define a network 𝑁 by the following: (1) Let Π be the set of processes in the network, and 𝑛 = |Π|. (2) Let 𝑄 𝑅 be the algorithm’s set of read quorums, and 𝑅 = Ð 𝑄 ∈𝑄 𝑅 𝑄 the set of all readers. (3) Let 𝛿𝑝 1 𝑝 2 be the one-way latency from 𝑝 1 ∈ Π to 𝑝 2 ∈ Π. (4) Let 𝛿𝑝𝑆𝑝 = max𝑠 ∈𝑆 {𝛿𝑝𝑠 + 𝛿𝑠𝑝 } be the time for 𝑝 to message a set 𝑆 and receive replies.

(1)

To commit a write, ℓ broadcasts prepares and waits for replies from (a) any majority and (b) at least one process in every read quorum; the write latency is the worse of the two, captured by the outer max. Condition (a) costs 𝛿 ℓ𝑀ℓ , the RTT to the closest majority. For condition (b), each read quorum is satisfied by its member closest to ℓ (the min), and the slowest such quorum is latency-determining (the inner max). 3.1.2

Best Case Read Latency. 𝐵𝐶 (Δ𝑟 )(𝑁 , 𝑝) = min {𝛿𝑝𝑄𝑝 }

(2)

𝑄 ∈𝑄 𝑅

With no concurrent write, 𝑝 serves the read as soon as one read quorum replies, so the latency is the RTT to 𝑝’s closest read quorum, the min in eq (2). 3.1.3

Worst Case Read Latency. 𝑊 𝐶 (Δ𝑟 (𝑁 , 𝑝)) = min max( max{Δ𝑤 + 𝛿 ℓ𝑝 − 𝛿 ℓ𝑞 + 𝛿𝑝𝑞 }, 𝑄 ∈𝑄 𝑅

𝑞 ∈𝑄

𝛿𝑝𝑄𝑝 )

(3)

In eager stamping, 𝑝 broadcasts for indexes, stamps with the maximum 𝑖𝑚𝑎𝑥 its read quorum returns, and serves once 𝑖𝑚𝑎𝑥 commits. The worst case is the larger of two costs (outer max): the quorum contact time 𝛿𝑝𝑄𝑝 , when the quorum replies so late that 𝑖𝑚𝑎𝑥 is already committed at 𝑝 (case a), or the read blockage time (case b). For case (b), the read blocks longest when the concurrent write 𝑖 starts as late as possible while still being stamped. To 4

Figure 6: Visualizes the derivation of worst case read latency in eager stamping in the case where read blockage time is the dominating factor

Figure 7: Visualizes the derivation of worst case read latency in delayed stamping in the case where read blockage time is the dominating factor

stamp with 𝑖, it suffices that one 𝑞 ∈ 𝑄 replies with 𝑖 to 𝑝’s request. Taking the worst 𝑞 (inner-most max), the latest time the write can start is such that 𝑝’s request reaches 𝑞 exactly as 𝑞 receives that prepare, i.e. 𝑡 (𝑟𝑖 ) + 𝛿𝑝𝑞 = 𝑡 (𝑤𝑖 ) + 𝛿 ℓ𝑞 , where 𝑡 (𝑟𝑖 ) and 𝑡 (𝑤𝑖 ) are the read and write invocation times. The read returns when the commit for 𝑖 reaches 𝑝, at 𝑡 (𝑤𝑖 ) + Δ𝑤 + 𝛿 ℓ𝑝 . Subtracting the read invocation time and simplifying gives a latency of Δ𝑤 + 𝛿 ℓ𝑝 − 𝛿 ℓ𝑞 + 𝛿𝑝𝑞 . The outer min then captures 𝑝’s closest quorum, giving the final expression. Figure 6 illustrates case (b).

at worst equivalent), specifically, half an RTT before the commit, at 𝑡 (𝑤𝑖 ) + Δ𝑤 (𝑁 ) − 𝛿 ℓ𝑞 (Section 2.6, Figure 4). The read blocks longest when 𝑝’s request reaches 𝑞 exactly when 𝑞’s stop event for 𝑖 elapses, so 𝑡 (𝑟𝑖 ) + 𝛿𝑝𝑞 = 𝑡 (𝑤𝑖 ) + Δ𝑤 (𝑁 ) − 𝛿 ℓ𝑞 . The read returns when the commit for 𝑖 reaches 𝑝, at 𝑡 (𝑤𝑖 ) + Δ𝑤 (𝑁 ) + 𝛿 ℓ𝑝 and subtracting 𝑡 (𝑟𝑖 ) gives a latency of 𝛿 ℓ𝑝 + 𝛿 ℓ𝑞 + 𝛿𝑝𝑞 . Unlike eager’s term, this contains no Δ𝑤 . Delayed stamping drops the full-write-latency penalty, so blockage shrinks for readers near the leader and is zero at ℓ itself. Figure 7 illustrates case (b).

3.2

We model variance as a change in 𝛿, giving a before network 𝑁 and an after network 𝑁 ′ that differ only in 𝛿, and hence in 𝑀. The effect of variance on a metric is its difference across the two, for instance Δ𝑤 (𝑁 ′ ) − Δ𝑤 (𝑁 ) for write latency. Variance occurring during an in-progress operation leaves that operation’s metric somewhere between its values for 𝑁 and 𝑁 ′ . Delayed stamping adds one wrinkle. Pairwise’s 𝛼 should always be the RTT to the furthest process the leader needs to await, and this RTT changes with variance. Misconfiguring 𝛼 costs latency but not safety, and the Status Mechanism of [4] adjusts it automatically. For simplicity, we assume 𝛼 is always perfectly tuned. In practice, there is a short adjustment period during which a minor performance cost is paid. Additionally, the expressions above heavily rely on the notion of closest which is also a function of variance. However, because reads use full broadcast, 𝑝 always finds its current closest quorum implicitly, so the expressions above stay valid as 𝛿 changes.

3.4

Invalidation

Invalidation shares eager stamping’s write procedure and best case read latency, so eq (1) and eq (2) carry over with 𝐿 substituted for 𝑄 𝑅 , as invalidation supports only local reads. Its worst case, however, is unbounded. 3.2.1

Worst Case Read Latency. 𝑊 𝐶 (Δ𝑟 (𝑁 , 𝑝)) = ∞

(4)

Invalidation’s go event for 𝑖 fires only when 𝑝’s latest committed index catches up to its latest received prepare index. Under constant write contention the prepare index is always greater, so the go event may never elapse. Invalidation is therefore worse than eager stamping, on par without contention, and unbounded with it. We therefore focus on eager versus delayed from here.

3.3

Delayed Stamping

Delayed stamping is best of the three mechanisms, but as Figure 5 shows it supports only local reads, so we state its differing results in terms of 𝐿 rather than 𝑄 𝑅 . Its write procedure matches eager stamping, i.e., the leader attaches a promise time 𝑡 + 𝛼 to prepares, and setting 𝛼 to the RTT to the furthest process the write must wait for makes 𝑡 +𝛼 elapse exactly when the necessary prepares are acknowledged, leaving write latency unchanged (eq 1). Best case read latency is likewise unchanged (eq 2). With no concurrent write, all stop and go events have already elapsed and the delayed semantics do not apply. 3.3.1

3.5

𝑊 𝐶 (Δ𝑟 (𝑁 , 𝑝)) = min{max(𝛿𝑝𝑞 + 𝛿 ℓ𝑞 + 𝛿 ℓ𝑝 , 𝛿𝑝𝑞 + 𝛿𝑞𝑝 )}

Other Considerations

Two factors fall outside our latency analysis but can still guide algorithm choice, and both point to the same escape hatch. First, algorithms that use read leases to support smaller-than-majority read quorums generate passive traffic. Leases are short-lived and must be renewed continually, even when no operations run. Second, leases require an assumption on bounded clock drift, as mentioned in Section 2.1. PQR uses neither leases nor clock assumptions, so deployments that cannot tolerate the background traffic or cannot make clock assumptions are confined to PQR.

Worst Case Read Latency. 𝑞 ∈𝐿

Network Variance

3.6

(5)

Trend Analysis

We now use these expressions to draw out the trends that motivate our two new algorithms. First, we demonstrate the quorum system’s two tradeoff axes from the introduction, which make the optimal configuration depend on the network and workload conditions that shift over time. This is what Ditto (Section 5) reconfigures across at runtime to remain adaptive and optimal.

Delayed stamping changes only the read blockage term. As before, the worst case is the larger of the contact time to the closest local reader, 𝛿𝑝𝑞 +𝛿𝑞𝑝 (case a), and the blockage time (case b). The difference is when 𝑞’s stop event for 𝑖 elapses. In eager, it is when 𝑞 receives the prepare, but in delayed it is often later (or 5

Second, we expose the worst case read latency gap in delayed stamping, where wanting a quorum-based configuration currently forces a needless sacrifice in read blockage time, one our Pairwise Quorums generalization (Section 4) removes.

Figure 10: The change in write latency and best case read latency (read at 𝐺) after spiking processes 𝐵 and 𝐶. Figure 8: Fully connected ‘line’ network of 7 processes with 𝐴 as leader, and a version of the same network with failslow processes 𝐵 and 𝐶

3.6.2 Network Variance Tradeoff. To see where local reads breaks down, we spike 𝐵 and 𝐶 to be fail slow [17] by adding 3000𝑚𝑠 to all of their incoming links, as reflected in the Fail-Slow Network of Figure 8, leaving the leader fast (a slow leader would force the spike on every write regardless of configuration, calling for a leader change instead). Figure 10 plots the resulting change in write and best case read latency from before the spike to after. For writes, low-𝑞 configurations, especially local reads, must contact a slow process to satisfy quorum intersection and absorb the spike as a result, while larger 𝑞 gives the leader enough redundancy to route around the slow processes. All configurations still take an unavoidable 200𝑚𝑠 increase, since the leader must now use the farther 𝐸 and 𝐹 for its majority. For reads, the full spike appears only when every read quorum contains a slow process, so reads are most tolerant at 𝑞 = 1, 𝑟 = 7 (Pairwise), where a fast local reader always exists. This is the second tradeoff of quorum systems, again generalizing to arbitrary 𝑄 𝑅 : at fixed 𝑅, growing quorum sizes trades read latency for write tolerance to network variance. High variance wants one end, low variance the other. Together these two axes show that the full space of quorum configurations matters, with different conditions calling for different points. This is what Ditto reconfigures across at runtime, keeping a system optimal as conditions change.

We use a fully connected line network of seven processes {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺 } with leader 𝐴 and symmetric 50𝑚𝑠 links, the Base Network of Figure 8. For the heatmaps we will present, we restrict 𝑄 𝑅 to two configuration axes reflecting the key tradeoffs, 𝑟 = |𝑅| and 𝑞 = |𝑄 |, where 𝑄 𝑅 is the set of all size-𝑞 subsets of the 𝑟 processes closest to the leader. For instance 𝑟 = 3, 𝑞 = 2 gives 𝑄 𝑅 = {{𝐴, 𝐵}, {𝐵, 𝐶}, {𝐴, 𝐶}}. This omits some configurations such as grid quorums [9] for simplicity of visualization, but the trends we show generalize to arbitrary 𝑄 𝑅 .

Figure 9: Write latency and best case read latency (read at 𝐺) from equations (1) and (2) as a function of 𝑄 𝑅 defined in terms of 𝑟 and 𝑞 (same for delayed and eager). 3.6.1 Static Read-Write Tradeoff. Figure 9 plots write latency and best case read latency over all 𝑟, 𝑞 following from the mathematical expressions, with reads at 𝐺 (the two are equal for eager and delayed in the best case). The two metrics trend oppositely. Read latency falls as 𝑟 grows or 𝑞 shrinks. At 𝑟 = 7, 𝑞 = 1, 𝐺’s closest quorum is itself with zero latency, whereas at 𝑞 = 2 it becomes {𝐹, 𝐺 }, adding a 100𝑚𝑠 RTT; lowering 𝑟 likewise pushes 𝐺’s closest quorum away. Write latency moves the other way, floored at 300𝑚𝑠 by the SMR majority requirement. The key point is that the 𝑞 = 1 column, local reads, already spans the entire read-write latency tradeoff and is the only configuration reaching zero read latency; larger 𝑞 only adds redundancy. So where network variance is negligible and the considerations of Section 3.5 do not apply, local reads suffices. This is the first fundamental tradeoff of quorum systems, generalizing to arbitrary 𝑄 𝑅 : shrinking 𝑅 towards the leader while keeping fixed quorum sizes trades write latency for read latency and vice versa. A read-heavy workload wants one end and a write-heavy one the other.

Figure 11: Worst case read latency heatmaps at leader 𝐴 and at 𝐺, comparing eager and delayed stamping (delayed stamping only supported for local reads). 3.6.3 Worst Case Read Latency Gap. Finally, Figure 11 shows worst case read latency, under maximal write contention, for reads at the leader 𝐴 and at 𝐺, placing delayed stamping’s 𝑞 = 1 column beside the full eager heatmaps. Delayed stamping improves the worst case almost everywhere, and dramatically near 6

procedure read(): 𝑐𝑛𝑡𝑟 := 𝑐𝑛𝑡𝑟 + 1 /* Local operation identifier */ 3 send ⟨𝑅𝐸𝐴𝐷, 𝑐𝑛𝑡𝑟 ⟩ to all processes 4 𝑟𝑒𝑝𝑙 𝑦𝑀𝑎𝑝 := ∅ /* map index to set of SNP/SP/NA */ 5 𝑟𝑒𝑝𝑙𝑖𝑒𝑑𝑃𝑟𝑜𝑐𝑠 := ∅ 6 upon receiving ⟨𝑅_𝐴𝐶𝐾, 𝑐𝑛𝑡𝑟, 𝑀 ⟩ from 𝑞: 7 𝑟𝑒𝑝𝑙𝑖𝑒𝑑𝑃𝑟𝑜𝑐𝑠 := 𝑟𝑒𝑝𝑙𝑖𝑒𝑑𝑃𝑟𝑜𝑐𝑠 ∪ {𝑞 } 8 foreach 𝑖𝑛𝑑𝑒𝑥 in 𝑀 .keys do 9 𝑟𝑒𝑝𝑙 𝑦𝑀𝑎𝑝 [𝑖𝑛𝑑𝑒𝑥 ] = 𝑟𝑒𝑝𝑙 𝑦𝑀𝑎𝑝 [𝑖𝑛𝑑𝑒𝑥 ] ∪ 𝑀 [𝑖𝑛𝑑𝑒𝑥 ] 10 wait for ∃𝑄 ∈ 𝑄 𝑅 , ∀𝑤 ∈ 𝑄, 𝑤 ∈ 𝑟𝑒𝑝𝑙𝑖𝑒𝑑𝑃𝑟𝑜𝑐𝑠 1

2

/* Stamp with max index with an SP reply and no SNPs 11

12 13 14 15

17

21

*/

if prepare for 𝑖 not received then 𝐼𝑛𝑑𝑒𝑥𝑀𝑎𝑝 [𝑖 ] := NA */

else if current_time() < 𝑠𝑡𝑜𝑝_𝑒𝑣𝑒𝑛𝑡 [𝑖 ] then 𝐼𝑛𝑑𝑒𝑥𝑀𝑎𝑝 [𝑖 ] := SNP /* stop event for i passed

20

*/

𝐼𝑛𝑑𝑒𝑥𝑀𝑎𝑝 := ∅ foreach i in 0..vidx do

/* stop event for i not passed 19

With larger read quorums, no single quorum member can decide the stamp alone. Each member 𝑤 instead replies with a per-index status map: SP (the stop event for that index has elapsed), SNP (a prepare was received but the stop event has not elapsed), or NA (no prepare was received). 𝑝 aggregates these maps and stamps with the highest index that has at least one SP and no SNP (Algorithm 1). The reasoning is that an SP means that the member has entered its read blockage interval for that index and cannot be certain whether the write finished, so the read must conservatively observe it. A single SNP, on the other hand, proves the write has not finished, since every stop event elapses before the promise time, so 𝑝 may safely skip the index. Figure 12 shows an example execution in which 𝑝 contacts {𝐴, 𝐵, 𝐶} and stamps with index 3. A natural concern is that reply size grows with the number of writes, since each member returns a per-index map. However, in practice only indexes between the latest committed and the latest received prepare are uncertain; anything earlier is already committed and must be observed. Therefore, members include only this range, bounding the reply map size by the number of in-progress writes.

upon receiving ⟨𝑅𝐸𝐴𝐷, 𝑐 ⟩ from 𝑝:

/* Prepare not received (no stop event) 18

*/

𝑠𝑡𝑎𝑚𝑝𝐼𝑑𝑥 := max{𝑖 | 𝑖 ∈ 𝑟𝑒𝑝𝑙 𝑦𝑀𝑎𝑝.𝑘𝑒𝑦𝑠 ( ) ∧ 𝑆𝑃 ∈ 𝑟𝑒𝑝𝑙 𝑦𝑀𝑎𝑝 [𝑖 ] ∧ 𝑆𝑁 𝑃 ∉ 𝑟𝑒𝑝𝑙 𝑦𝑀𝑎𝑝 [𝑖 ] } wait for 𝑠𝑡𝑎𝑚𝑝𝐼𝑑𝑥 is committed wait for 𝑔𝑜_𝑒𝑣𝑒𝑛𝑡 [𝑠𝑡𝑎𝑚𝑝𝐼𝑑𝑥 ] < current_time() return 𝑠𝑡𝑎𝑡𝑒𝑀𝑎𝑐ℎ𝑖𝑛𝑒.𝑟𝑒𝑎𝑑 (𝑠𝑡𝑎𝑚𝑝𝐼𝑑𝑥 ) /* Compute per-index reply map with SP/SNP/NA

16

Figure 12: Example of Pairwise Quorums stamping mechanism with process 𝑝 aggregating stop event information from quorum {𝐴, 𝐵, 𝐶} and stamping with index 3.

*/

else 𝐼𝑛𝑑𝑒𝑥𝑀𝑎𝑝 [𝑖 ] := SP send ⟨𝑅_𝐴𝐶𝐾, 𝑐, 𝐼𝑛𝑑𝑒𝑥𝑀𝑎𝑝 ⟩ to 𝑝

Algorithm 1: Read pseudocode for Pairwise Quorums assuming no message loss, all processes are non-faulty, a fixed leader ℓ, and a known 𝑄 𝑅

the leader: 𝐴 sees zero blockage under delayed against the full write latency under eager, while the distant 𝐺 sees a smaller gain. The gain is confined to local reads due to the gap in delayed stamping. A deployment that wants write tolerance to network variance needs a quorum-based (𝑞 > 1) configuration, which forces it onto eager stamping and its full read blockage. Closing this gap, extending delayed stamping to arbitrary quorums 𝑄 𝑅 , is what our algorithm Pairwise Quorums (Section 4) solves.

4

4.2

We sketch correctness through the four real-time ordering cases of linearizability. Write before read. If write 𝑜 𝑤 completes before read 𝑜𝑟 starts, 𝑜𝑟 must observe 𝑜 𝑤 . Say 𝑜 𝑤 committed at index 𝑖; then 𝑜𝑟 must stamp with at least 𝑖. Suppose 𝑜𝑟 stamped using quorum 𝑄. Since 𝑜 𝑤 completed, every process’s stop event for 𝑖 has passed, and by the intersection requirement at least one 𝑤 ∈ 𝑄 received a prepare for 𝑖. So 𝑝’s aggregate map holds at least one SP for 𝑖 and no SNP, thus 𝑝 stamps with at least 𝑖. Write before write. Unchanged from Pairwise [45], since we keep its write procedure. Read before write. If 𝑜𝑟 completes before 𝑜 𝑤 starts, 𝑜 𝑤 ’s readmodify-write must observe at least the state read by 𝑜𝑟 . If 𝑜𝑟 stamped with 𝑖, then 𝑖 committed at 𝑝 and so completed, and by the write-before-write case 𝑜 𝑤 observes 𝑖. Read before read. If 𝑜𝑟 1 completes before 𝑜𝑟 2 starts, 𝑜𝑟 2 must observe at least the state read by 𝑜𝑟 1 . If 𝑜𝑟 1 stamped with 𝑖, then 𝑖 committed and so completed, and by the write-before-read case 𝑜𝑟 2 stamps with at least 𝑖.

Pairwise-Quorums Algorithm

We now present Pairwise Quorums, which closes the delayed stamping gap shown in Figure 11 by extending delayed stamping to arbitrary quorum configurations. Its write procedure is identical to Pairwise’s [45] (Section 2.6) except generalized to quorums (i.e 3.0.1), so we focus on the read procedure, building on the general read procedure of Section 3.0.2. To focus on the stamping mechanism, we assume every process knows a static 𝑄𝑅 .

4.1

Correctness

Read Procedure

In standard Pairwise every read quorum is a single local reader. Following the general read procedure, 𝑝 contacts its closest local reader, which returns the highest index 𝑖 for which it has received a prepare and its stop event has elapsed. With a single-process quorum this index is already the stamp, so no aggregation is needed; 𝑝 blocks until 𝑖 commits and its own go event elapses, then returns.

4.3

Analysis

We now fill the gap from Section 3 by extending the delayed stamping worst case read latency, eq (5), from 𝐿 to arbitrary 𝑄 𝑅 . 7

4.3.1

Worst Case Read Latency.   𝑊 𝐶 (Δ𝑟 (𝑁 , 𝑝)) = min max 𝑄 ∈𝑄 𝑅

max {𝛿𝑝𝑞 + 𝛿 ℓ𝑝 + min(𝛿 ℓ𝑞 , Δ𝑤 (𝑁 ) − 𝛿 ℓ𝑞 )},  𝛿𝑝𝑄𝑝

𝑞 ∈𝐴(𝑄,𝑝 )

where 𝐴(𝑄, 𝑝) = {𝑞 1 ∈𝑄 | ∀𝑞 2 ∈ 𝑄, ¬(𝛿 ℓ𝑞2 < max(Δ𝑤 (𝑁 ) − 𝛿 ℓ𝑞1 , 𝛿 ℓ𝑞1 ) − 𝛿𝑝𝑞1 + 𝛿𝑝𝑞2 < Δ𝑤 (𝑁 ) − 𝛿 ℓ𝑞2 )} Figure 14: Worst case read latency compared analytically between Pairwise Quorums and eager stamping for reads at leader 𝐴 in the same Base Network, showing generalization of read blockage time improvement in delayed stamping.

(6) The outer min picks the closest quorum 𝑄, and within it the latency is the worse of (a) the quorum contact time 𝛿𝑝𝑄𝑝 , identical to case (a) of eq (3), and (b) the read blockage time, the max over 𝑞 ∈ 𝐴(𝑄, 𝑝). For case (b), we find the latest time a concurrent write 𝑖 can start while the read still stamps with 𝑖. The protocol needs at least one 𝑞 ∈ 𝑄 to reply SP, so 𝑞 must have received the prepare for 𝑖 and its stop event elapsed. Thus the latest time the write can start is when 𝑝’s request reaches 𝑞 at the exact first moment 𝑞 can reply SP, namely 𝑡 (𝑟𝑖 ) + 𝛿𝑝𝑞 = max(𝑡 (𝑤𝑖 ) + 𝛿 ℓ𝑞 , 𝑡 (𝑤𝑖 ) + Δ𝑤 (𝑁 ) −𝛿 ℓ𝑞 ), the later of the prepare arriving and the stop event elapsing. We call this aligning to 𝑞; the prepare term dominates only for processes farther than the promise time accounts for, those in large quorums the leader need not intersect. The read returns when the commit reaches 𝑝, at 𝑡 (𝑤𝑖 ) + Δ𝑤 (𝑁 ) + 𝛿 ℓ𝑝 . Subtracting 𝑡 (𝑟𝑖 ) via the alignment equality and applying the identity Δ𝑤 − max(Δ𝑤 − 𝛿 ℓ𝑞 , 𝛿 ℓ𝑞 ) = min(Δ𝑤 − 𝛿 ℓ𝑞 , 𝛿 ℓ𝑞 ) gives 𝛿 ℓ𝑝 + 𝛿𝑝𝑞 + min(𝛿 ℓ𝑞 , Δ𝑤 (𝑁 ) − 𝛿 ℓ𝑞 ), the inner expression of eq (6).

5

Ditto Algorithm for Reconfiguration

We now present Ditto, our mechanism for reconfiguring 𝑄 𝑅 at runtime. Ditto reconfigures at runtime and builds on Pairwise Quorums thus retaining delayed stamping’s reduced read blockage at every configuration. Under our model, Ditto subsumes every existing algorithm: against each, it is either better, using delayed stamping where the other uses eager or invalidation, or reconfigures to match it on the tradeoff axes where no single configuration dominates. Ditto stores 𝑄 𝑅 in a blackbox linearizable object, the configuration layer, as an explicit set of sets. Every write and every read first reads this layer to learn the current 𝑄 𝑅 . A write does so to know which processes it must intersect, and a read, to know which quorums it may contact. We require two things of the configuration layer. First, it must make progress under up to 𝑓 faults in the main layer, so that a faulty quorum can always be reconfigured out of 𝑄 𝑅 to avoid stalling writes. Second, non-faulty processes must read it with zero latency, so that consulting it adds no overhead to a mainlayer operation. We satisfy both by running the configuration layer as a second MultiPaxos instance on the same processes and leader, using Pairwise with every process a local reader. This gives zero-latency configuration reads everywhere, at the price of configuration writes contacting every process, following from the read-write tradeoff our analysis described earlier. Because the configuration layer runs Pairwise, it already handles all faulttolerance through leases and inherits a fault tolerance of 𝑓 , so the main layer itself uses no leases. If a read quorum becomes faulty on the main layer, a write to the configuration layer is performed to reconfigure out the faulty quorum, and all lease and fault tolerance mechanisms are handled there. Reconfiguration can violate linearizability if handled naively. Consider {𝐴, 𝐵, 𝐶, 𝐷, 𝐸} with 𝑄 𝑅 = {{𝐵}} and writes committed through index 𝑖 = 10. Suppose the leader satisfied intersection using {𝐴, 𝐵, 𝐶} and its prepares never reached 𝐷 or 𝐸. Reconfiguring to 𝑄 𝑅 = {{𝐷 }} now lets a read contact 𝐷, which stamps with 𝑖 = 0 and misses all 10 committed writes. The new quorum was never intersected by the earlier writes, so it lacks their indexes. Correctness requires that every new quorum serve reads only once it is at least as up-to-date as some old quorum, that is, it would stamp with an index at least as large. Intuitively, the old quorums must “pass the torch” to the new ones.

Figure 13: Aligning to 𝑞 1 allows the write to start the latest, however, 𝑞 2 would end up returning SNP making this the incorrect worst case.

We now address 𝐴(𝑄, 𝑝). With quorums larger than one, aligning to some 𝑞 1 may push another 𝑞 2 ∈ 𝑄 into its SNP zone, the interval between when 𝑞 2 receives the prepare for 𝑖 and when its stop event elapses, during which 𝑞 2 replies SNP and prevents stamping with 𝑖 (Figure 13). 𝐴(𝑄, 𝑝) is therefore the set of alignable 𝑞 1 ∈ 𝑄: those that when aligned to leave every other 𝑞 2 outside its SNP zone. Writing that condition for 𝑞 2 , ¬(𝑡 (𝑤𝑖 ) + 𝛿 ℓ𝑞2 < 𝑡 (𝑟𝑖 ) + 𝛿𝑝𝑞2 < 𝑡 (𝑤𝑖 ) + Δ𝑤 (𝑁 ) − 𝛿 ℓ𝑞2 ), and substituting the alignment equality for 𝑡 (𝑟𝑖 ) gives the set builder of eq (6). This makes the worst case expression tight by excluding seemingly valid but actually impossible constructions. Figure 14 plots worst case read latency for Pairwise Quorums against eager stamping at leader 𝐴 in the Base Network. The delayed stamping improvement we observed initially only for local reads generalizes across every quorum-based configuration, so deployments can now tune both tradeoff axes without giving up reduced read blockage time. 8

Testbeds. We use two networks, both realized on separate virtual machines with per-link latencies enforced by Linux traffic control. The first is the emulated Base Network of Figure 8: seven processes on a fully connected line with symmetric 50ms links, together with its Fail-Slow variant in which processes 𝐵 and 𝐶 are spiked to 3000ms. The second is an emulated geo-distributed network of five processes whose pairwise latencies are set to measured AWS p50 inter-region round-trip times across ca-central-1 (the leader), us-east-1, us-west-1, eu-north-1, and eu-central-1. Methodology. Latency is measured from the moment a process receives a request to when it is about to return it. Each experiment dispatches a set number of operations at a set dispatch interval, run concurrently (exact values stated per experiment). Because the JVM introduces latency through just-in-time compilation and garbage collection that the analytical model does not capture, we warm up the JVM before measuring and discard outliers. We also set the Pairwise 𝛼 promise time to 10𝑚𝑠 above the RTT to the furthest process, penalizing writes by 10𝑚𝑠 but keeping reads optimal – a suggested buffer for real deployments.

We enforce this with a lower bound index (or “wall” index). On each read, 𝑝 compares the configuration layer’s current index against the one it last saw; if they differ, a reconfiguration has occurred, so 𝑝 fetches the latest prepare index 𝑖𝑙𝑏 from the leader and stamps with at least 𝑖𝑙𝑏 for the current and all future reads regardless of what its read quorum returns. Since 𝑖𝑙𝑏 is at least what any former quorum would have stamped with, the new quorum’s possibly stale indexes no longer threaten correctness.

6.2

Validating the Analytical Model

Figure 15: All procedures of the Ditto reconfiguration algorithm visualized.

The read, write, and reconfiguration procedures are illustrated in Figure 15. Ditto’s overhead is modest: a zero-latency configuration read on every operation, and, only while a reconfiguration is in flight, a full config-layer write plus a short window where reads pay an extra round trip to the leader for 𝑖𝑙𝑏 and see elevated read blockage. These costs buy the ability to move 𝑄 𝑅 across the two tradeoff axes at runtime, keeping a system at the optimal configuration as its workload and network change.

6

Figure 16: Measured write and best case read latency (reads at 𝐺) over the (𝑟, 𝑞) space on the Base Network, reproducing Figure 9. Figure 16 shows measured write and best case read latency across the (𝑟, 𝑞) space on the Base Network, with reads executing at process 𝐺. We realize each configuration with EdgePQR, which supports the full quorum space under eager stamping; since write latency and best case read latency are identical across stamping mechanisms (Section 3), this validates those expressions for every configuration. For each cell, we execute 5000 operations at a 2𝑚𝑠 dispatch interval and report a trimmed mean over the interquartile range, discarding the top and bottom quartiles to remove compilation and collection outliers. The write heatmap runs an all-writes workload, and the read heatmap an all-reads workload with reads at 𝐺 and no concurrent writes. The measured heatmaps reproduce the analytical ones of Figure 9, deviating by at most a few milliseconds per cell, attributable to JVM scheduling, measurement noise, and the 10𝑚𝑠 𝛼 buffer. Figure 17 measures how write and best case read latency change between the Base Network and the Fail-Slow Network, again reading at 𝐺. We rerun the previous experiment on both networks and report the per-cell difference after interquartile trimming. We raise the dispatch interval to 7.5𝑚𝑠 here because at 2𝑚𝑠 the Fail-Slow Network cannot drain operations fast enough, and network congestion rather than the fail-slow spike becomes

Evaluation

Our evaluation has two goals. First, we validate the analytical expressions of Sections 3 and 4 against a real implementation. Second, we demonstrate the two practical benefits the analysis predicts: that Pairwise Quorums removes the forced tradeoff between stamping mechanism and tolerance to network variance, and that Ditto reconfigures to remain optimal as conditions change. We first reproduce the analytical heatmaps experimentally, then demonstrate both benefits on an emulated geo-distributed network.

6.1

Experimental Setup

Implementation. Our prototype runs on the JVM and realizes the full framework of Section 3: every existing algorithm, as well as Pairwise Quorums and Ditto, is obtained by selecting a stamping mechanism and a read-write quorum system, so all baselines and our own algorithms execute on identical code paths and differ only in configuration. 9

Figure 17: Measured change in write and best case read latency (reads at 𝐺) over the (𝑟, 𝑞) space from the Base to the Fail-Slow Network, reproducing Figure 10.

Figure 19: Per-operation latency over time on the AWS p50 network with one fail-slow reader. Pairwise Quorums keeps reads and writes fast, Pairwise pays the spike on writes, EdgePQR pays eager blockage on reads.

the dominant slowdown. The measurements again match the analytical heatmaps of Figure 10 to within a few milliseconds per cell.

read latency through maximal write contention. We run 5000 operations at a 5𝑚𝑠 interval and make the second-furthest process from the leader (by p50 latency) fail-slow by adding 1200𝑚𝑠 to its incoming messages. Figure 19 plots per-operation latency over time, side by side for reads at the process closest to the leader and writes at the leader. The results expose the tradeoff. Pairwise reads quickly, but since every write must reach all local readers, every write incurs the fail-slow spike. EdgePQR’s larger quorums let writes route around the slow process, yet its eager stamping makes every contended read pay the full worst case blockage. Pairwise Quorums alone escapes both: its size-two quorums absorb the spike on writes while its delayed stamping keeps reads fast, reaching the optimal corner that neither alternative can.

Figure 18: Measured worst case read latency (reads at leader 𝐴) over the (𝑟, 𝑞) space on the Base Network: Pairwise Quorums (delayed, left) vs. EdgePQR (eager, right), reproducing Figure 14 and confirming delayed stamping’s advantage.

6.4

Finally, Figure 18 measures worst case read latency across the (𝑟, 𝑞) space on the Base Network, reading at leader 𝐴. The left heatmap uses Pairwise Quorums and the right EdgePQR, both over 5000 operations at a 5𝑚𝑠 interval. To drive the worst case, we alternate reads and writes at the leader, so every read overlaps a freshly initiated, still-in-progress write. The measurements again reproduce Figure 14 to within a few milliseconds per cell. Together, these three experimental heatmaps validate our theoretical analyses and derived insights from sections 3.6 and 4.3, confirming the two core tradeoff axes in the configuration space, and the advantage of delayed stamping.

6.3

The Value of Reconfiguration

The previous experiment assumes the right configuration is known in advance. When conditions are unknown or change over time, no static configuration suffices, and Ditto reconfigures to track the optimum. In both experiments below, Ditto is hardcoded to reconfigure at the right time, since policy design is left to future work (Section 8).

Removing the Stamping-Variance Tradeoff

This experiment shows that Pairwise Quorums escapes the tradeoff between read blockage time and write tolerance to network variance that the existing alternatives are forced to make. On the emulated 5-node AWS p50 network we run three executions, one each for Pairwise, EdgePQR, and Pairwise Quorums (PwQ). We configure EdgePQR and PwQ to every size-two quorum (𝑞 = 2, 𝑟 = 5), and Pairwise to every process a local reader. In each execution, all processes but the leader run 100% reads, while the leader alternates 50% reads and 50% writes to drive worst case

Figure 20: Operation latencies as the workload shifts from reads to writes on the AWS p50 network. Ditto reconfigures from the read-optimal to the write-optimal configuration, matching the best static choice in each phase. 10

7

We first exercise reconfiguration along the read-write latency axis. On the emulated AWS p50 network we dispatch 3000 reads at the process second-furthest from the leader, then 3000 writes at the leader, each at a 5𝑚𝑠 interval. We compare Ditto against Pairwise and Leader Reads, the read-optimal and write-optimal extremes. All three run delayed stamping, so any difference is due to quorum configuration alone. Pairwise and Leader Reads stay fixed, while Ditto starts read-optimal and reconfigures to Leader Reads, matching the better extreme in each phase. Figure 20 plots operation latency over time; a dotted line marks the switch from all reads (the first 3000 operations) to all writes, and a dashed line marks where Ditto reconfigures. Apart from a brief spike as the new configuration installs – an expected cost – Ditto stays optimal throughout.

Related Work

State machine replication. Our work builds on leader-based SMR, including Paxos [24, 25] and its multi-decree form MultiPaxos [49], Viewstamped Replication [38], and Raft [40]. Fundamental limits on these protocols come from impossibility results such as FLP [12] and CAP [14], and, for read-only transactions, SNOW [30]. Leaderless and multi-leader protocols such as Mencius [32], EPaxos [33, 47], and SwiftPaxos [41] rotate or remove the leader to improve wide-area latency and load balance, while Clock-RSM [11] and Nezha [13] order commands using synchronized clocks. We assume a stable leader and do not address these protocols. Linearizable reads. Section 2 places the leader-based read algorithms [4, 6–8, 16, 34, 45] in our framework. Raft offers analogous leader reads, either confirming leadership with a round of heartbeats (ReadIndex) or relying on a leader lease [39]. Several systems outside leader-based SMR also serve linearizable reads away from the leader. Megastore [3] serves local reads at any replica whose coordinator vouches that it is up to date, and a write must invalidate the coordinators of replicas that miss it. Hermes [23] lets every replica read locally by broadcasting invalidations on each write, and relies on an external membership service for fault tolerance. Chain replication [50] serves reads at the tail, and CRAQ [44] lets any node serve reads, querying the tail only for objects with an uncommitted version. Gryff [5] pairs consensus for read-modify-writes with shared-register quorum reads. In our terms, Megastore and Hermes resemble invalidation over local read quorums, and CRAQ trades read blockage for a round trip to the tail. Because these systems order writes per object or depend on external coordination, they fall outside our model and we do not evaluate them. Bodega [21] orders writes in a single log but serves local reads at per-key responders protected by all-to-all roster leases, and a read waits only on in-flight writes to the same key. This per-key conflict detection relies on key-value semantics that our model, a single replicated object updated by read-modify-writes, does not capture, so Bodega also falls outside it.

Figure 21: Per-operation latency as reads give way to concurrent reads and writes and a process turns fail-slow, on the AWS p50 network. Ditto reconfigures from readoptimal to variance-tolerant, matching the best static choice in each phase. We next exercise reconfiguration along the network-variance axis. On the emulated AWS p50 network we dispatch 3000 reads at the process second-furthest from the leader (eu-central-1) at a 5𝑚𝑠 interval, then spike the second-closest process (us-west-1) to fail-slow by adding 600𝑚𝑠 to its incoming messages. After the spike, a further 3000 reads at the second-furthest process run concurrently with 3000 writes at the leader, both at a 5𝑚𝑠 interval. Figure 21 plots read latency (dotted lines) and write latency (solid lines) over time, with a vertical dotted line marking the spike and the end of the first 3000 reads. We compare Ditto against two static Pairwise Quorums configurations: one with the four processes closest to the leader as local readers, and one with size-two quorums covering every process (𝑞 = 2, 𝑟 = 5). The first is read-optimal, serving reads locally; the second tolerates any single fail-slow process, shielding writes from the variance at a modest cost to reads. Each static choice is stuck with its tradeoff, but Ditto reconfigures past it. Before the spike, both Ditto and local reads serve reads at 0𝑚𝑠 while the quorum configuration sits at 50𝑚𝑠; after the spike and reconfiguration settle, Ditto and the quorum configuration share a worst case read latency of 222𝑚𝑠 and a write latency of 222𝑚𝑠, while local reads holds marginally faster reads (188𝑚𝑠) but pays heavily on writes (640𝑚𝑠). Ditto again absorbs a few seconds of reconfiguration cost, but maintains optimality. One might ask why not simply reconfigure the fail-slow process out rather than going to quorums. That is only possible after the fact and demands a fresh reconfiguration every time a process slows, whereas a quorum configuration tolerates any single fail-slow process with no further reconfiguration at only a minor cost to reads.

Quorum systems. Quorum systems have a long history in replicated data [9, 35], including dynamic quorum adjustment [18]. Flexible Paxos [20] showed that consensus only needs leaderelection quorums to intersect replication quorums, which WPaxos [2] and DPaxos [36] exploit to place quorums near users; DPaxos can also move its leader-election zones at runtime. Quoracle [52] and Pando [48] select a read-write quorum system before deployment by optimizing load, latency, or cost. Our analysis plays a similar role for the latency and variance tolerance of linearizable reads, including the effect of the stamping mechanism, and Ditto acts on it at runtime. An offline optimizer such as Quoracle could serve as one of Ditto’s reconfiguration policies. Reconfiguration. Reconfiguration in consensus has been studied extensively, including Raft’s joint consensus [40], Vertical Paxos [26], SMART [29], and general methods for reconfiguring state machines [27]. RAMBO [31] and DynaStore [1] reconfigure the replica sets and quorums of atomic read/write storage, with RAMBO using the old and new configurations together during a transition. These works change the membership or quorums of the replication protocol itself, whereas Ditto reconfigures only the read quorum system on top of an unchanged SMR instance. 11

Fail-slow faults and synchronized clocks. Fail-slow and gray failures are common in production systems [17, 22]. Copilot replication [37] tolerates one slow replica by having two distinguished replicas, a pilot and a copilot, both order every command, so either can make progress when the other slows. Ditto instead tolerates slow processes by choosing read quorums that let writes route around them. Synchronized clocks offer another path to fast reads. Spanner [10] waits out clock uncertainty at commit so that sufficiently up-to-date replicas can serve consistent reads, and CockroachDB’s global tables [51] schedule writes at future timestamps so that any replica can serve strongly consistent reads locally, an idea close to the promise time of delayed stamping. Both rely on bounded clock skew, whereas delayed stamping needs only bounded drift; exploiting bounded skew, as BHT [4] does, is future work.

8

[3] Jason Baker, Chris Bond, James C. Corbett, J. J. Furman, Andrey Khorlin, James Larson, Jean-Michel Léon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing Scalable, Highly Available Storage for Interactive Services. In Proceedings of the 5th Biennial Conference on Innovative Data Systems Research (CIDR). 223–234. [4] Changyu Bi, Vassos Hadzilacos, and Sam Toueg. 2022. Parameterized Algorithm for Replicated Objects with Local Reads. arXiv preprint arXiv:2204.01228 (2022). [5] Matthew Burke, Audrey Cheng, and Wyatt Lloyd. 2020. Gryff: Unifying Consensus and Shared Registers. In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI). 591–617. [6] Tushar D. Chandra, Robert Griesemer, and Joshua Redstone. 2007. Paxos Made Live: An Engineering Perspective. In Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC). 398–407. [7] Tushar D. Chandra, Vassos Hadzilacos, and Sam Toueg. 2016. An Algorithm for Replicated Objects with Efficient Reads. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC). 325–334. [8] Aleksey Charapko, Ailidani Ailijiang, and Murat Demirbas. 2019. Linearizable Quorum Reads in Paxos. In Proceedings of the 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage). [9] Shun Yan Cheung, Mostafa H. Ammar, and Mustaque Ahamad. 1992. The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data. IEEE Transactions on Knowledge and Data Engineering 4, 6 (1992), 582–592. [10] 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 Transactions on Computer Systems 31, 3 (2013), 1–22. [11] Jiaqing Du, Daniele Sciascia, Sameh Elnikety, Willy Zwaenepoel, and Fernando Pedone. 2014. Clock-RSM: Low-Latency Inter-Datacenter State Machine Replication Using Loosely Synchronized Physical Clocks. In Proceedings of the 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 343–354. [12] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32, 2 (1985), 374–382. [13] Jinkun Geng, Anirudh Sivaraman, Balaji Prabhakar, and Mendel Rosenblum. 2022. Nezha: Deployable and High-Performance Consensus Using Synchronized Clocks. Proceedings of the VLDB Endowment 16, 4 (2022), 629–642. [14] Seth Gilbert and Nancy Lynch. 2002. Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News 33, 2 (2002), 51–59. [15] Cary G. Gray and David R. Cheriton. 1989. Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency. In Proceedings of the 12th ACM Symposium on Operating Systems Principles (SOSP). 202–210. [16] Joshua Guarnieri and Aleksey Charapko. 2023. Linearizable Low-Latency Reads at the Edge. In Proceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC). 77–83. [17] Haryadi S. Gunawi, Riza O. Suminto, Russell Sears, Casey Golliher, Swaminathan Sundararaman, Xing Lin, Tim Emami, Weiguang Sheng, Nematollah Bidokhti, Caitie McCaffrey, Gary Grider, Parks M. Fields, Kevin Harms, Robert B. Ross, Andree Jacobson, Robert Ricci, Kirk Webb, Peter Alvaro, H. Birali Runesha, Mingzhe Hao, and Huaicheng Li. 2018. Fail-Slow at Scale: Evidence of Hardware Performance Faults in Large Production Systems. In Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST). 1–14. [18] Maurice Herlihy. 1987. Dynamic Quorum Adjustment for Partitioned Data. ACM Transactions on Database Systems 12, 2 (1987), 170–194. [19] Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems 12, 3 (1990), 463–492. [20] Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. 2016. Flexible Paxos: Quorum Intersection Revisited. In Proceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs, Vol. 70). 25:1– 25:14. [21] Guanzhou Hu, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2026. Bodega: Localized Linearizable Reads at Anywhere Anytime via Roster Leases. In Proceedings of the 20th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 1243–1281. [22] Peng Huang, Chuanxiong Guo, Lidong Zhou, Jacob R. Lorch, Yingnong Dang, Murali Chintalapati, and Randolph Yao. 2017. Gray Failure: The Achilles’ Heel of Cloud-Scale Systems. In Proceedings of the 16th Workshop on Hot Topics in Operating Systems (HotOS). 150–155. [23] Antonios Katsarakis, Vasilis Gavrielatos, M. R. Siavash Katebzadeh, Arpit Joshi, Aleksandar Dragojević, Boris Grot, and Vijay Nagarajan. 2020. Hermes: A Fast, Fault-Tolerant and Linearizable Replication Protocol. In Proceedings of the 25th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 201–217. [24] Leslie Lamport. 1998. The Part-Time Parliament. ACM Transactions on Computer Systems 16, 2 (1998), 133–169. [25] Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News 32, 4 (2001), 51–58.

Conclusion

We presented a unified framework for reasoning about linearizable reads algorithms, decomposing each into a choice of readwrite quorum system and a stamping mechanism and placing all existing algorithms in a single space. A mathematical analysis of write and read latency over this space showed that no configuration dominates: the quorum system sets two tradeoffs, read versus write latency and read versus write tolerance to network variance. Meanwhile the stamping mechanism has a single best choice, delayed stamping, that prior work could apply only to local reads. We closed that gap with Pairwise Quorums, which extends delayed stamping to arbitrary quorum configurations, and built Ditto on top of it to reconfigure 𝑄 𝑅 at runtime. Under our model, Ditto subsumes every existing algorithm, so a deployment now needs to consider only Ditto and can use our analysis to guide its reconfiguration. Several directions remain open. First, GPS clocks [10] make bounded clock skew, rather than only bounded drift, a practical assumption. Bounded skew keeps clocks synchronized within a fixed bound regardless of distance, which under delayed stamping could give near-zero blockage at every process, not just those near the leader, a property BHT [4] already claims. Extending our analysis to a GPS-clock stamping mechanism is a natural next step. Second, our analysis can guide reconfiguration but says nothing about when to reconfigure, or how to balance conservative against aggressive strategies. Third, Ditto assumes reconfigurations are infrequent and does not optimize their cost; edge deployments, with frequent failures and a volatile network, may demand far faster reconfiguration. A natural next step is also read throughput, which our analysis does not address. It depends on the read contact strategy, on message sizes that in Pairwise Quorums grow with in-progress writes, and on queueing effects, so it calls for a different treatment than latency. The contact strategy alone carries a further tradeoff: the full broadcast we assume always finds a process’s closest quorum under variance but floods the network on every read, whereas the thrifty optimization [47] contacts only the knownclosest quorum, lowering load at the cost of slower adaptation to variance. Characterizing read throughput across the space, and tuning along it, is a promising direction.

References [1] Marcos K. Aguilera, Idit Keidar, Dahlia Malkhi, and Alexander Shraer. 2011. Dynamic Atomic Storage Without Consensus. Journal of the ACM 58, 2 (2011). [2] Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, and Tevfik Kosar. 2020. WPaxos: Wide Area Network Flexible Consensus. IEEE Transactions on Parallel and Distributed Systems 31, 1 (2020), 211–223. 12

[26] Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. 2009. Vertical Paxos and Primary-Backup Replication. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC). 312–313. [27] Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. 2010. Reconfiguring a State Machine. ACM SIGACT News 41, 1 (2010), 63–73. [28] Barbara Liskov. 1991. Practical Uses of Synchronized Clocks in Distributed Systems. In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing (PODC). 1–9. [29] Jacob R. Lorch, Atul Adya, William J. Bolosky, Ronnie Chaiken, John R. Douceur, and Jon Howell. 2006. The SMART Way to Migrate Replicated Stateful Services. In Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems (EuroSys). 103–115. [30] Haonan Lu, Christopher Hodsdon, Khiem Ngo, Shuai Mu, and Wyatt Lloyd. 2016. The SNOW Theorem and Latency-Optimal Read-Only Transactions. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 135–150. [31] Nancy Lynch and Alex A. Shvartsman. 2002. RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks. In Proceedings of the International Symposium on Distributed Computing (DISC) (LNCS, Vol. 2508). 173–190. [32] Yanhua Mao, Flavio P. Junqueira, and Keith Marzullo. 2008. Mencius: Building Efficient Replicated State Machines for WANs. In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 369–384. [33] Iulian Moraru, David G. Andersen, and Michael Kaminsky. 2013. There Is More Consensus in Egalitarian Parliaments. In Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP). 358–372. [34] Iulian Moraru, David G. Andersen, and Michael Kaminsky. 2014. Paxos Quorum Leases: Fast Reads Without Sacrificing Writes. In Proceedings of the ACM Symposium on Cloud Computing (SoCC). 1–13. [35] Moni Naor and Avishai Wool. 1998. The Load, Capacity, and Availability of Quorum Systems. SIAM J. Comput. 27, 2 (1998), 423–447. [36] Faisal Nawab, Divyakant Agrawal, and Amr El Abbadi. 2018. DPaxos: Managing Data Closer to Users for Low-Latency and Mobile Applications. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD). 1221–1236. [37] Khiem Ngo, Siddhartha Sen, and Wyatt Lloyd. 2020. Tolerating Slowdowns in Replicated State Machines Using Copilots. In Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 583–598. [38] Brian M. Oki and Barbara H. Liskov. 1988. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (PODC). 8–17. [39] Diego Ongaro. 2014. Consensus: Bridging Theory and Practice. Ph. D. Dissertation. Stanford University.

[40] Diego Ongaro and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Annual Technical Conference (USENIX ATC). 305–319. [41] Fedor Ryabinin, Alexey Gotsman, and Pierre Sutra. 2024. SwiftPaxos: Fast Geo-Replicated State Machines. In Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI). 345–369. [42] Fred B. Schneider. 1990. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys 22, 4 (1990), 299–319. [43] Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, 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). 1493–1509. [44] Jeff Terrace and Michael J. Freedman. 2009. Object Storage on CRAQ: HighThroughput Chain Replication for Read-Mostly Workloads. In Proceedings of the 2009 USENIX Annual Technical Conference (USENIX ATC). [45] Myles Thiessen, Guy Khazma, Sam Toueg, and Eyal de Lara. 2025. Asymmetric Linearizable Local Reads. Proceedings of the VLDB Endowment 18, 8 (2025), 2427–2439. [46] Myles Thiessen, Aleksey Panas, Guy Khazma, and Eyal de Lara. 2024. Towards Reconfigurable Linearizable Reads. arXiv preprint arXiv:2404.05470 (2024). [47] Sarah Tollman, Seo Jin Park, and John Ousterhout. 2021. EPaxos Revisited. In Proceedings of the 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI). 613–632. [48] Muhammed Uluyol, Anthony Huang, Ayush Goel, Mosharaf Chowdhury, and Harsha V. Madhyastha. 2020. Near-Optimal Latency Versus Cost Tradeoffs in Geo-Distributed Storage. In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI). 157–180. [49] Robbert van Renesse and Deniz Altinbuken. 2015. Paxos Made Moderately Complex. ACM Computing Surveys 47, 3 (2015), 1–36. [50] Robbert van Renesse and Fred B. Schneider. 2004. Chain Replication for Supporting High Throughput and Availability. In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI). [51] Nathan VanBenschoten, Arul Ajmani, Marcus Gartner, Andrei Matei, Aayush Shah, Irfan Sharif, Alexander Shraer, Adam Storm, Rebecca Taft, Oliver Tan, Andy Woods, and Peyton Walters. 2022. Enabling the Next Generation of Multi-Region Applications with CockroachDB. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD). 2312–2325. [52] Michael Whittaker, Aleksey Charapko, Joseph M. Hellerstein, Heidi Howard, and Ion Stoica. 2021. Read-Write Quorum Systems Made Practical. In Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC). 1–8.

13

Related documents

• Ditto: Generalized Reconfigurable Linearizable Reads#1155637
• Accelerating vector operations by utilizing reconfigurable coprocessor architectures#420803
• Trillion-Parameter MoE in a Box: Decoupling Memory Provisioning with High-Bandwidth Flash#1109618
• Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers#271792
• Cutadapt removes adapter sequences from high-throughput sequencing reads#6299