Draft Whitepaper for CEP-15: General Purpose Transactions

CEP-15: Fast General Purpose Transactions

Elliott Smith, Benedict

Zhang, Tony

Eggleston, Blake

benedict@apple.com

nudzhang@umich.edu

beggleston@apple.com

Andreas, Scottcscotta@apple.com

Abstract
Modern applications replicate and shard their state to achieve fault tolerance and scalable performance. This presents
a coordination problem that modern databases address using leader-based techniques that entail trade-offs: either ascalability bottleneck or weaker isolation. Recent advances in leaderless protocols that claim to address this coordination
problem have not yet translated into production systems. This paper outlines distinct performance compromises entailed
by existing leaderless protocols in comparison to leader-based approaches. We propose techniques to address theseshort-comings and describe a new distributed transaction protocol ACCORD, integrating these techniques. ACCORD is
the first protocol to achieve the same steady-state performance as leader-based protocols under important conditions
such as contention and failure, while delivering the benefits of leaderless approaches to scaling, transaction isolationand geo-distributed client latency. We propose that this combination of features makes ACCORD uniquely suitable for
implementing general purpose transactions in Apache Cassandra.

1

Introduction

Modern applications rely upon remote database services to ensure their state is durable and available to clients. To
provide these properties, modern databases partition their state into geo-replicated shards. This permits some tolerated
combination of failures to coincide without interrupting the service, while ensuring the database may scale to meet user
demand. However, a distributed coordination problem is introduced for transaction execution.
Real-world database systems address this by imposing restrictions on functionality or sacrificing performance.
Systems that offer transactions using Raft [34] or Multi-Paxos [21] are now common-place [4,13,14,16,29,36,42,44,47],
but most do not offer cross-shard transactions. These were first introduced by Spanner [8], but required specialised
hardware and multiple WAN round-trips. More recently, systems using commodity hardware have begun to catch up:
FaunaDB and FoundationDB offer strict-serializable isolation, but order transactions with a global leader process [14,47];
CockroachDB, YugaByte and DynamoDB avoid this bottleneck, but claim only serializable isolation [6, 40, 44]. Neithergroup therefore achieves the optimal combination of isolation properties and scalability. Furthermore, being leaderbased these systems require additional wide area round-trips for clients that are not co-located with the leader, and fortransactions that involve keys whose leaders are not co-located.
Raft and Multi-Paxos confer some important properties though: they may assign their leader role to any healthy
process and require only a simple majority of votes, so they may suffer the loss of any minority of replicas and be able
to promptly restore their prior steady-state performance. Transactions that share leaders also do not suffer contention
penalties, and reads may be performed concurrently - they may even circumvent the leader entirely [23, 31]. Leaderlessquorum-based protocols have been proposed [2, 11, 12, 23, 30, 32, 45] that utilise a fast-path to achieve optimal commit
latency under low contention, but these have not been used in real systems. We propose that this is in part explained bytheir unpredictable performance under these same conditions.
In particular, these protocols have fast-path quorums that are disabled by fewer failures than are tolerated overall.
For example, Tempo [11] tolerates f failures using 2 f + 1 replicas, but at most one replica may fail before its fast-path
is unable to reach decisions. Tapir [45] fares better, with a fast path that survives b 2f c failures - but this is half as manyas it tolerates overall, and its optimistic concurrency control fails to guarantee forward progress for all transactions.
1Draft Whitepaper for CEP-15: General Purpose Transactions

ProtocolContention Concurrent
No
No
Round-trips
Reads
Livelock Aborts

TAPIR

2

X

Janus

2

X

Tempo

2

ACCORD

1

X

GeneralPurpose

X
X
X

X

X

X

X

Table 1: Leaderless protocol properties

Switching to the slow-path imposes a burden on the wider system: each operation now consumes more system
resources, as the remaining replicas must process and send more messages. Such additional burden introduces the riskof cascading failure or service degradation. This translates particularly poorly to common failure models. Services
that are expected to continue in the face of major incidents such as natural disaster, or the widespread loss of power orconnectivity, typically utilise multiple regions for redundancy. Existing leaderless protocols require more regions topredictably accommodate the same number of failures. Since each region incurs an independent risk of failure, the riskof experiencing any failure increases as more regions are added. By requiring more regions to accommodate the same
number of failures, these protocols afford less protection overall - as well as any additional fixed costs associated witheach region.
In addition, existing leaderless protocols offer a choice of undesirable trade-offs: either commutative commands must
be serialized [11] or forward progress is not guaranteed [2, 32, 45] (Table 1). These are both properties that we would
rather avoid. Guaranteed forward progress in practice means progress is more predictable, while resource-intensive
read-only transactions are common — serializing them introduces a bottleneck that cannot be readily circumvented
through scaling.
This paper describes techniques to address these shortcomings of leaderless protocols.
We introduce the idea of flexible [18] fast-path quorums for reaching fast-path consensus, offering protocols theability to modify their fast-path criteria. We demonstrate that by modifying these quorums in response to failure, we canretain fast-path availability under any number of tolerated failures. This supports any replica layout without steady-state
performance penalty versus leader-based approaches.
We additionally show how leaderless protocols that utilise timestamps to order transactions [2, 11, 12] may be
combined with topographical knowledge and per-replica message buffers [43] to guarantee single round-trip consensus
under tolerated latency and clock skew, regardless of message arrival order.
Finally, we describe ACCORD, a leaderless protocol designed to exploit these techniques while further guaranteeing
forward progress and permitting commutative commands to be processed concurrently. We propose that this combinationof properties makes ACCORD uniquely suited to providing general purpose distributed transactions.

2

Predictable Leaderless Protocols

There exists a broad literature of leaderless state-machine replication (SMR) protocols [2, 11, 12, 30, 32, 45] that utilise
quorums, with a fast-path that can achieve optimal commit latency. These protocols utilise a process that executes atransaction on behalf of a client that we shall refer to as the transaction’s coordinator. This process is responsible forseeking votes and advancing the distributed state machine.
We assume a partially synchronous network, that processes fail only by crashing, and that there are no more thanf failed processes in any replica set containing r processes where f = b r−1
2 c. We additionally assume a weak failure
detector [5], and that each process has a logical clock that is loosely synchronized with real time.
We introduce the concept of robustness and stability to illustrate some of the compromises entailed by these
protocols.
Robustness. Fast-path quorums are said to be collectively robust to f failures if, in the presence of f failed processes,
there remains at least one such quorum of correct processes.
Stability. A protocol is stable to f failures if no additional per-transaction messages must be exchanged in thepresence of f failed processes. A protocol is similarly stable to contention if no additional messages must be exchanged
when conflicting transactions reach processes out of order.

2

Draft Whitepaper for CEP-15: General Purpose Transactions

FailureProtocolFast-Path

Tolerance

Robustness

Stability

TAPIR

d 32f e + 1f

b 2f cb 2f c

Janus

2f +1

f

0

0

Tempof

2f

f

1

1

Tempo1

f +1

1

1

1

ACCORDf + 1 to d 32f e + 1

f

0 to b 2f c

f

Table 2: Comparison of failure properties with 2 f + 1 replicas per shard

2.1

Flexible Fast-Path Quorums

Existing protocols [2, 11, 32, 45] have fast-path quorums that are robust to fewer failures than are tolerated overall(Table 2). Thus, the protocols are unstable in the face of failure: if fast-path quorums become unreachable, remaining
processes must exchange additional messages to reach slow-path consensus. Recent work [37] has demonstrated that
this trade-off is inherent to leaderless SMR, and that a protocol tolerating f failures cannot have a fast path that is robust
to more than b 2f c failures. Fortunately, the principles of Flexible Paxos [18] provide an alternative.
We declare that fast-path quorums may be reconfigured, but for now leave the mechanism aside. In particular we
may reduce the number of quorums, thereby reducing their collective robustness. We will demonstrate that in doing so
we are able to reduce the size of the remaining quorums, thereby improving stability. The trick is that this is a one-sided
trade: quorums that contain one or more crashed processes no longer contribute to robustness, so we lose nothing by
removing them.
We assume that a protocol utilises three kinds of quorum, or sets of processes that may unanimously reach decisions:fast-path quorums F for one round-trip consensus, simple quorums Q for slow-path consensus, and recovery quorums R
for completing interrupted operations. We make no assumptions about the kind or configuration of these quorums but
define the set of fast-path quorums to be F. For recovery to arbitrate between transactions that may each have potentiallytaken the fast path, it is common to require that any two fast-path quorums must intersect with each other and any/ For protocols that follow this design
recovery quorum at one or more correct replicas [2, 17, 30, 32], i.e., F ∩ F0 ∩ R 6= 0.
it is possible to guarantee stability to all tolerated failures, as we will now demonstrate.
Under maximal tolerated failures there must always be a simple quorum Q0 consisting of correct processes that
may reach decisions, and thus we may always assign our fast-path the set containing only Q0 . In this case all fast paths
use the same quorum, so their intersection is also Q0 . For recovery to be possible on the slow-path, all simple andrecovery quorums must intersect at one or more correct replicas, therefore this set of fast-path quorums maintains our/ Since Q ∩ R 6= 0/ andabove properties. That is to say, if we fix F = {Q0 } so that F = F0 we only require that F ∩ R 6= 0.
/ and we may reach fast-path consensus under maximal tolerated failures.
F = Q0 it must therefore be that F ∩ R 6= 0,This ensures no additional per-transaction messages must be exchanged under any number of tolerated failures,providing optimal stability to failure.
2.1.1

Fast-Path Electorates

Most quorum based protocols [2, 11, 21, 30, 34] use simple vote thresholds, where any replica may vote in combination
with any other. This is the simplest model to reason about, so we adopt it for ACCORD. We introduce the concept of anelectorate, namely those replicas whose votes may be counted towards such a vote threshold. Ordinarily all replicas are
members of both the simple and fast-path electorates, but in the case of the fast-path we may remove replicas in orderto reduce the successful vote threshold. We define a fast-path electorate E, the membership of which makes fast-pathdecisions. To maintain the previously outlined recovery properties, namely that the intersection of any recovery quorum
with any two fast-path quorums contains at least one correct replica, we derive the vote threshold as follows:|F| − (|E| −|F|) − f > 0
|E| + f + 1
|F| =
=⇒
2

(1)
(2)
3

Draft Whitepaper for CEP-15: General Purpose Transactions

For example, a replica set of r = 9 processes tolerating f = 4 failures could choose an electorate of size 9, 7 or
5 conferring fast-path quorums of 7, 6 and 5 respectively. An electorate of 9 could then reach fast-path decisions
with fewer than 3 failed processes, at which point the electorate would need to be reduced to either 7 or 5. Under the
maximum 4 tolerated failures, all 4 failed processes would need to be excluded from the electorate so that all fast- andslow-path decisions would use the same quorum.

2.2

Timestamp Reorder Buffer

Leaderless consensus protocols can directly process transactions from clients in any region, but this capability introduces
the risk of contention: two transactions started at the same time but in different regions may be unable to both reachfast-path consensus. Those replicas closest to each coordinator will witness its corresponding transaction first, so thatno fast-path quorum may witness a consistent order of arrival for either transaction. Recent work [43] has demonstrated
the potential for loosely synchronized clocks to improve this scenario. Coordinators may assign transactions a future
time to be processed on recipient replicas, with the time selected to allow conflicting transactions sent by further-away
coordinators to arrive first.
This approach can be refined to guarantee consensus for every transaction under realistic conditions. Firstly, since
clocks are not perfectly synchronized messages may still be processed too early. By measuring clock asynchrony, or
clock skew we can extend our processing delay to reliably accommodate differences in link latency. Secondly, byutilising a protocol such as Caesar [2] or Tempo [11], that proposes an execution timestamp. Unlike protocols that agree
dependencies [30], where every fast-path vote must witness identical histories, timestamp protocols only require that
voters witness timestamps in ascending order. Therefore, if the message processing time is derived from the transaction’s
proposed execution timestamp we are able to guarantee fast-path consensus for all transactions proposed by a correct
and responsive coordinator, using only two weak assumptions: that we can measure both the latency of our network andthe error margins of our clocks.
We assume a protocol P that utilises a fast-path for one-round consensus, that its correctness is independent of
message arrival order, and that it proposes a timestamp t0 as a transaction’s intended execution time. We will refer tothis round as PreAccept. If a fast path quorum witnesses t0 before any higher timestamp then it must be accepted, andthis must uniquely determine the transaction’s execution order.
We define the set C of all coordinators, SkewMax the maximum instantaneous difference between the logical clocks
on any two nodes, and Latency(C, P) as the latency between some coordinator C and some replica P. We finally define
Deadline(t0 ,C, P) = t0 + SkewMax + max(Latency(C0 , P) | C0 ∈ C) − Latency(C, P). On replica P, receiving a message
from coordinator C, this computes the last point in time at which a transaction might arrive from other members of C
with an earlier t0 .
There are no modifications necessary to protocol P. On receiving a PreAccept request, replicas do not immediately
process the message, instead buffering it in a queue ordered by t0 until the computed Deadline, at which point the buffer
is processed up to and including this message.
Since P’s safety does not depend on message arrival order, it is unaffected by this change. We assume that ourbounds on message latency and clock synchrony are not breached and that processes are responsive. Under these
conditions, this generic change guarantees that for any two transactions γ and τ with t0 γ < t0 τ so that τ could prevent
fast-path consensus for γ, it must be that γ is known to E before τ is processed, and will be processed first. As a result,out-of-order transaction arrival does not result in any additional messages being exchanged.
This provides stability to contention.
2.2.1

Clock Synchrony versus Latency

This technique trades wide area round-trips for an additional latency penalty equal to the bounds on clock synchrony.
How useful is this exchange in practice? Many modern data centres have at least one high quality time source suchas GPS that is typically combined with a protocol such as NTP or PTP to synchronize commodity time sources
residing on the local network, such as those embedded into modern CPUs. In this configuration clock skew may be
sub-millisecond [15], so that this penalty will likely be dwarfed by wide-area latency. Importantly any additional latency
is uncorrelated with wide-area latency: each locale has its own time source and dissemination mechanism, so that
accommodating clock skew represents a fixed global penalty.

4

Draft Whitepaper for CEP-15: General Purpose Transactions

3

ACCORD Basic Protocol

ACCORD builds upon a rich history of leaderless state-machine replication (SMR) protocols [2, 11, 12, 32] exploiting theintuitions of EPaxos [30]. This broad approach can be viewed as performing a separate instance of classic Paxos for eachtransaction to agree its execution order, with a special initial round that permits faster consensus. Recent work has shownthat this technique can be easily extended to partial state-machine replication (PSMR) scenarios for improved scalability,with shards replicating only a portion of the global state-machine [11, 32]. ACCORD utilises this approach to agree atimestamp to determine a transaction’s execution order, reducing the incidence of contention. Like Caesar [2], ACCORD
uses its consensus acknowledgments to determine the set of conflicting transactions that may execute earlier, however the
worst case behaviour is improved so that consensus is reached in at most two round-trips, and live-lock [11] is avoided.
Uniquely, this dependency set is not decided consistently during consensus - only a superset of each transaction’s final
dependencies is determined, that may be filtered during execution to ensure consistency. This approach achieves anoptimal baseline combination of characteristics compared to comparable state-of-the-art protocols, providing a suitable
platform for utilising a fast-path electorate and reorder buffer.
As is typical for Paxos [21] derivatives, ballots are used to ensure only the most recent command for a given phase
may complete [2, 11, 23, 30]. For brevity we elide the handling of these ballots from the Consensus protocol, andimplicitly discard messages if a newer ballot has been witnessed. We additionally discard messages from earlier phasesof the protocol.
Transactions are denoted by γ, τ and υ. We say that two transactions γ and τ conflict (γ ∼ τ) if their execution is notcommutative, so that either their response or the database state would differ if their execution order were reversed.
Variables declared with a τ subscript are persistent, storing the most recent value for τ on that process. ρ, E, Q, F
represent, respectively, a replica-set for a single shard, its fast-path electorate, and a simple and fast-path quorum. By
the same token, Pτ , Eτ , Qτ , Fτ denote the replica-sets participating in τ, the union of their fast-path electorates, and a setof responses constituting a simple and fast-path quorum in each replica-set in Pτ .

3.1

Overview

A client process that wishes to execute a transaction selects a nearby non-replica coordinator C to perform consensus
with Algorithm 1 so that an execution timestamp may be decided. Along with this timestamp, the protocol also
determines a set of conflicting transactions that might precede our execution. Algorithm 2 is then performed, also by
C, so that general-purpose transactions combining cross-shard state may be executed. C steps through several phases
across these two protocols: PreAccept, Accept, Commit, Execute and Apply, all of which must occur in sequence. Only
Accept may be skipped, if the fast path is taken. PreAccept and Accept collectively decide the order of execution, whichis durably decided prior to entry to Commit, where this decision is disseminated to dependent transactions. Execute
then awaits the execution of those dependencies with lower execution timestamps before computing the result of thetransaction. Apply persists this result to all replicas. Should the coordinator fail, a weak failure detector invokes therecovery protocol on a replica that has witnessed the transaction, that then takes over the coordinator role from the last
successfully completed phase.
In the following sections the consensus and execution protocols will be described in detail, alongside certain simple
properties that they maintain. In Section 4 the recovery protocol will be described for finishing interrupted transactions.
In Section 3.4 and Section 4 these properties will be used to demonstrate that these protocols in combination maintainthe following properties:
Consistency. Conflicting transactions are applied in the same order on all participating replicas.
Real-time order. Any transaction γ acknowledged before a conflicting transaction τ has been submitted is executedand applied before τ on all replicas in common.
Liveness. Any transaction that is known by at least one correct replica will execute eventually and apply on all
correct participating replicas.

3.2

Consensus

ACCORD imposes a total order on conflicting transactions by assigning them each a unique execution timestamp.
Timestamps consist of a tuple (time, seq, id), where time is assigned from a per-process monotonically increasing valuethat is loosely synchronised with the wall clock, seq is a logical time component and id is a unique identifier of theprocess that created the timestamp. A timestamp sorts by its components in precedence of their declared order. We
5

Draft Whitepaper for CEP-15: General Purpose Transactions

use three symbols to represent timestamps t0 ≤ t ≤ T where t0 denotes the timestamp first proposed by PreAccept, t a
proposed execution timestamp and Tτ the highest timestamp witnessed by a process for τ.
At a high level, a Lamport clock of these timestamps assigns execution times to conflicting transactions, imposing
a total order [20]. ACCORD ensures this order is consistent for transactions that have been acknowledged to clients,
so that in the event of failure the same total order will be recovered. Initially, a transaction coordinator proposes atimestamp for execution. If a fast-path quorum of replicas unanimously accept and record this timestamp as the mostrecent, then only this single timestamp may be recovered and it is decided immediately. Otherwise some replicas
have responded proposing newer timestamps, so that there are multiple possible Lamport timestamps that may berecovered, and therefore distinct total orders. In this case a slow path using classic Paxos durably agrees which of these
possibilities is decided. To execute transactions in timestamp order, replicas also inform coordinators of any conflicting
transactions that may take an earlier timestamp. Execution proceeds once these have all committed, and any with anearlier timestamp have executed. This is now described in more detail, alongside certain properties that are maintained.
Algorithm 1 Consensus Protocol
receive τ on coordinator C from client:
1: t0 ← (now, 0, C)
2: send PreAccept(τ,t0 ) to ∀p ∈ Eτ
receive PreAccept(τ,t0 τ ) on p:
3: if t0 τ > max(Tγ | γ ∼ τ) then4:tτ ← t0 τ
5: else6:tτ ← max(Tγ | γ ∼ τ)7:tτ .(seq, id) ← (tτ .seq + 1, p)
8: end if
9: Tτ ← tτ
10: PreAcceptedτ ← true
11: reply PreAcceptOK(tτ , deps : {γ | γ ∼ τ ∧ t0 γ < t0 τ })receive PreAcceptOK(t, deps) from Qτ :S
12: deps ← {p.deps | p ∈ Qτ }13: if ∃F τ ⊆ Qτ (∀p ∈ F τ · p.t = t0 ) then14:
send Commit(τ,t0 ,t0 , deps) to ∀p ∈ ρ ∈ Pτ15:
go to Execution Protocol
16: else
17:t ← max(p.t | p ∈ Qτ )18:
send Accept(τ,t0 , t, deps) to ∀p ∈ ρ ∈ Pτ
19: end if
receive Accept(τ,t0 τ , tτ , depsτ ):20: Tτ ← max(tτ , Tτ )21: Acceptedτ ← true
22: reply AcceptOK(deps : {γ | γ ∼ τ ∧ t0 γ < tτ })receive AcceptOK(deps) on C from Qτ :S
23: deps ← {p.deps | p ∈ Qτ }24: send Commit(τ,t0 , t, deps) to ∀p ∈ ρ ∈ Pτ25: go to Execution Protocol
Property 3.1 (Timestamp ordering). For any two conflicting transactions γ ∼ τ where γ commits before τ is submitted
by a client, tγ < tτ .
The coordinator assigns transaction τ a globally unique timestamp t0 and proposes this to Eτ , the members of all
fast-path electorates participating in τ. This is the lowest possible execution timestamp t that τ may take. On recipient
replicas, t0 is compared with the largest timestamp witnessed for all conflicting transactions γ ∼ τ. If it is larger, thereplica votes in favour of setting t = t0 ; otherwise a new larger t is proposed. In either case the proposed t is stored by
the replica so that it may only vote for higher timestamps for future conflicting transactions.
6Draft Whitepaper for CEP-15: General Purpose Transactions

Each replica additionally includes in its PreAcceptOK response the set depsτ of conflicting transactions γ ∼ τwitnessed by the replica that might take a lower execution timestamp, namely those where t0 γ < t0 τ . Note that any
transitive dependency of another γ ∈ depsτ where Committedγ may be pruned from depsτ , as it is durably a transitive
dependency of τ.
Property 3.2 (Timestamp consistency). All processes that commit a transaction do so with the same timestamp.
If a fast-path quorum Fτ votes to accept t = t0 , this timestamp is durably decided and is committed to all replicas
participating in τ. Fast-path quorums and their durability are described in more detail in Section 4.
If insufficient fast-path responses are received, the maximum t from any simple quorum Qτ may be taken to impose
a valid total order [20]. However there is no single t that can be durably recovered should this coordinator fail. To ensure
consistency we require that a recovery coordinator will select the same t that we proceed to Execute with. We achieve
this with an Accept phase that can be viewed as a classic Paxos Accept phase with a privileged initial ballot b0 , similar
to Fast Paxos [23]. This phase requires only a simple quorum for all ρ ∈ Pτ before τ may be committed.
In this case every replica includes in its AcceptOK response the set of conflicting transactions γ ∼ τ witnessed by
the replica that might take a lower execution timestamp, namely those where t0 γ < tτ .

3.3

Execution

Once tτ is decided it is logically committed, and disseminated to every shard alongside depsτ via Commit so that
other transactions with an earlier execution timestamp that had witnessed us during consensus may proceed. Note that
only tτ is durably committed, depsτ is only recorded for recovery purposes outlined in Section 4. Simultaneously thecoordinator issues Read messages to at least one process in each ρ ∈ Pτ , including the nearest correct process for eachshard. In common configurations this will permit a response without any wide-area latency. The Read request includes
the subset of depsτ that interacts with ρ , and replicas wait to answer this message until every such dependency has
either been witnessed as committed with a higher execution timestamp tγ > tτ , or its result has been applied locally.
Replicas do not advance further until the coordinator evaluates τ against these responses and submits Apply messages,that must in turn be received by replicas before they may process conflicting transactions with a higher timestamp.
Algorithm 2 Execution Protocol
Coordinator C:
26: for ρ ∈ Pτ do
27:depsρ ← {γ | γ ∈ deps ∧ ρ ∈ Pγ }28:
send Read(τ, t, depsρ ) to some nearby p ∈ ρ
29: end forreceive Commit(τ,t0 τ , tτ , depsτ ):30: Committedτ ← truereceive Read(τ, tτ , depsτ,ρ ) on p:
31: await Committedγ ∀γ ∈ depsτ,ρ
32: await Appliedγ ∀γ ∈ depsτ,ρ , tγ < tτ
33: reads ← read(τ)
34: reply ReadOK(reads)
receive ReadOK(reads) from each shard:
35: result ← execute(τ, reads)
36: send Apply(τ, t, depsτ,ρ , result) to ∀p ∈ ρ ∈ Pτ37: send result to client
receive Apply(τ, tτ , depsτ,ρ , resultτ ):38: await Committedγ ∀γ ∈ depsτ,ρ
39: await Appliedγ ∀γ ∈ depsτ,ρ , tγ < tτ
40: apply(writes, tτ )41: Appliedτ ← true
Note. The result of execution is persisted at replicas to avoid the following situation: if a transaction involving
shards a and b is applied at all correct ρa , but is unapplied at all correct ρb , we would be unable to re-compute the result7

Draft Whitepaper for CEP-15: General Purpose Transactionsof τ, and transactions that conflict on b would be unable to proceed. By persisting its result, these transactions may
consult a to complete τ on b.

3.4

SafetyWe now demonstrate that this protocol maintains the atomicity and strict-serializable isolation properties, namely thatevery transaction is executed by every replica, in the same order, and that to an external observer every transaction
occurs in an order consistent with the real-time order of client-visible events.
Property 3.3 (Dependency safety). Any coordinator committing τ with tτ does so with depsτ containing all conflicting
γ that may be committed with tγ < tτ .
Proof. Suppose τ is committed with tτ and depsτ , and consider any γ that commits with tγ < tτ . Each of γ, τ may havecommitted via the slow- or fast-paths. We illustrate the case where both γ, τ committed via the slow-path; the othercases are similar. By assumption, γ is pre-accepted at some slow-path quorum Qγ , where each replica in Qγ pre-accepted
γ for some execution timestamp ≤ tγ . Meanwhile, τ must be accepted at some slow-path quorum Qτ with tτ . Then for
any replica P in Qγ ∩ Qτ , P must have pre-accepted γ before accepting τ, since otherwise P will not have pre-accepted γwith an execution timestamp less than tτ . As a result, by the Accept Phase of the protocol, γ ∈ depsτ .
Property 3.4 (Timestamp order). For any transactions γ and τ where γ ∼ τ and tγ < tτ , τ executes after γ.
Proof. By Property 3.3 the coordinator knows all γ that may be committed with tγ < tτ . By waiting for these to commit
we know all γ where tγ < tτ and wait for them to apply on a replica of each shard.
Property 3.5 (Application order). For any transaction τ, τ applies at p after all γ ∼ τ where, once γ is committed,
tγ < tτ .
Proof. By Property 3.3 the coordinator knows all γ that may be committed with tγ < tτ , and waits for them to apply
before sending the result of executing τ to p. The subset of depsτ that applies on p is included, and p waits for thissubset to apply locally before applying τ.
Theorem 3.1 (Consistency). For any two conflicting transactions γ ∼ τ where γ is applied before τ on some replica, γ
will be applied before τ on all replicas in common.
Proof. By Properties 3.2, 3.3 and 3.4, tγ < tτ and γ ∈ depsτ . By Properties 3.4 and 3.5 γ executes before τ and applies
before τ at all replicas.
Theorem 3.2 (Real-time order). For any two conflicting transactions γ ∼ τ where τ is proposed by a client after γ hasbeen committed, γ executes before τ, and is applied before τ at all replicas in common.
Proof. By Properties 3.1, 3.2 and 3.3, tγ < tτ and γ ∈ depsτ . By Properties 3.4 and 3.5 γ executes before τ and applies
before τ at all replicas.

4

Recovery Protocol

Algorithm 3 is invoked by a weak failure detector to recover a transaction τ whose coordinator has failed. This protocol
contacts a recovery quorum Rτ that ensures τ is pre-accepted before responding, ensuring the properties of normal
execution are maintained against any υ that had not previously committed. For those υ that had already committed wemust now demonstrate that we maintain our declared properties while recovering τ. In the case where τ has reached aslow-path decision, any quorum R ⊆ ρ where |R| ≥ r − f must witness at least one response from the last completed
phase of the state machine. The state machine can be picked-up from this point, similarly maintaining the properties ofnormal execution. We now only require a similar capability for fast-path decisions.
Fast-path recovery operates on a simple intuition: if we may deduce that an incomplete transaction τ either cannot
have been committed on the fast path or that any υ that may execute after τ has τ ∈ depsυ , then we may safely proposet = t0 by the slow path. If υ is committed after the recovery quorum was reached then it must witness τ. Otherwise
this is achieved by using the deps associated with all Accepted or Committed υ that supersede τ: if any of these had
8Draft Whitepaper for CEP-15: General Purpose Transactions

Algorithm 3 Recovery Protocol
Coordinator C:
1: b ← fresh ballot
2: send Recover(b, τ,t0 ) to ∀p ∈ ρ ∈ Pτ
receive Recover(b, τ,t0 ) on p:
3: if b ≤ MaxBallotτ then4:
reply NACK(bτ )5: else6:
MaxBallotτ ← b
7:
Accepts ← {γ | γ ∼ τ ∧ τ 6∈ depsγ ∧ Acceptedγ }8:Commits ← {γ | γ ∼ τ ∧ τ 6∈ depsγ ∧ Committedγ }9:Wait ← {γ ∈ Accepts | t0 γ < t0 τ ∧tγ > t0 τ }10:Superseding ← {γ ∈ Accepts | t0 γ > t0 τ }11:∪{γ ∈ Commits | tγ > t0 τ }12:
if 6 PreAcceptedτ then13:
run Consensus Protocol L3 to L10
14:
end if15:
if ¬Acceptedτ ∧ ¬Committedτ ∧ ¬Appliedτ then16:
depsτ ← {γ | γ ∼ τ ∧ t0 γ < t0 τ }17:
end if18:
reply RecoverOK(∗τ , Superseding, Wait)
19: end if
receive NACK on C:
20: yield to competing coordinatorreceive RecoverOK(∗, Superseding, Wait) from p ∈ Rτ21: if ∃p ∈ Rτ (p.Applied τ ) then22:
send response(result) to client
23:
send Apply(τ,t0 , p.t, p.deps, result) to ∀p0 ∈ ρ ∈ P
24: else if ∃p ∈ Rτ (p.Committed τ ) then25:
send Commit(τ,t0 , p.t, p.deps)∀p0 ∈ ρ ∈ Pτ26:
go to Execution Protocol
27: else if ∃p ∈ Rτ (Accepted τ ) then28:
select p with highest accepted ballot29:t ← p.t; deps ← p.deps
30:
go to Consensus Protocol L18
31: else
S
32:t ← t0 ; deps ← {p.depsτ | p ∈ Rτ }33:
if ∃i {p ∈ E | p.t > p.t0 } > |E| −|Fi | then34:t ← max(p.t | p ∈ Rτ )/ then35:
else if ∃p ∈ Rτ (p.Superseding 6= 0)36:
t ←Smax(p.t | p ∈ Rτ )37:else if {p.Wait | p ∈ Rτ } 6=S
0/ then38:
await Committedγ (∀γ ∈ {p.Wait | p ∈ Rτ })39:
restart Recovery Protocol
40:
end if41:
go to Consensus Protocol L18
42: end if. PreAccept. Accept. Accept9Draft Whitepaper for CEP-15: General Purpose Transactions

not witnessed τ in depsυ then τ had not reached a fast-path before they did, and since υ supersedes τ it may not reachfast-path consensus after. Conversely, if all have witnessed τ then they will wait for τ to commit so that we may propose
any t, including t0 .
In more detail, given transactions υ ∼ τ where υ supersedes τ, any shard ρ that υ and τ have in common, any
recovery quorum Rτ , and any subset E of the shard’s electorate that may be witnessed by this quorum1 , we must be able
to determine either that τ is not pre-accepted or that τ ∈ depsυ . To achieve this, as outlined in Section 2.1.1 we ensure/ i.e. that |F| = d |E|+2f +1 e. Now any τ that did not take the fast path must have fewer than r −|F|that Fτ ∩ Fυ ∩ E 6= 0,
votes for t = t0 . However not all τ with this many votes took the fast path, so we must either (1) deduce from otherinformation that they did not, so that we may propose a higher timestamp; or (2) determine that it is safe to propose t = t0
regardless. If τ was committed on the fast-path then proposing t = t0 is correct. If it was not then Timestamp consistency
and Timestamp ordering are unaffected by proposing t = t0 , so that we must only demonstrate that Dependency safetycontinues to be maintained in this case.
By definition, if both τ and υ may have reached fast-path consensus then Fτ ∩ Fυ 6= 0/ so that τ ∈ depsυ . By simple
induction this maintains Dependency safety between all transactions that may have committed on the fast-path.
For any υ committed on the slow path, an Accept or Commit must be witnessed by Rτ so that we may inspectdepsυ . If Acceptedυ , υ must have reached a simple quorum Qυ during PreAccept before proposing depsυ , so that ifτ∈/ depsυ and t0 υ > t0 τ we know that τ could not have reached fast-path consensus and we may proceed on the slow
path. Similarly, if Committedυ , υ must have reached Qυ during Accept so we may test tυ > t0 τ ∧ τ ∈/ depsυ . Conversely,
if τ ∈ depsυ and υ successfully committed, any execution of υ will know of τ so that Dependency Safety is maintained.
This leaves only those transactions γ where t0 γ < t0 τ that may have reached slow-path consensus with tγ > t0 τ buthave not been committed. Such transactions may not have witnessed τ without prohibiting τ from reaching fast-path
consensus. If we have not determined the correct course of action by other means, we may simply wait for thesetransactions to commit, or commit them ourselves.
Theorem 4.1 (Liveness). A transaction τ that is known by at least one healthy replica will always execute eventually
and apply on all correct participating replicas
Proof. A healthy coordinator executing the consensus protocol defined in Algorithm 1 always commits τ in a fixed
number of steps unless superseded by a recovery coordinator. If the coordinator process is faulty then, given synchrony
conditions and weak failure detectors, a recovery coordinator is eventually picked. The recovery protocol defined in
Algorithm 3 commits in a fixed number of steps unless there exists an γ where Acceptedγ ∧ t0 γ < t0 τ ∧ tγ > t0 τ . Given
loosely synchronized clocks there are finite γ, so by simple induction all commands are able to commit eventually. Once
committed, execution waits only for those commands γ ∈ depsτ where tγ < tτ , so all commands are able to eventually
execute. This result is sent to Apply on all healthy replicas. If a healthy process witnesses τ, but does not witness Apply,
it eventually invokes the recovery protocol.

5

Reconfiguring Electorates

A configuration consists of a monotonically increasing epoch identifier, the membership of all shards ρ and their fastpath electorates E. We say that a configuration ei+1 has taken effect on ρ once a simple quorum of ρei , the membershipof ρ as decided by ei , is aware of it.
Timestamps are modified to include epoch as their first value, so that a transaction τ is coordinated by C withconfiguration e1 using t0 τ .epoch = e1 . Any p ∈ ρe1 with a newer configuration e2 will respond to PreAccept withtτ .epoch = e2 so that p may not participate in fast-path decision. This alerts C to the new configuration, which is
fetched asynchronously. If a fast-path quorum is not reached with ρe1 , we wait for the new configuration and for Qe2
PreAcceptOK responses - if necessary sending additional PreAccept to ρe2 . The remainder of the Consensus protocol
executes for both configurations simultaneously, i.e. so that Accept is sent to all Pτ = Pτe1 ∪ Pτe2 , and Qτ = Qτe1 ∪ Qτe2
must respond with AcceptOk before we may proceed to the Commit phase. The Execution protocol must wait for depsτ
to apply in Pτe1 only, before applying in Pτe2 only. The Recovery protocol remains unmodified, depending only on thesechanges to the Consensus and Execution protocols.
This ensures atomic migration from one configuration to another. No replica that is aware of e2 may participate ina fast-path decision using e1 , so if sufficient fast-path responses are received e2 has not taken effect and τ completes
1 That is, where t0τ

< t0 υ , ρ ∈ (Pτ ∩ Pυ ), E ⊆ ρ and E = Rτ ∩ E

10Draft Whitepaper for CEP-15: General Purpose Transactions

normally. A slow-path decision executes the protocol for both configurations, necessarily informing a majority of ρ ofthe new configuration, so that it takes effect for transactions that follow τ.
However, by itself this modification does not maintain consistency during recovery. Recall that the simultaneousintersection of any two fast-path quorums with any recovery quorum must include at least one correct process. To
ensure this property is maintained, replicas that join the electorate must not participate in any fast-path decision until
all fast-path decisions from the prior configuration are known to them. This is achieved by requiring that at least
1 + Ee1 − Fe1 members of Ee1 inform the new members of Ee2 of all transactions they accepted on the fast-pathunder configurations ≤ e1 . Since these replicas will no longer accept transactions under e1 , and no fast-path decision
may be taken under e1 without at least one of these replicas participating, this constitutes knowledge of all fast-pathdecisions taken under e1 . Therefore, all fast-path decisions involving the new members of Ee2 must witness all fast-pathdecisions taken against e1 . If another configuration e3 adds additional members, those members that joined in e2 must
wait until they have received their join notifications from members of Ee1 before propagating this knowledge on to
those members joining in e3 . This way all new members in any configuration are aware of every fast-path decision
taken by all earlier configurations. Specifically, we introduce a new boolean property ReadyElectoratee , and modify theConsensus Protocol at Line 3 so that a replica p ∈ Eei where p ∈/ Eei−1 also requires Readyei to hold, else the slow pathbranch is taken.
The complete Reconfiguration Protocol is included in the appendix, alongside fully specified versions of theConsensus, Execution and Recovery Protocols integrating the above details. A detailed proof of correctness and livenessproperties for these protocols is also included in the appendix.

6

Related Work

State machine replication (SMR). SMR [38] is a common foundation for building reliable, fault-tolerant systems.
Traditional SMR protocols [21–23, 25, 33, 34] rely on a stable leader to efficiently assign a linearizable ordering toclient requests. Replicas execute requests in this order, and are able to adopt the leader role should it fail. This provides
clients the illusion of a unified service running on a single machine. However, the single leader in these protocols is abottleneck that limits throughput, and results in increased latency for remote clients in a wide area network.
For better performance in geo-replicated systems, SMR protocols such as Mencius [28] and EPaxos [30] havebeen proposed. While Mencius permits the leader role to be efficiently rotated between regions to improve client
latency, if any replica is faulty progress stalls until this is detected and recovered. EPaxos instead discards the conceptof a leader, permitting any replica to coordinate a command at the same time as any other. Dependency graphs andtopological sorting ensure a consistent order of execution for non-commutable commands. Recently EPaxos has been
demonstrated to suffer degraded performance under contended workloads [2, 12, 43]. Two approaches to this problem
have been outlined: loosely synchronized clocks have been employed to synchronize the order in which replicas process
conflicting commands [43], and alternative protocols such as Caesar [2] and Atlas [12] have been proposed that agree
an execution timestamp, permitting replicas to reach consensus without witnessing identical histories, so that conflicts
may be reduced. ACCORD combines both techniques, proposing an execution timestamp and processing messages intimestamp order. This combination provides ACCORD stronger stability properties. Additionally, ACCORD has a worst
case execution path of two wide area round-trips instead of Caesar’s three, ACCORD does not order non-commutative
commands in comparison to Atlas.
Separately, SMR approaches have been proposed that vary failure handling properties. Vertical Paxos [24] demonstrated consensus with an optimal two replicas, by permitting the membership to be reconfigured between rounds.
Flexible Paxos [18] demonstrated that quorums need not be homogenous, and that these quorums may be reconfigured
between rounds, affording similar advantages to Vertical Paxos. Fast Flexible Paxos [17], Atlas [12] and Tempo [11]exploit Flexible Paxos’ non-homogenous quorums to trade failure tolerance for steady-state performance. ACCORD
demonstrates that optimal failure tolerance may be maintained alongside optimal stability to failure by permitting theset of quorums that may reach fast-path decisions to be reconfigured, and that by reducing the number of such quorums
we may reach fast-path decisions under any tolerated failures.
Transactional systems. Transactional storage systems typically partition data into multiple shards for scalability,
and replicate each shard for fault tolerance. Transactions that span across shards hence rely on concurrency control
mechanisms to achieve varying degrees of consistency. For performance reasons, however, many systems [3, 7, 10, 19,11

Draft Whitepaper for CEP-15: General Purpose Transactions

27, 39, 46] offer isolation levels short of strict serializability, or accept scalability bottlenecks [14, 47]. ACCORD differs
by featuring scalable strict serializable transactions.
Among systems that do offer strict serializable transactions, Spanner [8], CLOCC [1, 26], and Granola [9] build atransaction layer on top of a replication layer, leading to increased latency [45]. Calvin [41] and SLOG [35] similarly
rely on a distinct Paxos layer to order multi-shard transactions. Tapir [32] is the first to address the over-coordination
inherent to such architectures, offering strict serializable multi-shard transactions in a single wide area round-trip.
Likewise, Janus [32] uses an EPaxos-like approach to provide multi-shard transactions, offering better performance
than Tapir under contended workloads, albeit with limited stored procedure semantics and no stability to failure. Morerecently, Tempo [11] improves upon Janus by leveraging timestamps instead of explicit dependencies, at a cost ofordering non-commutative transactions.
Compared to prior systems that achieve strict serializable multi-shard transactions, ACCORD achieves optimal
performance by utilizing real time timestamps and a message reorder buffer. Unlike Tempo, ACCORD does not relyon additional periodic broadcast mechanisms for timestamp stability, and commutative commands do not interfere.
Importantly, ACCORD addresses the poor fast-path stability of existing systems by introducing a configurable fast-pathelectorate. This provides optimal failure tolerance and consistent performance under any number of tolerated failures.
ACCORD is the first leaderless protocol that is sufficiently stable for practical use in a large scale industrial databasesystem. Finally, to the best of our knowledge, no commercial or open-source database systems offer strict serializable
transactions across regions in a single wide area round-trip.

References[1] Atul Adya, Robert Gruber, Barbara Liskov, and Umesh Maheshwari. Efficient optimistic concurrency control using
loosely synchronized clocks. In Proceedings of the 1995 ACM SIGMOD International Conference on Managementof Data, SIGMOD ’95, page 23–34, New York, NY, USA, 1995. Association for Computing Machinery.
[2] Balaji Arun, Sebastiano Peluso, Roberto Palmieri, Giuliano Losa, and Binoy Ravindran. Speeding up consensus bychasing fast decisions. In 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks,
04 2017.
[3] Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony
Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat
Venkataramani. TAO: Facebook’s distributed data store for the social graph. In 2013 USENIX Annual TechnicalConference (USENIX ATC 13), pages 49–60, San Jose, CA, June 2013. USENIX Association.
[4] Apache Cassandra. https://cassandra.apache.org/.
[5] Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus.
J. ACM, 43(4):685–722, July 1996.
[6] CockroachDB. https://www.cockroachlabs.com.
[7] Brian F. Cooper, Raghu Ramakrishnan, Utkarsh Srivastava, Adam Silberstein, Philip Bohannon, Hans-Arno
Jacobsen, Nick Puz, Daniel Weaver, and Ramana Yerneni. Pnuts: Yahoo!’s hosted data serving platform. Proc.
VLDB Endow., 1(2):1277–1288, August 2008.
[8] James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ 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. Spanner: Google’s
globally-distributed database. In 10th USENIX Symposium on Operating Systems Design and Implementation(OSDI 12), pages 261–264, Hollywood, CA, October 2012. USENIX Association.
[9] James Cowling and Barbara Liskov. Granola: Low-overhead distributed transaction coordination. In Proceedingsof the 2012 USENIX Annual Technical Conference, Boston, MA, USA, June 2012. USENIX.

12Draft Whitepaper for CEP-15: General Purpose Transactions[10] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin,
Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon’s highly available key-value
store. 41(6):205–220, 2007.
[11] Vitor Enes, Carlos Baquero, Alexey Gotsman, and Pierre Sutra. Efficient Replication via Timestamp Stability,
page 178–193. Association for Computing Machinery, New York, NY, USA, 2021.
[12] Vitor Enes, Carlos Baquero, Tuanir Rezende, Alexey Gotsman, Matthieu Perrin, and Pierre Sutra. State-machine
replication for planet-scale systems. In EuroSys ’20: Proceedings of the Fifteenth European Conference on
Computer Systems, pages 1–15, 04 2020.
[13] etcd. https://etcd.io.
[14] FaunaDB. https://fauna.com.
[15] Yilong Geng, Shiyu Liu, Zi Yin, Ashish Naik, Balaji Prabhakar, Mendel Rosenblum, and Amin Vahdat. Exploiting anatural network effect for scalable, fine-grained clock synchronization. In 15th USENIX Symposium on Networked
Systems Design and Implementation (NSDI 18), pages 81–94, Renton, WA, April 2018. USENIX Association.
[16] Hazelcast. https://hazelcast.com.
[17] Heidi Howard, Aleksey Charapko, and Richard Mortier. Fast flexible paxos: Relaxing quorum intersection for fast
paxos. In International Conference on Distributed Computing and Networking 2021, ICDCN ’21, page 186–190,
New York, NY, USA, 2021. Association for Computing Machinery.
[18] Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. Flexible paxos: Quorum intersection revisited. CoRR,
abs/1608.06696, 2016.
[19] Tim Kraska, Gene Pang, Michael J. Franklin, Samuel Madden, and Alan Fekete. Mdcc: Multi-data center
consistency. In Proceedings of the 8th ACM European Conference on Computer Systems, EuroSys ’13, page
113–126, New York, NY, USA, 2013. Association for Computing Machinery.
[20] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558–565,
July 1978.
[21] Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133–169, May 1998.
[22] Leslie Lamport. Generalized consensus and paxos. Technical Report MSR-TR-2005-33, March 2005.
[23] Leslie Lamport. Fast paxos. Distributed Computing, 19:79–103, October 2006.
[24] Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. Vertical paxos and primary-backup replication. Technical
Report MSR-TR-2009-63, May 2009.
[25] Leslie Lamport and Mike Massa. Cheap paxos. In International Conference on Dependable Systems and Networks(DSN 2004), June 2004.
[26] Barbara Liskov, Miguel Castro, Liuba Shrira, and Atul Adya. Providing persistent objects in distributed systems.
In Proceedings of the 13th European Conference on Object-Oriented Programming, ECOOP ’99, page 230–257,
Berlin, Heidelberg, 1999. Springer-Verlag.
[27] Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. Don’t settle for eventual: Scalablecausal consistency for wide-area storage with cops. In Proceedings of the Twenty-Third ACM Symposium on
Operating Systems Principles, SOSP ’11, page 401–416, New York, NY, USA, 2011. Association for Computing
Machinery.
[28] Yanhua Mao, Flavio P. Junqueira, and Keith Marzullo. Mencius: Building efficient replicated state machines forwans. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI’08,
page 369–384, USA, 2008. USENIX Association.
[29] MongoDB. https://www.mongodb.com.
13

Draft Whitepaper for CEP-15: General Purpose Transactions[30] Iulian Moraru, David G. Andersen, and Michael Kaminsky. There is more consensus in egalitarian parliaments. In
Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, page 358–372,
New York, NY, USA, 2013. Association for Computing Machinery.
[31] Iulian Moraru, David G. Andersen, and Michael Kaminsky. Paxos quorum leases: Fast reads without sacrificing
writes. In Proceedings of the ACM Symposium on Cloud Computing, SOCC ’14, page 1–13, New York, NY, USA,2014. Association for Computing Machinery.
[32] Shuai Mu, Lamont Nelson, Wyatt Lloyd, and Jinyang Li. Consolidating concurrency control and consensus forcommits under conflicts. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI16), pages 517–532, Savannah, GA, November 2016. USENIX Association.
[33] Brian M. Oki and Barbara H. Liskov. Viewstamped replication: A new primary copy method to support highlyavailable distributed systems. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed
Computing, PODC ’88, page 8–17, New York, NY, USA, 1988. Association for Computing Machinery.
[34] Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In 2014 USENIX Annual
Technical Conference (USENIX ATC 14), pages 305–319, Philadelphia, PA, June 2014. USENIX Association.
[35] Kun Ren, Dennis Li, and Daniel J. Abadi. Slog: Serializable, low-latency, geo-replicated transactions. Proc. VLDB
Endow., 12(11):1747–1761, July 2019.
[36] RethinkDB. https://rethinkdb.com.
[37] Tuanir França Rezende and P. Sutra. Leaderless state-machine replication: Specification, properties, limits(extended version). ArXiv, abs/2008.02512, 2020.
[38] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM
Comput. Surv., 22(4):299–319, December 1990.
[39] Yair Sovran, Russell Power, Marcos K. Aguilera, and Jinyang Li. Transactional storage for geo-replicated systems.
In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP ’11, page 385–400,
New York, NY, USA, 2011. Association for Computing Machinery.
[40] Doug Terry. Transactions and scalability in cloud databases - why can’t we have both? In Proceedings of the 18th
International Workshop on High Performance Transaction Systems (HPTS), November 2019.
[41] Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J. Abadi. Calvin: Fast
distributed transactions for partitioned database systems. In Proceedings of the 2012 ACM SIGMOD International
Conference on Management of Data, SIGMOD ’12, page 1–12, New York, NY, USA, 2012. Association for
Computing Machinery.
[42] TiKV. https://tikv.org.
[43] Sarah Tollman, Seo Jin Park, and John Ousterhout. Epaxos revisited. In 18th USENIX Symposium on Networked
Systems Design and Implementation (NSDI 21), pages 613–632. USENIX Association, April 2021.
[44] YugaByte. https://www.yugabyte.com.
[45] Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. Building
consistent transactions with inconsistent replication. ACM Trans. Comput. Syst., 35(4), December 2018.
[46] Yang Zhang, Russell Power, Siyuan Zhou, Yair Sovran, Marcos K. Aguilera, and Jinyang Li. Transaction chains:
Achieving serializability with low latency in geo-distributed storage systems. In Proceedings of the TwentyFourth ACM Symposium on Operating Systems Principles, SOSP ’13, page 276–291, New York, NY, USA, 2013.
Association for Computing Machinery.

14

Draft Whitepaper for CEP-15: General Purpose Transactions[47] Jingyu Zhou, Meng Xu, Alexander Shraer, Bala Namasivayam, Alex Miller, Evan Tschannen, Steve Atherton,
Andrew J. Beamon, Rusty Sears, John Leach, Dave Rosenthal, Xin Dong, Will Wilson, Ben Collins, David
Scherer, Alec Grieser, Young Liu, Alvin Moore, Bhaskar Muppana, Xiaoge Su, and Vishesh Yadav. Foundationdb:
A distributed unbundled transactional key value store. In Proceedings of the 2021 International Conference
on Management of Data, SIGMOD/PODS ’21, page 2653–2666, New York, NY, USA, 2021. Association for
Computing Machinery.

A

Full Protocol Specification

Notation. Qτt is shorthand for Qτt.epoch

15

Draft Whitepaper for CEP-15: General Purpose Transactions

Algorithm 4 Consensus Protocol (with reconfiguration and ballots)
receive τ on coordinator C from client:
1: t0 ← (Epoch, now, 0, C)
2: send PreAccept(τ,t0 ) to ∀p ∈ Eτ
receive PreAccept(τ,t0 τ ) on p:
3: if MaxBallotτ > 0 then4:
reply NACK
5: else if PreAcceptedτ ∨ Acceptedτ ∨ Committedτ ∨ Appliedτ then6:
return7: else8:
if t0 .epoch = Epoch ∧ t0 τ > max(Tγ | γ ∼ τ) ∧ ReadyElectoratee then9:tτ ← t0 τ
10:
else
11:
tτ ← max(Tγ | γ ∼ τ)
12:tτ .(seq, id) ← (tτ .seq + 1, p)
13:
end if14:
Tτ ← tτ
15:
PreAcceptedτ ← true
16:
reply PreAcceptOK(tτ , deps : {γ | γ ∼ τ ∧ t0 γ < t0 τ })17: end if
receive PreAcceptOK(t, deps) from Qtτ0 where Qtτ0 6⊇ Qτt :18: send PreAccept(τ,t0 ) to ∀p ∈ Eτt \ Etτ0
receive PreAcceptOK(t, deps) from Qτ ⊇ Qtτ0 ∪ Qτt :S
19: deps ← {p.deps | p ∈ Qτ }20: if ∃F τ ⊆ Qτ (∀p ∈ F τ · p.t = t0 ) then21:
send Commit(τ,t0 ,t0 , deps) to ∀p ∈ ρ ∈ Ptτ0 ∪ Pτt
22:
go to Execution Protocol
23: else
24:t ← max(p.t | p ∈ Qτ )25:
send Accept(0, τ,t0 , t, deps) to ∀p ∈ ρ ∈ Ptτ0 ∪ Pτt
26: end if
receive Accept(b, τ,t0 τ , tτ , depsτ ):27: if b < MaxBallotτ then28:
reply NACK
29: else if Committedτ ∨ Appliedτ then30:
return31: else
32:
MaxBallotτ ← b
33:
AcceptedBallotτ ← b
34:
Tτ ← max(tτ , Tτ )35:
Acceptedτ ← true
36:
reply AcceptOK(deps : {γ | γ ∼ τ ∧ t0 γ < tτ })37: end if
receive NACK on C:
38: yield to competing coordinatorreceive AcceptOK(deps) on C from Qtτ0 ∪ Qτt :S
39: deps ← {p.deps | p ∈ Qτ }40: send Commit(τ,t0 , t, deps) to ∀p ∈ ρ ∈ Ptτ0 ∪ Pτt
41: go to Execution Protocol

16

Draft Whitepaper for CEP-15: General Purpose Transactions

Algorithm 5 Execution Protocol (with reconfiguration and ballots)
Coordinator C:
42: for ρ ∈ Pτ do
43:depsρ ← {γ | γ ∈ deps ∧ ρ ∈ Pγ }44:send Read(τ, t, depsρ ) to some nearby correct p ∈ ρ
45: end forreceive Commit(τ,t0 τ , tτ , depsτ ):46: Committedτ ← truereceive Read(τ, tτ , depsτ,ρ ) on p:
47: await Committedγ ∀γ ∈ depsτ,ρ
48: await Appliedγ ∀γ ∈ depsτ,ρ , tγ < tτ
49: reads ← read(τ)
50: reply ReadOK(reads)
receive ReadOK(reads) from each shard:
51: result ← execute(τ, reads)
52: send Apply(τ, t, depsτ,ρ , result) to ∀p ∈ ρ ∈ Pτt
53: send result to client
receive Apply(τ, tτ , depsτ,ρ , resultτ ):54: if ¬Appliedτ then55:
await Committedγ ∀γ ∈ depsτ,ρ
56:
await Appliedγ ∀γ ∈ depsτ,ρ , tγ < tτ
57:
apply(writes, tτ )58:
Appliedτ ← true
59: end if

17

Draft Whitepaper for CEP-15: General Purpose Transactions

Algorithm 6 Reconfiguration Protocol
receive new configuration Con f ige+1 on process p :1: await ReadyEpoch = e
2: if p ∈ Ee−1 then3:await ReadyElectoratee
4:
send JoinElectorate({τ | tτ = t0 τ }, e + 1) to ∀p ∈ (Ee+1 \ Ee )5: end if
6: if p ∈ Ee+1 ∧ p ∈/ Ee then7:
ReadyElectoratee+1 ← false
8: else9:
ReadyElectoratee+1 ← true
10: end if
11: Epoch ← e + 1
12: ReadyReconfiguree+1 ← true
13: if p ∈ ρe ∪ ρe+1 then14:await ReadyShard
15:
await Committedτ · ∀τ ∈ {τ | PreAcceptedτ ∧ tτ .epoch ≤ e} . Should only wait for those notified on join, so
introduce a special flag, to prevent forward progress
16:
await Appliedτ · ∀τ ∈ {τ | Committedτ ∧ tτ .epoch ≤ e}17:
send JoinShard({(τ, ∗τ ) | Appliedτ ∧ tτ .epoch ≤ e}, e + 1) to ∀p ∈ (ρe+1 \ ρe ) . TODO: also send commitsthat are dependencies!
18: end if
19: ReadyEpoch ← ereceive JoinElectorate(Txns, e) on replica p from p0 :20: await ReadyReconfiguree+1
21: for ∀τ ∈ Txns do
22:
if ¬PreAcceptedτ then23:
run Consensus Protocol L8 to L15. PreAccept
24:
end if
25: end for
26: ReceivedJoinElectoratee+1 ← ReceivedJoinElectoratee+1 ∪ {p0 }27: ReadyElectoratee+1 ← |ReceivedJoinElectoratee+1 | > Ee − Fereceive JoinShard(Txns, e + 1) on replica p from p0 :28: await ReadyReconfiguree+1
29: for ∀(τ, ∗τ ) ∈ Txns do
30:
if Appliedτ then31:
async receive Apply(τ, tτ , depsτ,ρ , resultτ )32:else if Committedτ then33:
async receive Commit(τ,t0 τ , tτ , depsτ )34:
end if
35: end for
36: await
37: ReceivedJoinShard e+1 ← ReceivedJoinShard e+1 ∪ {p0 }38: ReadyShard ← ∃Qe ⊆ ReceivedJoinShard e+1

18

Draft Whitepaper for CEP-15: General Purpose Transactions

Algorithm 7 Recovery Protocol
Coordinator C:
1: b ← fresh ballot
2: send Recover(b, τ,t0 ) to ∀p ∈ ρ ∈ Pτ[ t0 ]receive Recover(b, τ,t0 ) on p:
3: if b ≤ MaxBallotτ then4:
reply NACK(bτ )5: else6:
MaxBallotτ ← b
7:
Accepts ← {γ | γ ∼ τ ∧ τ 6∈ depsγ ∧ Acceptedγ }8:Commits ← {γ | γ ∼ τ ∧ τ 6∈ depsγ ∧ Committedγ }9:Wait ← {γ ∈ Accepts | t0 γ < t0 τ ∧tγ > t0 τ }10:Superseding ← {γ ∈ Accepts | t0 γ > t0 τ }11:∪{γ ∈ Commits | tγ > t0 τ }12:
if 6 PreAcceptedτ then13:
run Consensus Protocol L8 to L15
14:
end if15:
if ¬Acceptedτ ∧ ¬Committedτ ∧ ¬Appliedτ then16:
depsτ ← {γ | γ ∼ τ ∧ t0 γ < t0 τ }17:
end if18:
reply RecoverOK(∗τ , Superseding, Wait)
19: end if
receive NACK on C:
20: yield to competing coordinatorreceive RecoverOK(∗, Superseding, Wait) from p ∈ Rτ ⊇ Qtτ0
21: if ∃p ∈ Rτ (p.Applied τ ) then22:
send response(result) to client
23:
send Apply(τ,t0 , p.t, p.deps, result) to ∀p0 ∈ ρ ∈ Pτt
24: else if ∃p ∈ Rτ (p.Committed τ ) then25:
send Commit(τ,t0 , p.t, p.deps)∀p0 ∈ ρ ∈ Pτ[ t0 ] ∪ Pτt
26:
go to Execution Protocol
27: else if ∃p ∈ Rτ (Accepted τ ) then28:
select p with highest AcceptedBallotτ
29:t ← p.t; deps ← p.deps
30:
go to Consensus Protocol L19
31: else
S
32:t ← t0 ; deps ← {p.depsτ | p ∈ Rτ }33:
if ∃i {p ∈ E | p.t > p.t0 } > |E| −|Fi | then34:t ← max(p.t | p ∈ Rτ )/ then35:
else if ∃p ∈ Rτ (p.Superseding 6= 0)36:t ← max(p.t | p ∈ Rτ )S
37:else if {p.Wait | p ∈ Rτ } 6= 0/ thenS38:
await Committedγ (∀γ ∈ {p.Wait | p ∈ Rτ })39:
restart Recovery Protocol
40:
end if41:
go to Consensus Protocol L19
42: end if. PreAccept. Accept. Accept

19Draft Whitepaper for CEP-15: General Purpose Transactions

B

Detailed Proof

We introduce the boolean predicates P RE ACCEPTED(P, τ), ACCEPTED(P, τ), C OMMITTED(P, τ) and A PPLIED(P, τ)that indicate the state of the transaction τ on replica P. Specifically, they each correspond to the boolean propertes
PreAcceptedτ , Accepted(τ), Committedτ and Appliedτ on P. Each of these predicates are true iff P records the corresponding boolean property as true, and all following properties (in the order given) as f alse.

B.1

Validity

Theorem B.1 (Validity). Transaction τ executes and applies at replicas only if it was submitted by a client.
Proof. A transaction may only execute after the PreAccept Phase, and may only apply after being executed. The
PreAccept Phase is only performed for transactions submitted by clients.

B.2

Isolation

B.2.1

Consistency

Observation B.1. For any replica P and transaction τ, if PreAcceptedτ then the following are true:
1. P.t0 τ is that which is assigned by the original coordinator for τ
2. P.t0 τ .seq = 0
3. P.t0 τ ≤ P.tτ
Proof. t0 τ is assigned only by L1 of the Consensus Protocol. This is executed only by the original coordinator, andalways assigns a sequence of 0. Candidate values for tτ are assigned by L4 and L6 of the Consensus Protocol, which
both select a value at least as large as t0 τ . The ultimate tτ is selected in a multitude of places, but is always either t0 τ or
the maximum of some collection of these candidate tτ .
Observation B.2. No two transactions are assigned the same t0 .
Proof. Let γ and τ be distinct transactions. By Observation B.1, t0 γ and t0 τ each take only the value assigned by theirrespective original coordinators. If t0 γ and t0 τ are assigned by different coordinators, then the t0 γ .id 6= t0 τ .id. Otherwise,
t0 γ .time 6= t0 τ .time by assumption.
Observation B.3. For any transaction τ, and ballot b belonging to some coordinator C, C attempts to commit τ using
b for at most one distinct tuple.
Proof. The Consensus Protocol may only be invoked once and attempts only one Commit with a single tuple, using
the special ballot b0 that may not be used by the Recovery Protocol. By the Recovery Protocol, b must be larger thanany previous ballot witnessed by a majority of replicas, so a coordinator may not execute the Recovery Protocol twice
using b, and each execution of the Recovery Protocol submits at most one Commit tuple.
Observation B.4. For any replica P and conflicting transactions γ, τ, if P RE ACCEPTED(P, γ) and P RE ACCEPTED(P, τ),with γ arriving at P before τ, then tγ 6= tτ .
Proof. By assumption, tγ is set prior to processing PreAccept for τ, so tτ = t0 τ only if t0 τ > tγ ; otherwise tτ ≥(tγ .time, tγ .seq + 1, P) > tγ .
Lemma B.1. For any replicas P, R and conflicting transactions γ, τ, if P RE ACCEPTED(P, γ) and P RE ACCEPTED(R, τ)
then P.tγ 6= R.tτ .
Proof. Let P and R be replicas that pre-accepted γ and τ respectively as described. Suppose for the sake of contradictionthat tγ = tτ . First, given Observation B.4 it must be that P 6= R. Then there are four cases to consider:
1. tγ = t0 γ and tτ = t0 τ . This means that t0 γ = t0 τ . However, this contradicts Observation B.2.

20

Draft Whitepaper for CEP-15: General Purpose Transactions

2. tγ = t0 γ but tτ 6= t0 τ . This means that R reassigned tτ during pre-accept. As a result, tτ .seq ≥ 1, while by Observation B.1 tγ .seq = 0.
3. tγ 6= t0 γ but tτ = t0 τ . This is symmetric to the above case.
4. tγ 6= t0 γ and tτ 6= t0 τ . This means that P and R reassigned the execution timestamp of γ and τ respectively during
pre-accept. Moreover, tγ = tτ implies tγ .id = tτ .id. But this means that P = R, which is a contradiction.
Corollary B.1.1. No two interfering commands commit with the same execution timestamp.
Proof. Suppose for the sake of contradiction that γ and τ are interfering transactions that committed with the same
execution timestamp. Then there must be some replica that pre-accepted γ and some replica that pre-accepted τ withthat execution timestamp. This contradicts Lemma B.1.
Lemma B.2. Let bsmallest be the smallest ballot number with which a transaction τ was committed at any replica. Then
any other commits for τ with any ballot number b ≥ bsmallest must be of the same execution timestamp.
Proof. Suppose τ is committed at a replica P with t0 τ , tτ , depsτ using ballot bsmallest . Proof by induction on ballot
number b.
Base case: b = bsmallest . By design, b belongs to a single coordinator C. This means C sent m = Commit(τ,t0 τ , tτ , depsτ )to P using ballot b. By Observation B.3, m is the only Commit message C sends to any replica using ballot b.
Inductive case: Consider some ballot number b1 ≥ bsmallest . Suppose that τ is committed using ballot number b1
with execution timestamp tτ . We now show that the next attempted ballot b2 > b1 will attempt τ with the same execution
timestamp.
Let b2 be the next highest ballot number than b1 attempted for τ. Note that b2 cannot be the default ballot for τ asthere is a ballot smaller than it. Hence b2 is attempted via the Recovery Phase, in which case there are two cases toconsider:1. τ committed via the fast-path using ballot b1 . Then τ must be pre-accepted at Fτ with t0 τ = tτ . Let C be thecoordinator running Recovery for τ using ballot b2 . If C observes from its RecoverOK responses that Committedτ
or Appliedτ then we are done given the induction hypothesis together with Observation B.3. Note that C will notobserve that Acceptedτ since τ was fast-path committed by ballot b1 , and by assumption there is no intermediate
ballot b0 where b1 < b0 < b2 such that a replica could have accepted τ with b0 . Hence, for all ρ, C must observe
no more than |E| −|F| replicas in E pre-accepted without t0 τ as their execution timestamps.
It remains to show that C evaluates the condition in line 35 to false. Suppose otherwise. This means that some
replica P either (a) accepted a conflicting transaction γ, such that τ 6∈ depsγ and t0 γ > t0 τ ; or (b) committed a
conflicting transaction γ such that τ 6∈ depsγ and tγ > t0 τ .
(a) Consider the former case where P accepted some conflicting transaction γ, such that τ 6∈ depsγ and t0 γ > t0 τ .
Since γ has been accepted at P, it must have been pre-accepted by a slow-path quorum Qγ . Moreover,by assumption τ has been pre-accepted by a fast-path quorum Fτ . As such, there must be some replica
P ∈ Qγ ∩ Fτ that pre-accepted both γ and τ. If P pre-accepted γ before τ, then τ could not have committed
via the fast-path since t0 γ > t0 τ . Otherwise, P pre-accepted τ before γ, in which case τ ∈ depsγ . Either way,
we arrive at a contradiction.
(b) Consider the latter case where P committed some conflicting transaction υ, such that τ 6∈ depsυ and tυ > t0 τ .
υ could not have committed via the fast-path as if tυ = t0 υ then P would have included τ in its response andso we would have τ ∈ depsυ . Hence, υ committed via the slow-path, and there is a quorum Qυ that accepted
υ. Moreover, by assumption τ has been pre-accepted by a fast-path quorum Fτ . As such, there must be some
replica R ∈ Qυ ∩ Fτ that both pre-accepted τ and accepted υ. If R accepted υ before pre-accepting τ, then τ
could not have committed via the fast-path since tυ > t0 τ . Otherwise, R pre-accepted τ before accepting υ,
in which case τ ∈ depsυ . Either way, we arrive at a contradiction.
2. τ committed via the slow-path using ballot b1 . This means that there is a slow-path quorum Qτ that acceptedτ using ballot b1 . Let C be the coordinator running Recovery for τ using ballot b2 . By quorum intersection, C
must observe a RecoverOK response from a replica in Qτ . By assumption there is no ballot intermediate ballotb1 < b0 < b2 such that a replica could have accepted τ with ballot b0 . Hence, by the induction hypothesis, C
21

Draft Whitepaper for CEP-15: General Purpose Transactions

observes that τ has been accepted with execution timestamp tτ using the largest ballot number b1 , and proceeds toattempt τ with the same execution timestamp. By Observation B.3, ballot b2 will only be used to attempt thisvalue.
Lemma B.3. If a transaction τ is committed at some replica, then for any interfering transaction γ committed at some
replica with a lower execution timestamp tγ < tτ , γ must be in depsτ .
Proof. Suppose Committedτ on some replica and Committedγ on some replica, where tγ < tτ . There are four cases toconsider:1. γ and τ both committed via the fast-path. Then γ must be pre-accepted at some fast-path quorum Fγ with t0 γ = tγ .
Likewise, τ must be pre-accepted at some fast-path quorum Fτ with t0 τ = tτ . Then for any replica P in Fγ ∩ Fτ , P
must have pre-accepted γ before pre-accepting τ, since otherwise P will not have pre-accepted γ with t0 γ = tγ < t0 τ .
As a result, by the PreAccept phase of the Consensus Protocol, γ ∈ depsτ .
2. γ committed via the fast-path, while τ committed via the slow-path. Then γ must be pre-accepted at some fast-path
quorum Fγ with tγ = t0 γ . Meanwhile, τ must be accepted at some slow-path quorum Qτ with tτ . Then for any
replica P in Fγ ∩ Qτ , P must have pre-accepted γ before accepting τ, since otherwise P will not have pre-accepted
γ with tγ = t0 γ < t0 τ . As a result, by the Accept phase of the Consensus Protocol, γ ∈ depsτ .
3. γ committed via the slow-path, while τ committed via the fast-path. Then γ must be pre-accepted at some slowpath quorum Qγ with each member voting for an execution timestamp t ≤ tγ . Meanwhile, τ must be pre-accepted
at some fast-path quorum Fτ with t0 τ = tτ . Then for any replica P in Qγ ∩ Fτ , P must have pre-accepted γ before
pre-accepting τ else P will not have pre-accepted γ with t ≤ tγ < tτ . As a result, by the PreAccept phase of theConsensus Protocol, γ ∈ depsτ .
4. γ and τ both committed via the slow-path. Then γ must be pre-accepted at some slow-path quorum Qγ , where
each replica in Qγ pre-accepted γ for some execution timestamp t ≤ tγ . Meanwhile, τ must be accepted at someslow-path quorum Qτ with tτ . Then for any replica P in Qγ ∩ Qτ , P must have pre-accepted γ before accepting τ,
since otherwise P will not have pre-accepted γ with t ≤ tγ < tτ . As a result, by the Accept phase of the ConsenssProtocol, γ ∈ depsτ .
Theorem B.2 (Execution consistency). For any two interfering transactions τ and γ, if both τ and γ are committed,
then τ and γ will be applied in the same order by every replica involved in both transactions.
Proof. Suppose Committedτ on some replica and Committedγ on some replica, where tγ < tτ . By Observation B.1
and Lemma B.2 every replica with Committedτ record the same tτ , and by Lemma B.3 γ ∈ depsτ . As a result, by the
Execution Protocol, any replica participating in γ that applies τ does so only after γ has been executed and applied.
B.2.2

Real-time order

Lemma B.4. Let τ and γ be interfering commands such that τ is proposed by a client only after γ is committed at some
replica. Then for any replicas P, R where P.Committedτ and R.Committedγ , tτ > tγ .
Proof. Suppose γ is committed at some replica before τ is proposed. By Observation B.1 and Lemma B.2, any replicathat commits γ must do so with the same low timestamp and execution timestamps, namely t0 γ and tγ . Then there are
two cases:
1. γ committed via the fast-path. Then γ must be pre-accepted by some fast-path quorum Fγ ⊃ Qγ and all R ∈ Fγ
must now have Tγ ≥ tγ .
2. γ committed via the slow-path. Then γ must be accepted by some slow-path quorum Qγ with R.Tγ ≥ tγ for all
R ∈ Qγ .
In any case, by the time τ is proposed, some members of Qγ would have recorded the accepted tγ and set Tγ ≥ tγ . Any
Qτ must intersect this Qγ at one or more correct replicas, each of which may therefore only accept t0 τ if it is greater thanTγ and otherwise will propose an alternative tτ > Tγ , ensuring that τ is committed with a higher execution timestamp
than tγ .
Theorem B.3 (Real-time order). For any two interfering transactions τ and γ where τ is submitted after γ is committed,
every replica will apply γ before τ.
22Draft Whitepaper for CEP-15: General Purpose Transactions

Proof. Let γ and τ be as described. Consider some replica P where Committedγ and Committedτ . Since γ was committed
before τ was proposed, we have tγ < tτ by Lemma B.4. Moreover, by Lemma B.3, we have γ ∈ depsτ . Hence, by the
Apply phase of the Execution Protocol, P applies γ before τ.

B.3

Durability

Theorem B.4 (Durability). Committed transactions stay committed, maintaining the original real-time order.
Proof. Consider any transaction τ that is committed by its coordinator. If Committedτ or Appliedτ at all replicas insome Qτ then τ is durably committed. Otherwise, suppose τ has been acknowledged to the client and the coordinatorcrashes before a quorum of replicas have been sent their Apply messages. There are two cases:
1. τ committed via the fast path. Any recovery coordinator C for τ must contact some Rτ . τ must be pre-accepted bysome fast-path quorum Fτ with its committed execution timestamp tτ , and therefore E for each ρ ∈ P must containat most |E| −|F| replicas where tτ > t0 τ , and so Rτ may not witness more than this. Moreover, C must observe/ andSuperseding = 0/ as by Lemma B.3 any υ ∈ Commits must contain τ ∈ depsυ which implies Commits = 0,any υ ∈ Accepts must be pre-accepted by some Qυ after τ else τ would have been rejected on the fast-path, so/ Hence C must attempt to commit τ with the same tτ .
τ ∈ depsυ and therefore Accepts = 0.
2. τ committed via the slow-path. Then for some slow-path quorum Qτ each member has Acceptedτ and thecommitted execution timestamp tτ . Any recovery coordinator for τ must contact at least one member of Qτ andhence resume committing τ with the same tτ .

B.4

Liveness

Given a partially synchronous network we may assume that messages eventually arrive at all correct processes,
and the protocol assumes there is always at least one Qτ consisting of correct processes for all τ. We additionallyassume that any faulty process that recovers eventually receives messages that were sent to it while it was faulty,that process clocks are loosely synchronised, and that processes join at most one shard, at most once. We finallyassume the existence of a separate reliable configuration service that broadcasts new configurations sequentiallyalong with their epochs to all correct processes and that processes start with an initial configuration e0 and initialise(Epoch, ReadyEpoch, ReadyElectorate, ReadyShard) ← (e0 , e0 , P ∈ E, P ∈ ρ) · ∀P.
Observation B.5. For any transaction τ, there are a finite number of transactions γ such that t0 γ < t0 τ
Proof. By the assumption of loosely synchronised clocks, eventually all new γ must be assigned t0 γ > t0 τ
Observation B.6. A transaction τ known to some correct process eventually commits on all correct replicas P ∈ ρ ∈ Pτtτ .
Proof. The PreAccept, Accept and Commit phases exchange a fixed number of messages that by assumption must
eventually be delivered, and execute a fixed number of synchronous steps on receipt of each message. Therefore acorrect initial coordinator eventually delivers a Commit message to all correct replicas.
If the initial coordinator is faulty, a weak failure detector nominates a coordinator C to invoke the Recovery Protocol
with a sufficiently high ballot, in which case one of the following must be true:
1. A fixed number of steps are taken before the Accept or Commit phase is invoked. By the above paragraph thiswill eventually commit.
2. C must wait for transactions with a lower t0 . This cannot create a circular dependency, by Observation B.5 this set
is finite and so by induction, these transactions may themselves be committed.

γ

Lemma B.5. A transaction τ where all γ ∈ depsτ with tγ < tτ have applied at all correct replicas P ∈ ρ ∈ (Pτtτ ∩ Ptτ )will itself execute and apply on all correct replicas P ∈ ρ ∈ Pτtτ .
Proof. τ commits by Observation B.6. The coordinator that commits τ invokes the Execution Protocol, issuing a Readto each partition. By Observation B.6 all of depsτ commit, and by assumption all γ ∈ depsτ where tγ < tτ have applied,so that a correct replica in each shard responds with ReadOK permitting the coordinator to submit Apply messages toall correct replicas P ∈ Pτtτ . By the same justification as for Read, these are applied at each recipient.
23

Draft Whitepaper for CEP-15: General Purpose Transactions

If the coordinator becomes faulty, a weak failure detector selects a recovery coordinator to invoke the Recovery
Protocol with a sufficiently high ballot. This coordinator must either witness an incomplete Apply from the prior attempt
and replicate it to all correct replicas, or else will commit τ and by the above paragraph apply it at all correct replicas
P ∈ ρ ∈ Pτtτ .
Observation B.7. A transaction τ with committed execution timestamp tτ does not apply at all P ∈ ρe where e < tτ .epochand ρe ∪ ρtτ 6= ρe
Proof. By assumptions replicas may participate in at most one shard at most once, so any replica that leaves a shard
may not rejoin. By the Execution Protocol only those members of ρtτ receive Apply, and by the Reconfiguration Protocol
τ is only propagated to members of ρg where g > tτ which by assumption cannot contain any P ∈ ρe where P ∈/ ρf ande < f ≤ g.
Lemma B.6. A transaction τ that applies at all correct replicas P ∈ ρ ∈ ρτtτ also applies at all correct replicas R ∈ ρ ∈ ρτewhere ReadyEpoch ≥ e ≥ tτ .epoch on all correct processes.
Proof. By assumption, for all shards ρ ∈ Pτ any replica in ρtτ ∩ ρe applies τ so we must only demonstrate that τ
also applies on P ∈ (ρe \ ρtτ ). Assume otherwise. By the Reconfiguration Protocol any P ∈ (ρe+1 \ ρe ) must wait
for ReadyShard before setting ReadyEpoch = e + 1, which may only happen once some Qe of JoinShard messages
has been received and all γ applied where Appliedγ on the sender. Since senders first commit and apply all γ where
PreAcceptedγ and tγ .epoch ≤ e, there must exist some Qe where each member has either ¬PreAcceptedγ or tτ .epoch > e.
Since senders set Epoch = e + 1 prior to this, by the Consensus Protocol any replica with ¬PreAcceptedτ must on
PreAccept now assign tτ .epoch > e. Therefore either τ has already been committed with tτ .epoch > e or any quorum
that may pre-accept τ must involve at least one node where tτ .epoch > e, so that τ must commit with tτ .epoch > e. This
contradicts our assumption and Observation B.7.
Lemma B.7. A transaction τ committed with depsτ , where ReadyEpoch ≥ tτ .epoch on all correct replicas, executes
and applies at all correct replicas P ∈ ρ ∈ Pτtτ
Proof. Let e = tτ .epoch. By the Execution Protocol, τ must wait for depsτ to commit, and for all γ ∈ depsτ wheretγ < tτ to apply before executing and applying in a fixed number of steps.
By Observation B.6 depsτ all commit. By Observation B.5, the transitive closure of deps where t < tτ may beordered by t to create a list where, by Lemma B.5 and Lemma B.6, any transaction in the list may execute and apply if
those that precede it have themselves applied. Therefore, the first non-applied transaction in the list may execute andapply at all correct replicas, and by induction this may continue until all transactions have applied.
Lemma B.8. A new configuration Con f ige applies, setting ReadyEpoch = e and ReadyElectoratee = true on all correct
processes, and ReadyShard = true on all correct replicas.
Proof. By assumption Con f ige arrives at each correct replica, and nodes start with a correctly initialised Con f ige0 .
Proof by induction.
Base case: By assumption all processes are correctly initialised with Con f ige0
Inductive case: By assumption, ReadyEpoch = e and ReadyElectoratee = true on all correct processes so that Lines
1 and 3 of the Reconfiguration Protocol complete. Correct members of the prior electorate therefore send JoinElectorate
to each new member, ReadyReconfiguree+1 = true will be set on every correct process, and ReadyElectoratee+1 set on
each correct process that is not newly a member of Ee+1 .
Given some Qe of correct replicas by definition |Ee ∩ Qe | ≥ 1 +|Ee | −|Fe | so that eventually 1 +|Ee | −|Fe |JoinElectorate messages must be received by correct replicas that are new to the electorate. As demonstrated ReadyReconfiguree+1
will be set by these processes so that L20 eventually completes and these JoinElectorate messages thereby collectively
set ReadyElectoratee+1 = true on each new member of Ee+1 , so that it is now eventually set on all correct processes.
By assumption ReadyShard is set for all replica P ∈ ρe , by Observation B.6 Line 15 of the Reconfiguration Protocol
completes, and by Lemma B.7 Line 16 completes, so that JoinShard messages are sent and ReadyEpoch = e + 1 is set
on these replicas.
Some Qe of correct replicas must therefore send JoinShard messages to all P ∈ ρe+1 \ ρe that by assumption are
eventually received by each correct replica. JoinShard messages contain only transactions that have been applied by24

Draft Whitepaper for CEP-15: General Purpose Transactions

the sender and their dependencies, so by definition each Apply on the recipient must succeed and terminate, so that
ReadyShard is eventually set on each replica that is new to ρe+1 . Therefore, by the prior paragraph, these replicas also
eventually set ReadyEpoch = e+1 and this eventually holds on all correct processes. By assumption ReadyShard = trueholds for all correct P ∈ ρe , therefore ReadyShard = true eventually holds on all correct P ∈ ρe+1 .
Theorem B.5. A transaction τ known to some correct replica or coordinator commits with some tτ and applies at all
correct replicas P ∈ ρ ∈ ρτe where e ≥ tτ .epoch.
Proof. By Observation B.6 τ eventually commits with some tτ . By the Consensus Protocol some process had
Epoch = tτ .epoch, so the reconfiguration service has sent this configuration and by Lemma B.8 all correct processes
set Epoch ≥ tτ . By Lemma B.7 τ applies at all correct replicas P ∈ ρ ∈ Pτtτ and by Lemma B.6 τ applies at all correct
replicas P ∈ ρ ∈ Pτe where e ≥ tτ .epoch.

25