betaFeedback

WorksComputer Science

A Deterministic Commitment Rule over Unstructured DAGs for Optimistic Replication

Abstract

In optimistic replication protocols, each replica uses the local state to execute requests from its clients in a wait-free manner, without synchronizing with other replicas. The outcomes may be revised later, making optimistic protocols only eventually consistent. To compensate for this consistency loss, an additional commitment mechanism can be employed: an underlying atomic broadcast protocol that allows replicas to periodically agree on the evolution of the object state. In this paper, we introduce a simple framework for optimistic replication based on a causality DAG: every replica represents the object state via a causally ordered set of client operations. The framework incorporates a deterministic commitment rule that incurs virtually zero message overhead beyond the basic dissemination of submitted operations.

2012 ACM Subject Classification Theory of computation →\to Distributed algorithms

Introduction

Optimistic replication. Distributed systems face a fundamental tradeoff between responsiveness and consistency. Strongly consistent protocols require replicas to coordinate before responding to client requests, which can significantly increase latency. Optimistic replication takes the opposite approach: replicas execute client operations immediately using their local state and perform synchronization in the background. As a result, clients obtain low-latency responses, while replicas gradually converge towards a common state [28].

The behavior of optimistic protocols is commonly captured through eventual consistency. Replicas may temporarily disagree on the order in which operations should be applied, causing local states to diverge. Nevertheless, after exchanging sufficient information, correct replicas eventually converge. In many applications, it is desirable to complement eventual consistency with a commitment mechanism that allows replicas to irrevocably determine a common ordering of operations. Such a mechanism enables strongly consistent operations, safe garbage collection, and reconfiguration.

Conflict-Free Replicated Data Type (CRDT) [30] protocols are among the most widely used optimistic replication techniques. CRDT protocols satisfy strong eventual consistency: whenever replicas observe the same set of operations, they reach the same state. Moreover, they tolerate an arbitrary number of failures and avoid the need for consensus during normal operation. However, CRDTs do not naturally provide a commitment mechanism.

Numerous CRDT implementations rely on causal broadcast [7, 2, 20] to disseminate operations. In particular, Baquero et al. [6] and Almeida [2] describe a generic framework based on a partially ordered log, where the replicated state is derived by locally interpreting a causally ordered set of operations. Following this approach, we view the causality relation between disseminated operations as a directed acyclic graph (DAG) and show that this structure can be leveraged not only to guarantee convergence but also to derive a deterministic commitment mechanism.

Deterministic commitment from the DAG. DAG-based protocols have recently attracted considerable attention due to their simplicity and high throughput. Most existing DAG-based solutions operate in the Byzantine setting and target blockchain applications, whereas we consider crash failures, the conventional failure model for optimistic replication systems. These blockchain solutions typically construct DAGs with layered structures by organizing vertices into asynchronous rounds [17, 10] and requiring replicas to collect sufficient information before issuing a new vertex. Commitment is obtained through additional mechanisms such as randomization [27, 5, 13] or waiting for designated leaders [18, 4].

Rather than constructing a layered DAG, we consider the causality DAG that naturally emerges from the exchange of replica messages in an optimistic replication protocol, similarly to the partially ordered logs used in CRDT systems. Since replicas do not wait for any particular message before issuing new vertices, the DAG remains unstructured. To ensure progress, replicas equip every disseminated message with the output of an eventual leader oracle Ω\Omega, which encapsulates the smallest amount of synchrony for establishing a total order on the inputs [9]. Therefore, the DAG captures not only causality relations between operations, but also information about the underlying system synchrony. Using this information, replicas can locally and deterministically derive a common total order whenever a majority of replicas remain correct and Ω\Omega eventually stabilizes on the same leader at all correct replicas. No rounds, randomization, or separate ordering protocol are required.

Contributions. To summarize, our contributions are threefold:

  • We show how the information produced by an eventual leader oracle can be embedded into a causality DAG, allowing replicas to derive deterministic commitment without rounds, randomization, or timeout-driven coordination.

  • We use the resulting framework to construct a generic replication protocol supporting both optimistic and strong consistency criteria.

  • We devise an efficient commitment mechanism that incurs virtually no communication overhead1 beyond the dissemination layer already used by many optimistic replication protocols.

Roadmap. The rest of the paper is organized as follows. We discuss related work in § 2. In § 3, we present our system model and specify the optimistic replication problem. We present the commitment framework and prove its correctness in § 4. We give our concluding remarks in § 5.

Related Work

Optimistic Replication. The idea of optimistic replication [28] is to prioritize availability over consistency. The local state of the shared data is represented by a set of submitted updates, and the clients’ operations are applied to the state without synchronizing with other replicas. Consistency is therefore only eventual: during periods in which no new updates are applied, replicas converge to the same state.

This approach has found numerous practical applications [33, 22, 32, 11], including many implementations of CRDTs [30]. In the optimistic setting, message causality has been used since early work to identify and resolve conflicts among concurrent operations [21, 26]. In the Pure Operation-Based CRDT framework introduced by Baquero et al. [6] and later advocated by Almeida [2], replicas maintain a partially ordered log of operations together with their causal dependencies. The state of the replicated object is obtained by locally interpreting this partially ordered structure according to the object semantics. However, operations are applied only optimistically, and replicas may never learn whether certain operations have become irreversible.

Mixed-consistency systems, by contrast, seek to provide stronger guarantees for selected critical operations, typically through a commitment mechanism that enables strongly consistent execution [14]. In previous approaches, however, adding a commitment mechanism on top of an optimistic service incurs significant costs: strongly consistent operations may lack fault tolerance [24], block progress [25], or require an external atomic broadcast protocol [19, 34], thereby increasing communication overhead. In contrast, our approach relies solely on the dissemination layer (causal broadcast), together with a lightweight leader oracle, to both commit operations and derive their optimistic ordering.

Closer to our work, Dubois et al. [12] present an eventual total-order broadcast protocol in which replicas maintain a DAG capturing causal dependencies, while the replica currently elected by Ω\Omega periodically disseminates a causality-preserving total order. The resulting order eventually stabilizes, but replicas cannot determine when this has occurred, since the stabilization time of Ω\Omega is unknown. In contrast, our commitment rule allows every replica to locally determine a committed prefix whose order is guaranteed to remain stable.

DAG-based protocols. DAG-based protocols have received significant attention in the design of high-throughput blockchain and state machine replication systems [5, 13, 17, 10, 31, 18, 3, 16]. A common design consists of organizing the DAG into asynchronous rounds [17], where replicas disseminate blocks and wait for a quorum of blocks before progressing. Earlier works also explored less structured DAG constructions [27, 5].

To derive commitment, prior protocols typically rely on mechanisms such as external leader election [10], common coins or randomized voting [13, 10, 18], timeout-based leader proposals [18, 4], or assumptions on randomized network schedulers [27, 16]. In contrast, commitment in our DAG is obtained solely by interpreting the DAG and information carried by the vertices. Information provided by the eventual leader oracle Ω\Omega is embedded directly into disseminated messages, allowing replicas to commit without waiting for quorum certificates, or executing an auxiliary leader-election or common-coin protocol.

System Model and Problem Statement

Processes, failures, and communication. The system is composed of a fixed set of processes (or replicas) Π\Pi, each of which is a sequential automaton assigned a deterministic algorithm. A distributed protocol is an array of algorithms A\mathcal{A}, one for each process. Processes communicate by exchanging messages. In each algorithm step ee, a single process receives an input (a message, an application call or a special null value λ\lambda), performs some local computation based on the input and its current state, transitions to a new state and produces an output (a set potentially including messages, an application response, and the null value λ\lambda). A run (or execution) e1e2…e_1e_2 \ldots is a sequence of algorithm steps (or events). We assume a crash failure model: processes may stop taking steps but always follow their assigned algorithm. In an infinite execution, a process is correct if it takes an infinite number of steps, and it is faulty otherwise. In every run, at least a majority of processes is correct.2

There is no upper bound on message delays. Each message sent in a run is unique and is received at most once. Moreover, if there is an event ee in which a process qq receives a message mm from a process pp, then there is an event e′e' preceding ee in which pp sends mm to qq.

Happens-before and causality. For a given execution, an event ee happens-before [23, 8] another event e′e' if any of the following conditions is satisfied:

  1. ee and e′e' occur at the same process pp, and pp executes step ee before e′e'.

  2. A message mm is sent in ee and received in e′e'.

  3. There exists an event e′′e'' such that ee happens-before e′′e'' and e′′e'' happens-before e′e'.

A message mm causally precedes another message m′m', written m⇝m′m \rightsquigarrow m', if the event in which mm is sent happens-before the event in which m′m' is sent. A pair of messages mm and m′m' is concurrent, denoted m∥m′m \parallel m', if neither mm causally precedes m′m' nor m′m' causally precedes mm.

Leader oracle. Each replica is equipped with a local eventual leader oracle Ω\Omega [9, 8], which it queries at every algorithm step to receive a replica id. In any infinite execution, the outputs produced by Ω\Omega satisfy:

  • (Eventual Accuracy) There is a step after which every query from a correct replica outputs the id of a correct replica.

  • (Eventual Agreement) There is a step after which every query from all correct replicas outputs the same replica id.

Communication Layer

We restrict our attention to a class of protocols combining two components: a communication component, where each replica builds an ever-growing directed acyclic graph [15] (DAG) induced by the causal relations among messages, and a local computation component that interprets the DAG to produce outputs. A message is a tuple (data,id,leader)(\mathrm{data}, \mathrm{id}, \mathrm{leader}), where data is some message content, id is the identifier of the replica sending the message, and leader is the output of Ω\Omega at the event in which the message is sent. For the communication component, every replica rir_i periodically (and forever) issues a new message mm, in which case rir_i sends mm to every other replica rjr_j. Upon receiving mm, rjr_j updates its local DAG by adding the new message as a vertex. Let GiG_i denote the DAG at replica rir_i and let past⁡i(v)\operatorname{past}_i(v) be the set of vertices ww such that there is a path from ww to vv in GiG_i. The construction satisfies the following properties in every infinite execution:

  • If a correct replica issues vv, then every correct replica rjr_j eventually adds vv to GjG_j.

  • If a replica rir_i adds a vertex vv to GiG_i, then vv was previously issued by replica v.idv.\mathrm{id}.

  • For every vertex v∈Giv \in G_i, w∈past⁡i(v)w \in\operatorname{past}_i(v) if w⇝vw \rightsquigarrow v.

  • If a correct replica rir_i adds vv to GiG_i, then every correct replica rjr_j eventually adds vv to GjG_j.

Optimistic Replication with Commitment

Each replica maintains a local DAG reflecting the causality order of the exchanged messages. Given the local DAG GiG_i of a replica rir_i, rir_i periodically turns its vertices into two sequences as outputs: the optimistic ordering uncommittedSiuncommittedS_i and the irrevocable prefix committedSicommittedS_i, defined as follows.

Optimistic ordering. Let HistiHist_i be the set of vertices in GiG_i. The optimistic sequence uncommittedSiuncommittedS_i is a permutation of HistiHist_i. As new elements are added to the history, the order of some messages in the optimistic sequence may be revised, although this ordering must satisfy a convergence property and be consistent with the causal ordering of the messages. Formally, an optimistic replication protocol must satisfy:

  • (Strong Eventual-Consistency) For any pair of replicas rir_i and rjr_j, if Histi=HistjHist_i = Hist_j, then uncommittedSi=uncommittedSjuncommittedS_i = uncommittedS_j.

  • (Causal-Consistency) For every replica rir_i and all mm and m′m' in HistiHist_i, if m⇝m′m \rightsquigarrow m', then mm precedes m′m' in uncommittedSiuncommittedS_i.

Committed prefix. On the other hand, the ordering of messages established in committedSicommittedS_i should be irrevocable and agreed upon by the replicas. Formally:

  • (Prefix Consistency) For any pair of replicas rir_i and rjr_j, committedSicommittedS_i is a prefix of committedSjcommittedS_j or vice-versa.

  • (Prefix Inclusion) For every replica rir_i, committedSicommittedS_i is a prefix of uncommittedSiuncommittedS_i.

  • (Prefix Progress) For every correct replica, if rir_i adds mm to HistiHist_i, then rir_i eventually includes mm in committedSicommittedS_i.

In § 4, we describe a method that uses properties of the induced graph to locally compute sequences satisfying the above properties.

Deterministic Commitment

This section presents a deterministic commitment mechanism that derives a total order directly from the DAG. The key idea is to leverage the information provided by the eventual leader oracle Ω\Omega, which is embedded in every vertex. During periods in which Ω\Omega stabilizes, replicas can identify portions of the DAG that have been observed by a majority of replicas and use them to deterministically extend a common prefix.

Commitment proceeds in two steps. First, replicas apply a DAG predicate to identify a consistent sequence of special vertices, called pre-committed vertices. They then use these vertices as reference points to order all vertices in their causal past according to a topological sorting ff.3

Intuitively, a vertex becomes pre-committed if it gathers support from “enough” vertices in its past and future.4 Each leader identifier (output by Ω\Omega) associated with a vertex vv counts as a vote for a vertex ww issued by rleaderr_{\mathrm{leader}}. If a majority of replicas vote for w.idw.id (the issuer of ww) in the causal region of ww, then ww becomes a leader vertex and is pre-committed.

As illustrated in Figure 1 to Figure 3, the causal region of w\mathbf{w} is composed of its immediate past5 previous(w\mathbf{w}) (the latest vertices from each replica seen by w\mathbf{w}), its immediate future next(w\mathbf{w}) (the earliest vertices from each replica to see w\mathbf{w}), and vertices “in between”.

Local DAG of a replica $r_i$

Figure 1. Local DAG of a replica rir_i. The DAG represents rir_i’s view at a fixed point in time, which might be incomplete. In this particular case, vc:3v_{c:3} is a leader vertex. The vertex gathers support within its causal region from all vertices issued by replicas bb, cc, and dd, thus obtaining support from a majority of replicas.

Local DAG with leader vertex $v_{c:4}$ and partial leader $v_{b:2}$

Figure 3. Local DAG with leader vertex vc:4v_{c:4}, where vb:2v_{b:2} is a partial leader in the past of vc:4v_{c:4}. The vertex vb:2v_{b:2} can still gather support from a majority of replicas, for instance through an unseen vertex from replica aa, so it is a partial leader from vc:4v_{c:4}’s perspective (when looking in the past of vc:4v_{c:4}).

A vertex in the past of a pre-committed vertex is also considered pre-committed if it could eventually gather sufficient support to become a leader. Such a vertex is referred to as a partial leader. This condition ensures that future pre-committed vertices cannot miss vertices that were previously committed, as shown in § 4.1.

Local DAG without a leader vertex

Figure 2. Local DAG without a leader vertex. The only difference from Figure 1 is the leader output of vd:2v_{d:2}. The vertex vc:3v_{c:3} does not gather sufficient support within its causal region, since vd:2v_{d:2} supports replica aa rather than replica cc.

DAG Predicate

We now describe the construction of a function V\mathcal{V} that extracts a sequence of pre-committed vertices V(Gi)\mathcal{V}(G_i) (or ViV_i for short) from a local DAG GiG_i. For all replicas rir_i and rjr_j and all execution steps, the construction should satisfy:

  1. Vi⪯VjV_i \preceq V_j or vice-versa.

  2. If GiG_i is a subgraph of GjG_j, then Vi⪯VjV_i \preceq V_j.

  3. Every vertex in GiG_i eventually appears in the past of some vertex appearing in ViV_i.

In the definitions and statements below, we consider a fixed point in time in an arbitrary run. We omit subscripts when there is no ambiguity, or when concepts apply to all graphs.

Preliminaries. For v∈G\mathbf{v} \in G, next(v)next(\mathbf{v}) denotes the set of vertices w∈G\mathbf{w} \in G such that w\mathbf{w} is the first vertex from w.id\mathbf{w}.\mathit{id} satisfying v⇝w\mathbf{v} \leadsto\mathbf{w}. Analogously, previous(v)previous(\mathbf{v}) denotes the set of vertices z∈G\mathbf{z} \in G such that z\mathbf{z} is the last vertex from z.id\mathbf{z}.\mathit{id} satisfying z⇝v\mathbf{z} \leadsto\mathbf{v}.

Let WW be a set of vertices and let rep(W)rep(W) be the set of replicas with at least one issued vertex appearing in WW. The set votes(ri,W)votes(r_i,W) is comprised of replicas rj∈rep(W)r_j \in rep(W) such that every vertex from rjr_j in WW has rir_i as the leader. A projection of WW over a set of replicas PP, written W∣PW|_P, is the set of vertices v∈W\mathbf{v} \in W such that v.id∈P\mathbf{v}.\mathit{id} \in P.

Now, we give the definition of the set of vertices current(v)current(\mathbf{v}). A vertex w\mathbf{w} belongs to current(v)current(\mathbf{v}) iff w.id∈rep(previous(v))\mathbf{w}.\mathit{id} \in rep(previous(\mathbf{v})) (there is a vertex from the issuer of w\mathbf{w} in previous(v)previous(\mathbf{v})) and one of the two following conditions is satisfied:

  1. w∈next(v)\mathbf{w} \in next(\mathbf{v}).

  2. ∄z∈next(v)\nexists\mathbf{z} \in next(\mathbf{v}) such that z.id=w.id\mathbf{z}.\mathit{id} = \mathbf{w}.\mathit{id}, and w\mathbf{w} is the last vertex issued by w.id\mathbf{w}.\mathit{id} in GG.

Let v,w∈G\mathbf{v},\mathbf{w} \in G be two vertices issued by the same replica rr. Then, trace(v,w)trace(\mathbf{v},\mathbf{w}) is the set comprised of all vertices from v\mathbf{v} to w\mathbf{w} (inclusive) that were issued by rr. If v.id≠w.id\mathbf{v}.\mathit{id} \ne\mathbf{w}.\mathit{id} or w⇝v\mathbf{w} \leadsto\mathbf{v} (w\mathbf{w} was issued before v\mathbf{v}), we define trace(v,w)≜∅trace(\mathbf{v},\mathbf{w}) \triangleq\emptyset. We say that trace(v,w)trace(\mathbf{v},\mathbf{w}) precedes trace(v′,w′)trace(\mathbf{v}',\mathbf{w}') if both are non-empty and w⇝v′\mathbf{w} \leadsto\mathbf{v}'.

The trace-closure of WW, written T(W)\mathcal{T}(W), is the smallest set containing all possible traces for pairs of vertices in WW, and is formally defined as:

T(W)≜⋃v,w∈Wtrace(v,w).\mathcal{T}(W) \triangleq\bigcup_{\mathbf{v},\mathbf{w}\in W} trace(\mathbf{v},\mathbf{w}).

We define the causal region of v\mathbf{v} as causal-region(v)≜T(previous(v)∪current(v))causal\text{-}region(\mathbf{v}) \triangleq\mathcal{T}(previous(\mathbf{v}) \cup current(\mathbf{v})). Consider the first vertex w\mathbf{w} and last vertex z\mathbf{z} issued by a replica rr in causal-region(v)causal\text{-}region(\mathbf{v}). Observe that causal-region(v)∣{r}=trace(w,z)causal\text{-}region(\mathbf{v})|_{\{r\}} = trace(\mathbf{w},\mathbf{z}), i.e., causal-region(v)∣{r}causal\text{-}region(\mathbf{v})|_{\{r\}} is the trace of rr in the causal region of v\mathbf{v}. In the following, a quorumquorum is a set with at least a majority of replicas.

Definition 1 (Leader). Let PP be a set of replicas and vv a vertex. We say that vv is a PP-leader if all the following requirements are satisfied:

  1. P⊆rep⁡(previous⁡(v))P \subseteq\operatorname{rep}(\operatorname{previous}(v)). There is a vertex in previous⁡(v)\operatorname{previous}(v) for every replica belonging to PP.

  2. P⊆rep⁡(next⁡(v))P \subseteq\operatorname{rep}(\operatorname{next}(v)). There is a vertex in next⁡(v)\operatorname{next}(v) for every replica belonging to PP.

  3. P \subseteq\operatorname{votes}(v.\operatorname{id},\operatorname{causal\mathchar`-region}(v)). All vertices in the causal region of vv (that were issued by replicas belonging to PP) vote for v.id⁡v.\operatorname{id}.

We say that vv is a leader vertex if there exists a quorum QQ such that vv is a QQ-leader.

Lemma 2. Let vv be a leader vertex in GiG_i and ww be a leader vertex in GjG_j such that v≠wv \ne w, then either v⇝wv \leadsto w or w⇝vw \leadsto v.

Proof. If v.id = w.id, then the result is immediate. Otherwise, let QQ be a quorum for which vv is a QQ-leader in GiG_i, and let Q′Q' be a quorum for which ww is a Q′Q'-leader in GjG_j. Take r∈Q∩Q′r \in Q \cap Q'. By definition of a leader, there exist zprev∈previous⁡(v)\mathbf{z}_{\mathrm{prev}} \in\operatorname{previous}(v) and znext∈next⁡(v)\mathbf{z}_{\mathrm{next}} \in\operatorname{next}(v) issued by rr in GiG_i, but also zprev′∈previous⁡(w)\mathbf{z}'_{\mathrm{prev}} \in\operatorname{previous}(w) and znext′∈next⁡(w)\mathbf{z}'_{\mathrm{next}} \in\operatorname{next}(w) issued by rr in GjG_j. Observe that zprev⇝v⇝znext\mathbf{z}_{\mathrm{prev}} \leadsto v \leadsto\mathbf{z}_{\mathrm{next}} and zprev′⇝w⇝znext′\mathbf{z}'_{\mathrm{prev}} \leadsto w \leadsto\mathbf{z}'_{\mathrm{next}}. Since all vertices in \operatorname{causal\mathchar`-region}(v)|_{\{r\}} vote for v.id and all vertices in \operatorname{causal\mathchar`-region}(w)|_{\{r\}} vote for w.id, where v.id ≠\ne w.id, the two traces are disjoint. Because those vertices are issued by the same replica rr, either znext⇝zprev′\mathbf{z}_{\mathrm{next}} \leadsto\mathbf{z}'_{\mathrm{prev}} or znext′⇝zprev\mathbf{z}'_{\mathrm{next}} \leadsto\mathbf{z}_{\mathrm{prev}}, and the result follows from the previous observation.

Lemma 2 implies that if a vertex vv is a leader in graph GiG_i, then there is no vertex ww parallel to vv that is also a leader in any graph GjG_j.

A vertex v∈Gv \in G may contain an incomplete causal region for a quorum QQ voting for v.id, so that vv can potentially become a leader after adding vertices to GG. We capture this notion with the definition of partial leader.

Definition 3 (Partial Leader). A vertex v∈Gv \in G is a partial leader if there exists a quorum QQ such that both conditions hold:

  1. Q⊆rep⁡(previous⁡(v))Q \subseteq\operatorname{rep}(\operatorname{previous}(v)). There is a vertex in previous⁡(v)\operatorname{previous}(v) for every replica belonging to QQ.

  2. Q \subseteq\operatorname{votes}(v.\operatorname{id},\operatorname{causal\mathchar`-region}(v)). All vertices in the causal region of vv (that were issued by replicas belonging to QQ) vote for v.id.

If the conditions above hold, we say that vv is a partial leader for QQ. Note that a QQ-leader vertex is also a partial leader for QQ.

Lemma 4. If vv and ww are vertices such that v≠wv \ne w and both are partial leaders in the same graph GG, then either v⇝wv \leadsto w or w⇝vw \leadsto v.

Proof. The result trivially holds in the case with v.id = w.id. Otherwise, let QQ and Q′Q' be quorums for which vv and ww are partial leaders respectively. Take r∈Q∩Q′r \in Q \cap Q'. By definition, there exist zprev∈previous⁡(v)\mathbf{z}_{\mathrm{prev}} \in\operatorname{previous}(v) and zprev′∈previous⁡(w)\mathbf{z}'_{\mathrm{prev}} \in\operatorname{previous}(w) issued by rr. Also, let zlast\mathbf{z}_{\mathrm{last}} and zlast′\mathbf{z}'_{\mathrm{last}} be the last vertices issued by rr in \operatorname{causal\mathchar`-region}(v) and \operatorname{causal\mathchar`-region}(w) respectively. Since every vertex in trace⁡(zprev,zlast)\operatorname{trace}(\mathbf{z}_{\mathrm{prev}},\mathbf{z}_{\mathrm{last}}) (recall that \operatorname{causal\mathchar`-region}(v)|_{\{r\}} = \operatorname{trace}(\mathbf{z}_{\mathrm{prev}},\mathbf{z}_{\mathrm{last}})) votes for v.id and every vertex in trace⁡(zprev′,zlast′)\operatorname{trace}(\mathbf{z}'_{\mathrm{prev}},\mathbf{z}'_{\mathrm{last}}) votes for w.id, where v.id ≠\ne w.id, the two traces are disjoint and one must precede the other. Assume w.l.o.g. that trace⁡(zprev,zlast)\operatorname{trace}(\mathbf{z}_{\mathrm{prev}},\mathbf{z}_{\mathrm{last}}) precedes trace⁡(zprev′,zlast′)\operatorname{trace}(\mathbf{z}'_{\mathrm{prev}},\mathbf{z}'_{\mathrm{last}}) and suppose that w∥vw \parallel v. If zlast∈next⁡(v)\mathbf{z}_{\mathrm{last}} \in\operatorname{next}(v), then v⇝zlast⇝zprev′⇝wv \leadsto\mathbf{z}_{\mathrm{last}} \leadsto\mathbf{z}'_{\mathrm{prev}} \leadsto w, which contradicts the assumption that w∥vw \parallel v. On the other hand, if zlast∉next⁡(v)\mathbf{z}_{\mathrm{last}} \notin\operatorname{next}(v), then by the definitions of current⁡(v)\operatorname{current}(v) and trace closure, all vertices issued by rr after prev⁡(v)\operatorname{prev}(v) (including those within trace⁡(zprev′,zlast′)\operatorname{trace}(\mathbf{z}'_{\mathrm{prev}},\mathbf{z}'_{\mathrm{last}})) should belong to trace⁡(zprev,zlast)\operatorname{trace}(\mathbf{z}_{\mathrm{prev}},\mathbf{z}_{\mathrm{last}}). This contradicts the fact that trace⁡(zprev,zlast)\operatorname{trace}(\mathbf{z}_{\mathrm{prev}},\mathbf{z}_{\mathrm{last}}) and trace⁡(zprev′,zlast′)\operatorname{trace}(\mathbf{z}'_{\mathrm{prev}},\mathbf{z}'_{\mathrm{last}}) are disjoint.

From now on, we will write causal-regioni(v)causal\text{-}region_i(\mathbf{v}) (with the subscript ii) to denote the causal region of v\mathbf{v} according to a specific graph GiG_i.

Lemma 5. Let v\mathbf{v} be a leader in GiG_i. Then v\mathbf{v} is a partial leader in any GjG_j such that v∈Gj\mathbf{v} \in G_j.

Proof. Let QQ be a quorum for which v\mathbf{v} is a QQ-leader in GiG_i. Because Q⊆rep(next(v))Q \subseteq rep(next(\mathbf{v})), the set causal-regioni(v)∣Qcausal\text{-}region_i(\mathbf{v})|_Q contains the complete traces of every replica belonging to QQ, with every trace ending at a vertex in next(v)next(\mathbf{v}) (observe that all traces start from a vertex in previous(v)previous(\mathbf{v}) regardless of the graph). Moreover, all vertices in causal-regioni(v)∣Qcausal\text{-}region_i(\mathbf{v})|_Q vote for v\mathbf{v}.id. Take any replica r∈Qr \in Q. For any other graph GjG_j containing v\mathbf{v}, the trace of rr in causal-regionj(v)causal\text{-}region_j(\mathbf{v}) is either incomplete or it ends at next(v)∣{r}next(\mathbf{v})|_{\{r\}}. Therefore it is a subset of the trace in causal-regioni(v)causal\text{-}region_i(\mathbf{v}). Also, for all replicas in QQ, their traces vote for v\mathbf{v}.id. Thus v\mathbf{v} satisfies the conditions to be a partial leader.

Proposition 6. Consider two graphs GiG_i and GjG_j at replicas rir_i and rjr_j respectively. Let Gi⊆GjG_i \subseteq G_j. For every vertex v\mathbf{v} appearing in both graphs: causal-regioni(v)⊆causal-regionj(v)causal\text{-}region_i(\mathbf{v}) \subseteq causal\text{-}region_j(\mathbf{v}).

Proof. Because Gi⊆GjG_i \subseteq G_j, GjG_j contains every vertex (and edges) belonging to GiG_i. Moreover, from the properties of the communication component, past(w)past(\mathbf{w}) is the same for every vertex w\mathbf{w} appearing in both graphs. In particular, past(v)past(\mathbf{v}) is the same in GiG_i and GjG_j. Consider any replica rr with a vertex in causal-regioni(v)causal\text{-}region_i(\mathbf{v}). The trace of rr in causal-regioni(v)causal\text{-}region_i(\mathbf{v}) starts from previous(v)∣{r}previous(\mathbf{v})|_{\{r\}} and ends at a vertex zz. Let z′z' be the last vertex from rr in causal-regionj(v)causal\text{-}region_j(\mathbf{v}). It follows that either z=z′z = z' or z⇝z′z \leadsto z', thus causal-regioni(v)∣{r}⊆causal-regionj(v)∣{r}causal\text{-}region_i(\mathbf{v})|_{\{r\}} \subseteq causal\text{-}region_j(\mathbf{v})|_{\{r\}}. And since this holds for every such replica rr, causal-regioni(v)⊆causal-regionj(v)causal\text{-}region_i(\mathbf{v}) \subseteq causal\text{-}region_j(\mathbf{v}).

Lemma 7. Consider two graphs GiG_i and GjG_j at replicas rir_i and rjr_j respectively, such that Gi⊆GjG_i \subseteq G_j. Let v\mathbf{v} be a vertex that appears in both GiG_i and GjG_j. If v\mathbf{v} is a partial leader in GjG_j, then it is also a partial leader in GiG_i.

Proof. Let QQ be a quorum for which v\mathbf{v} is a partial leader in GjG_j. Observe that whenever a graph contains v\mathbf{v}, it holds that Q⊆rep(previous(v))Q \subseteq rep(previous(\mathbf{v})). Since GiG_i is a subgraph of GjG_j, causal-regioni(v)∣Q⊆causal-regionj(v)∣Qcausal\text{-}region_i(\mathbf{v})|_Q \subseteq causal\text{-}region_j(\mathbf{v})|_Q (by Proposition 6). Moreover, because v\mathbf{v} is a partial leader in GjG_j, all vertices in causal-regionj(v)∣Qcausal\text{-}region_j(\mathbf{v})|_Q vote for v\mathbf{v}.id. Therefore, all vertices in causal-regioni(v)∣Qcausal\text{-}region_i(\mathbf{v})|_Q also vote for v\mathbf{v}.id, which implies that v\mathbf{v} is a partial leader in GiG_i.

Let VV be a set of vertices, the projection of GG onto VV, denoted G∣VG|_V, is the induced subgraph6 of GG containing only the vertices belonging to VV. We define graph(v)≜G∣past(v)∪{v}graph(\mathbf{v}) \triangleq G|_{past(\mathbf{v}) \cup\{\mathbf{v}\}}.7

Definition 8 (Pre-Committed Set). Let is_leader(v)is\_leader(\mathbf{v}) be the predicate: v\mathbf{v} is a leader vertex in GG. Also, let is_partial(v,w)is\_partial(\mathbf{v}, \mathbf{w}) be the predicate: v\mathbf{v} is a partial leader in graph(w)graph(\mathbf{w}). The set CC of pre-committed vertices of GG is built according to Algorithm 1. The algorithm computes CC by applying the following rules:

  1. Add every leader vertex v\mathbf{v} to CC.

  2. Recursively add v\mathbf{v} to CC such that is_partial(v,w)is\_partial(\mathbf{v}, \mathbf{w}) holds for any w∈C\mathbf{w} \in C.

Algorithm 1  Code for replica r - Computation of pre-committed set.

1: operation get_pre_committed(G)
2:     oldC ← ∅
3:     newC ← {v | is_leader(v)}
4:     while oldC ≠ newC do
5:         oldC ← newC
6:         newC ← {v | ∃w ∈ oldC : is_partial(v, w)}
7:         newC ← newC ∪ oldC
8:     end while
9:     return newC

Lemma 9. Suppose that is_leader(v)is\_leader(v) hold in GiG_i for some vertex vv and is_leader(w)is\_leader(w) hold in GjG_j for some vertex ww. Then either is_partial(w,v)is\_partial(w, v) holds in GiG_i or is_partial(v,w)is\_partial(v, w) holds in GjG_j.

Proof. Both vv and ww are leaders. Thus from Lemma 2, either v⇝wv \rightsquigarrow w or w⇝vw \rightsquigarrow v. Assume w.l.o.g. that w⇝vw \rightsquigarrow v. Then w∈past(v)w \in past(v) and by Lemma 5, ww is also a partial leader in graph(v)graph(v), meaning is_partial(w,v)is\_partial(w, v) holds in GiG_i.

Lemma 10. The set CC of pre-committed vertices of a graph is totally ordered by ⇝\rightsquigarrow.

Proof. Consider a particular call of get_pre_committed(GG) from Algorithm 1. We split the call into rounds based on iterations of the while loop, where round 0 is the execution of line 3. Let newCknewC^k be the set newCnewC at the end of round kk (either lines 3 or 7). We show by induction on the number of rounds that newCknewC^k is totally ordered by ⇝\rightsquigarrow.

At the end of round 0, newC0newC^0 is entirely comprised of leader vertices. Thus, by Lemma 2, newC0newC^0 is totally ordered by ⇝\rightsquigarrow.

Assume that by the end of round nn, newCnnewC^n is totally ordered by ⇝\rightsquigarrow. Suppose that there exist v,w∈newCn+1v, w \in newC^{n+1} such that v∥wv \mathbin{\|} w. There are two cases to consider: either (1) (w.l.o.g.) vv was first added to newCnewC in round n+1n+1 and ww was added to newCnewC in an older round, or (2) both vv and ww were added to newCnewC in round n+1n+1. We address each case in the following.

Case (1). vv was added to newCnewC in round n+1n+1 and ww was added in a previous round. Let wkw^k be a vertex satisfying:

  1. wk∥vw^k \mathbin{\|} v.

  2. wkw^k was added to newCnewC in round kk (k<n+1k < n + 1).

  3. kk is the smallest round in which there exists a vertex w′w' , added to newCnewC in round kk, such that w′∥vw' \mathbin{\|} v.

Since vv was added to newCnewC in round n+1n+1, by construction of Algorithm 1, there exists a vertex vnv^n (first added in round nn) for which is_partial(v,vn)is\_partial(v, v^n) holds, and vnv^n was used in line 6 to add vv to newCnewC. We say that vv was added to newCnewC from the past of vnv^n. It follows that v⇝vnv \rightsquigarrow v^n and that vv is a partial leader in graph(vn)graph(v^n).

Because both vnv^n and wkw^k belong to newCnnewC^n, by the induction hypothesis, either vn⇝wkv^n \rightsquigarrow w^k or wk⇝vnw^k \rightsquigarrow v^n. If vn⇝wkv^n \rightsquigarrow w^k, then v⇝wkv \rightsquigarrow w^k, contradicting the assumption that v∥wkv \mathbin{\|} w^k. So it must be that wk⇝vnw^k \rightsquigarrow v^n. But vv is a partial leader in graph(vn)graph(v^n), so by Lemma 4, wkw^k cannot be a partial leader in graph(vn)graph(v^n) while being parallel to vv. This in turn implies (by Lemma 5) that wkw^k is not a leader vertex.

Since wkw^{k} is not a leader, it was added to newCnewC from the past of another vertex wk−1w^{k-1}, which was added in round k−1k-1 (observe that wkw^{k} is a partial leader in graph(wk−1)graph(w^{k-1})). By the inductive hypothesis (newCnnewC^{n} is totally ordered by ⇝\rightsquigarrow), either vn⇝wk−1v^{n} \rightsquigarrow w^{k-1} or vice-versa. If vn⇝wk−1v^{n} \rightsquigarrow w^{k-1}, then graph(vn)⊆graph(wk−1)graph(v^{n}) \subseteq graph(w^{k-1}). Because wkw^{k} is a partial leader in graph(wk−1)graph(w^{k-1}), that would imply (by Lemma 7) that wkw^{k} is also a partial leader in graph(vn)graph(v^{n}), contradicting the fact that it isn’t. So it must be that wk−1⇝vnw^{k-1} \rightsquigarrow v^{n} and that graph(wk−1)⊆graph(vn)graph(w^{k-1}) \subseteq graph(v^{n}).

Now, both wk−1w^{k-1} and vv belong to graph(vn)graph(v^{n}), and wk−1w^{k-1} cannot be parallel to vv (kk is the smallest round in which a vertex parallel to vv exists). If wk−1⇝vw^{k-1} \rightsquigarrow v, then wk⇝vw^{k} \rightsquigarrow v, contradicting the assumption that wk∥vw^{k} \parallel v. Let v⇝wk−1v \rightsquigarrow w^{k-1}. Because vv is a partial leader in graph(vn)graph(v^{n}), by Lemma 7, it is also a partial leader in graph(wk−1)graph(w^{k-1}). Therefore, both wkw^{k} and vv are partial leaders in graph(wk−1)graph(w^{k-1}). By Lemma 4, either v⇝wkv \rightsquigarrow w^{k} or vice-versa, which contradicts the assumption that v∥wkv \parallel w^{k}.

We conclude that no such vertex wkw^{k} exists. Thus, for a round k<n+1k < n+1, there is no vertex w′w' added to newCnewC in round kk such that w′∥vw' \parallel v.

Case (2). Both vv and ww were added to newCnewC in round n+1n+1. Let vnv^{n} and wnw^{n} be the vertices used to add vv and ww to newCnewC respectively. Then, vnv^{n} and wnw^{n} were added in round nn, and vv is a partial leader in graph(vn)graph(v^{n}) (respectively, ww is a partial leader in graph(wn)graph(w^{n})). By the inductive hypothesis, either vn⇝wnv^{n} \rightsquigarrow w^{n} or wn⇝vnw^{n} \rightsquigarrow v^{n} (since newCnnewC^{n} is totally ordered by ⇝\rightsquigarrow). Suppose w.l.o.g. that vn⇝wnv^{n} \rightsquigarrow w^{n}. If vn⇝wv^{n} \rightsquigarrow w, then v⇝wv \rightsquigarrow w, contradicting the assumption that v∥wv \parallel w. On the other hand, graph(vn)⊆graph(wn)graph(v^{n}) \subseteq graph(w^{n}). So if w⇝vnw \rightsquigarrow v^{n}, Lemma 7 would imply that ww is a partial leader in graph(vn)graph(v^{n}) together with vv, contradicting Lemma 4. Therefore, vn∥wv^{n} \parallel w. This is exactly Case (1), which leads to a contradiction.

Conclusion. Assuming that there exist vv and ww in newCnewC such that v∥wv \parallel w at the end of round n+1n+1 leads to a contradiction in both cases (1) and (2). We conclude that newCn+1newC^{n+1} is totally ordered by ⇝\rightsquigarrow. Since the value returned by get_pre_committed(G)(G) is the final value of newCnewC, and newCnewC is totally ordered by ⇝\rightsquigarrow at the end of every round, the set of pre-committed vertices is totally ordered by ⇝\rightsquigarrow. ◀

Lemma 11. Let CiC_i and CjC_j be the sets of pre-committed vertices from GiG_i and GjG_j respectively. Then, Ci⊆Cj∨Cj⊆CiC_i \subseteq C_j \lor C_j \subseteq C_i.

Proof. If either CiC_i or CjC_j is empty, the result is immediate. Otherwise, let vv and ww be the last pre-committed vertices (with respect to ⇝\rightsquigarrow) in CiC_i and CjC_j respectively. Since CiC_i and CjC_j are both totally ordered by ⇝\rightsquigarrow (Lemma 10), vv and ww exist. Moreover, both must be leaders in their respective graphs by construction. Thus, either v⇝wv \rightsquigarrow w or w⇝vw \rightsquigarrow v. Assume w.l.o.g. that v⇝wv \rightsquigarrow w and suppose that there is a vertex v′∈Civ' \in C_i satisfying: v′v' is the last vertex in CiC_i (according to ⇝\rightsquigarrow) such that v′∉Cjv' \notin C_j.

By Lemma 5, if v′v' is a leader in GiG_i, then it is a partial leader in graph(w)graph(w). Thus is_partial(v′,w)is\_partial(v', w) holds and v′v' should have been added to CjC_j in the first while loop iteration of Algorithm 1 (line 6). If v′v' is not a leader in GiG_i, then there is v′′∈Civ'' \in C_i for which is_partial(v′,v′′)is\_partial(v', v'') holds, and v′v' was added to CiC_i at line 6 by using v′′v''. But v′v' is the last vertex in CiC_i that does not belong to CjC_j, so CjC_j. Consider the iteration in which v′′v'' was added to CjC_j. Then, in the following iteration, is_partial(v′,v′′)is\_partial(v', v'') is true and v′v' is added to CjC_j.

We conclude that there is no such vertex v′v'. Therefore, Ci⊆CjC_i \subseteq C_j. ◀

Now, we define Vi\mathcal{V}_i as the permutation of CiC_i such that vv precedes ww in Vi\mathcal{V}_i iff v⇝wv \rightsquigarrow w.

Theorem 12. For all Vi\mathcal{V}_i and Vj\mathcal{V}_j it holds that Vi⪯Vj∨Vj⪯Vi\mathcal{V}_i \preceq\mathcal{V}_j \lor\mathcal{V}_j \preceq\mathcal{V}_i.

Proof. If any of Vi\mathcal{V}_i or Vj\mathcal{V}_j is an empty sequence, then the result is immediate. Otherwise, let Ci\mathcal{C}_i and Cj\mathcal{C}_j be the set of pre-committed vertices of GiG_i and GjG_j respectively (Vi\mathcal{V}_i is a permutation of Ci\mathcal{C}_i and Vj\mathcal{V}_j is a permutation of Cj\mathcal{C}_j). By Lemma 11, either Ci⊆Cj\mathcal{C}_i \subseteq\mathcal{C}_j or vice-versa. Assume w.l.o.g. that Ci⊆Cj\mathcal{C}_i \subseteq\mathcal{C}_j. Observe that every vertex that appears in Vi\mathcal{V}_i also appears in Vj\mathcal{V}_j. Let v\mathbf{v} be the last vertex in Vi\mathcal{V}_i (by construction, v\mathbf{v} is a leader in GiG_i), and suppose that Vi⪯̸Vj\mathcal{V}_i \not\preceq\mathcal{V}_j. Then, there is a vertex in Vj\mathcal{V}_j that precedes v\mathbf{v} and it does not appear in Vi\mathcal{V}_i (nor in Ci\mathcal{C}_i). Let w\mathbf{w} be the last vertex appearing in Vj\mathcal{V}_j such that w⇝v\mathbf{w} \leadsto\mathbf{v} and w\mathbf{w} does not appear in Vi\mathcal{V}_i. If w\mathbf{w} is a leader vertex in GjG_j, then is_partial(w,v)\mathit{is\_partial}(\mathbf{w},\mathbf{v}) holds and w\mathbf{w} would have been added to Ci\mathcal{C}_i at line 6 of Algorithm 1. This means that w\mathbf{w} would appear in Vi\mathcal{V}_i, a contradiction. Otherwise, there exists a vertex w′∈Cj\mathbf{w}' \in\mathcal{C}_j for which is_partial(w,w′)\mathit{is\_partial}(\mathbf{w},\mathbf{w}') holds, and w′\mathbf{w}' was used in line 6 to add w\mathbf{w} to Cj\mathcal{C}_j. Since w\mathbf{w} is the last in Vj\mathcal{V}_j to satisfy w⇝v\mathbf{w} \leadsto\mathbf{v} and w∉Ci\mathbf{w} \notin\mathcal{C}_i, either v⇝w′\mathbf{v} \leadsto\mathbf{w}' or w′∈Ci\mathbf{w}' \in\mathcal{C}_i (both cannot be true at the same time, since v\mathbf{v} is the last vertex of Vi\mathcal{V}_i). We consider each case in the following.

If v⇝w′\mathbf{v} \leadsto\mathbf{w}', then graph(v)⊂graph(w′)\mathit{graph}(\mathbf{v}) \subset\mathit{graph}(\mathbf{w}'). It follows from Lemma 7 that w\mathbf{w} is a partial leader in graph(v)\mathit{graph}(\mathbf{v}), since it is a partial leader in graph(w′)\mathit{graph}(\mathbf{w}'). Therefore, w\mathbf{w} should have been added to Ci\mathcal{C}_i at line 6 of Algorithm 1 (is_partial(w,v)\mathit{is\_partial}(\mathbf{w},\mathbf{v}) is true), a contradiction. Now, let w′∈Ci\mathbf{w}' \in\mathcal{C}_i, and consider the iteration of the while loop (Algorithm 1) in which w′\mathbf{w}' was added to Ci\mathcal{C}_i. In the next iteration, is_partial(w,w′)\mathit{is\_partial}(\mathbf{w},\mathbf{w}') holds, and w\mathbf{w} should have been added to Ci\mathcal{C}_i, a contradiction.

We conclude that no such vertex w\mathbf{w} exists, therefore Vi⪯Vj\mathcal{V}_i \preceq\mathcal{V}_j.

Theorem 13. If GiG_i is a subgraph of GjG_j, then Vi⪯Vj\mathcal{V}_i \preceq\mathcal{V}_j.

Proof. If Vi\mathcal{V}_i is empty, then the result is immediate. Otherwise, let v\mathbf{v} be the last vertex appearing in Vi\mathcal{V}_i. By construction, v\mathbf{v} is a leader vertex in GiG_i, thus it is also a leader in GjG_j. So v∈Cj\mathbf{v} \in\mathcal{C}_j and v\mathbf{v} appears in Vj\mathcal{V}_j. Since the sequence Vi\mathcal{V}_i ends at v\mathbf{v}, and because Vi⪯Vj∨Vj⪯Vi\mathcal{V}_i \preceq\mathcal{V}_j \lor\mathcal{V}_j \preceq\mathcal{V}_i (Theorem 12), it follows that Vi⪯Vj\mathcal{V}_i \preceq\mathcal{V}_j.

The following liveness results hold in every infinite execution.

Theorem 14. If a correct replica rir_i issues a vertex v\mathbf{v}, then v\mathbf{v} eventually appears in the causal past of some vertex pre-committed by rir_i.

Proof. From the communication component, every correct replica eventually receives v\mathbf{v}, and correct replicas periodically issue new vertices. Also, if a correct replica adds a vertex w\mathbf{w} to its local DAG, then every correct replica eventually does so. There exists an event eΩe_{\Omega} after which all queries output by Ω\Omega at correct replicas return the same correct replica rjr_j (Eventual Accuracy and Eventual Agreement). As a consequence, every new vertex issued by a correct replica has rjr_j as a leader after eΩe_{\Omega}. Let eleadere_{\mathrm{leader}} be an event after eΩe_{\Omega} satisfying: the last vertex rjr_j received from each correct replica has rjr_j as its leader, and every subsequent vertex rjr_j receives from correct replicas also has rjr_j as its leader (note that such an event exists since replicas periodically issue new vertices). Now, let eve_{\mathbf{v}} be the event in which the last correct replica receives v\mathbf{v}, and let ee be the later of eleadere_{\mathrm{leader}} and eve_{\mathbf{v}}. After ee, rjr_j eventually issues a new vertex w\mathbf{w} for which v∈past(w)\mathbf{v} \in\mathit{past}(\mathbf{w}) and there is a quorum of replicas in previous(w)\mathit{previous}(\mathbf{w}) that vote for rjr_j. From the communication component, w\mathbf{w} is eventually received and included in the past of a newly issued vertex from every correct replica. Such vertices are then received by rir_i, which gathers enough support from causal-region(w)∣Q\mathit{causal\text{-}region}(\mathbf{w})|_Q to pre-commit w\mathbf{w}, where QQ is a quorum containing only correct replicas, and the result follows.

Computing the Optimistic and Committed Sequences

Algorithm 2 describes the functions used to compute uncommittedSuncommittedS (get_uncommitted) and committedScommittedS (get_committed). The algorithm repeatedly uses a topological sorting ff to produce a totally ordered sequence from an input graph.

In order to generate committedSicommittedS_i and uncommittedSiuncommittedS_i, rir_i calls get_committed(GiG_i) and get_uncommitted(GiG_i) respectively. The function get_committed iterates through vertices from ViV_i in order. At each iteration, the next pre-committed vertex v\mathbf{v} is used as a reference for sorting graph(v)graph(\mathbf{v}) with the topological sorting ff, but only the vertices in graph(v)graph(\mathbf{v}) that are not yet committed are sorted, and the result is concatenated with the previously generated sequence. The resulting sequence after iterating through all pre-committed vertices becomes the new committed sequence.

For get_uncommitted, on the other hand, only the uncommitted tail (vertices from GiG_i that are not yet committed) is sorted using ff, and the resulting sequence is concatenated with the committed prefix.

Algorithm 2 Code for replica rr - Computation of sequences.

1: operation get_committed(G)
2:     pre_committedV ← 𝒱(G)
3:     new_committedV ← ()
4:     for each v ∈ pre_committedV in sequence order do
5:         to_commitV ← present(v) − present(last(new_committedV))
6:         new_committedV ← new_committedV + f(G|to_commitV)
7:     end for
8:     return new_committedV
9: operation get_uncommitted(G)
10:    comV ← get_committed(G)
11:    uncTail ← G.V − {comV} ▷ {comV} is the set of elements belonging to comV.
12:    return comV + f(G|uncTail)
13: Helper functions:
14:    last(sequence): Returns the last element from sequence or ⊥ if sequence = ().
15:    present(v): Returns past(v) ∪ {v} or ∅ if v = ⊥.
16:    +: Concatenation of sequences.

Theorem 15. The sequences computed from get_committed satisfy Prefix Consistency, Prefix Inclusion and Prefix Progress.

Proof. The order on the reference vertices for commitment is defined by the function V\mathcal{V} (line 2), which, by Theorem 12, satisfies V(Gi)⪯V(Gj)∨V(Gj)⪯V(Gi)\mathcal{V}(G_i) \preceq\mathcal{V}(G_j) \lor\mathcal{V}(G_j) \preceq\mathcal{V}(G_i) for all GiG_i and GjG_j, implying Prefix Consistency. Prefix Inclusion is satisfied by construction (line 12). By Theorem 14, every vertex issued by a correct replica rir_i is eventually committed by rir_i. Thus, if a vertex v\mathbf{v} is received by rir_i, rir_i will eventually issue a vertex with v\mathbf{v} in its past and commit that vertex, which guarantees Prefix Progress. ◀

Theorem 16. The sequences computed from get_uncommitted satisfy Strong Eventual-Consistency and Causal-Consistency.

Proof. Strong Eventual-Consistency holds because every computation is deterministic within get_uncommitted. For Causal-Consistency, we must analyze both the committed and uncommitted sequences, since the former is a prefix of the latter (Theorem 15).

By construction, the ordering of committed vertices preceding a reference (pre-committed) vertex follows the topological sorting ff (line 6), which preserves the partial ordering of the graph. Also, for each new tail sequence that is committed, the vertices in the tail must either be parallel to the previous reference vertex, or come after it according to ⇝\rightsquigarrow. Therefore the committed sequence is consistent with the partial order determined by ⇝\rightsquigarrow. The uncommitted tail (sequence of vertices not yet committed) from line 11 is also ordered according to ff. Lastly, all vertices from the uncommitted tail are either parallel or come after the ones from the committed sequence, so the concatenation from line 12 is consistent with ⇝\rightsquigarrow and thus the algorithm satisfies Causal-Consistency.

Communication Complexity and Latency

Communication complexity. Given a DAG produced by the communication component, Algorithm 2 derives both the optimistic and committed sequences using only local computation, and therefore incurs no additional communication overhead. The communication complexity of the protocol is thus inherited from the underlying communication component, with the only additional cost arising from the implementation of the Ω\Omega oracle.

Commitment latency. We analyze the case of a stable leader replica, whose identifier is output by Ω\Omega at a majority of replicas for a sufficiently long period, as the commitment protocol cannot make progress otherwise. Consider a vertex v\mathbf{v} issued by a stable leader replica rr, whose past already contains support from a quorum of replicas. The vertex can be committed at any replica within two message delays: one for v\mathbf{v} to reach a quorum of replicas, and another for vertices from that quorum to reach all other replicas. This measure, however, does not account for the time between receiving v\mathbf{v} and issuing a subsequent vertex, which is application-dependent.

Conclusion

We presented a framework for optimistic replication based on causality DAGs. In our approach, replicas execute operations using locally available information while exchanging messages asynchronously to ensure convergence. By augmenting disseminated messages with the output of an eventual leader oracle, replicas are able to derive an efficient deterministic commitment directly from the causality DAG. The resulting mechanism requires virtually no communication overhead beyond the dissemination layer and does not rely on rounds, randomization, or a separate ordering protocol. The approach shows that causality DAGs, as well as PO-Logs, can serve as practical constructions for commitment in optimistically replicated systems.

References

  1. [1]Marcos K Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Stable leader election. In International Symposium on Distributed Computing, pages 108–122. Springer, 2001.DOI
  2. [2]Paulo Sérgio Almeida. Approaches to conflict-free replicated data types. ACM Computing Surveys, 57(2):1–36, 2024.DOI
  3. [3]Ignacio Amores-Sesar and Christian Cachin. We will dag you. In European Symposium on Research in Computer Security, pages 276–291. Springer, 2024.
  4. [4]Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. Mysticeti: Reaching the limits of latency with uncertified dags. arXiv preprint arXiv:2310.14821, 2023.arxiv.org/abs/2310.14821
  5. [5]Leemon Baird. The Swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance. Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep, 34:9–11, 2016.
  6. [6]Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker. Pure operation-based replicated data types. arXiv preprint arXiv:1710.04469, 2017.arxiv.org/abs/1710.04469
  7. [7]Sebastian Burckhardt, Alexey Gotsman, Hongseok Yang, and Marek Zawirski. Replicated data types: specification, verification, optimality. ACM SIGPLAN Notices, 49(1):271–284, 2014.
  8. [8]Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011.DOI
  9. [9]Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus. Journal of the ACM (JACM), 43(4):685–722, 1996.
  10. [10]George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and tusk: a dag-based mempool and efficient bft consensus. In Proceedings of the Seventeenth European Conference on Computer Systems, pages 34–50, 2022.arxiv.org/abs/2105.11827
  11. [11]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. In SOSP, pages 205–220, 2007.
  12. [12]Swan Dubois, Rachid Guerraoui, Petr Kuznetsov, Franck Petit, and Pierre Sens. The weakest failure detector for eventual consistency. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 375–384, 2015.
  13. [13]Adam Gagol, Damian Leśniak, Damian Straszak, and Michał Świętek. Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 214–228, 2019.
  14. [14]Rachid Guerraoui, Matej Pavlovic, and Dragos-Adrian Seredinschi. Incremental consistency guarantees for replicated objects. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 169–184, 2016.arxiv.org/abs/1609.02434
  15. [15]Gregory Z Gutin and Jørgen Bang-Jensen. Digraphs: Theory, Algorithms and Applications. Springer-Verlag London, 2009.
  16. [16]Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. Mihi-mahi: Low-latency asynchronous bft dag-based consensus. In 2025 IEEE 45th International Conference on Distributed Computing Systems (ICDCS), pages 549–559. IEEE, 2025.DOI
  17. [17]Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All you need is dag. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 165–175, 2021.arxiv.org/abs/2102.08325
  18. [18]Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. Cordial miners: Fast and efficient consensus for every eventuality. In 37th International Symposium on Distributed Computing, 2023.DOI
  19. [19]Maciej Kocociński, Tadeusz Kobus, and Paweł T Wojciechowski. On mixing eventual and strong consistency: acute cloud types. IEEE Transactions on Parallel and Distributed Systems, 33(6):1338–1356, 2021.
  20. [20]Petr Kuznetsov, Maxence Perion, and Sara Tucci-Piergiovanni. Wait-free Replicated Data Types and Fair Reconciliation. arXiv e-prints, page arXiv:2508.18193, August 2025. arXiv: 2508.18193, doi:10.48550/arXiv.2508.18193.arxiv.org/abs/2508.18193
  21. [21]Rivka Ladin, Barbara Liskov, Liuba Shrira, and Sanjay Ghemawat. Providing high availability using lazy replication. ACM Transactions on Computer Systems (TOCS), 10(4):360–391, 1992.DOI
  22. [22]Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Oper. Syst. Rev., 44(2):35–40, 2010.
  23. [23]Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications, 1978.
  24. [24]Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno Preguiça, and Rodrigo Rodrigues. Making {Geo-Replicated} systems fast as possible, consistent when necessary. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), pages 265–278, 2012.
  25. [25]Cheng Li, Nuno Preguiça, and Rodrigo Rodrigues. Fine-grained consistency for geo-replicated systems. In 2018 USENIX Annual Technical Conference (USENIX ATC 18), pages 359–372, 2018.
  26. [26]Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. Don’t settle for eventual: scalable causal consistency for wide-area storage with cops. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 401–416, 2011.
  27. [27]Louise E Moser and Peter M Melliar-Smith. Byzantine-resistant total ordering algorithms. Information and Computation, 150(1):75–111, 1999.DOI
  28. [28]Yasushi Saito and Marc Shapiro. Optimistic replication. ACM Computing Surveys (CSUR), 37(1):42–81, 2005.DOI
  29. [29]Nicolas Schiper and Sam Toueg. A robust and lightweight stable leader election service for dynamic systems. In 2008 IEEE International Conference on Dependable Systems and Networks With FTCS and DCC (DSN), pages 207–216. IEEE, 2008.DOI
  30. [30]Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free replicated data types. In Symposium on Self-Stabilizing Systems, pages 386–400. Springer, 2011.DOI
  31. [31]Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bull-shark: Dag bft protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 2705–2718, 2022.
  32. [32]Douglas B. Terry, Marvin Theimer, Karin Petersen, Alan J. Demers, Mike Spreitzer, and Carl Hauser. Managing update conflicts in bayou, a weakly connected replicated storage system. In SOSP, 1995.
  33. [33]Werner Vogels. Eventually consistent. Commun. ACM, 52(1):40–44, 2009.
  34. [34]Paweł T Wojciechowski, Maciej Kokociński, and Tadeusz Kobus. Creek: A single-order mixed-consistency replication scheme. Theoretical Computer Science, page 115927, 2026.DOI

Paper details

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

views · 0

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents