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 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 , 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 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 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 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 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) , each of which is a sequential automaton assigned a deterministic algorithm. A distributed protocol is an array of algorithms , one for each process. Processes communicate by exchanging messages. In each algorithm step , a single process receives an input (a message, an application call or a special null value ), 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 ). A run (or execution) 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 in which a process receives a message from a process , then there is an event preceding in which sends to .
Happens-before and causality. For a given execution, an event happens-before [23, 8] another event if any of the following conditions is satisfied:
and occur at the same process , and executes step before .
A message is sent in and received in .
There exists an event such that happens-before and happens-before .
A message causally precedes another message , written , if the event in which is sent happens-before the event in which is sent. A pair of messages and is concurrent, denoted , if neither causally precedes nor causally precedes .
Leader oracle. Each replica is equipped with a local eventual leader oracle [9, 8], which it queries at every algorithm step to receive a replica id. In any infinite execution, the outputs produced by 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 , where data is some message content, id is the identifier of the replica sending the message, and leader is the output of at the event in which the message is sent. For the communication component, every replica periodically (and forever) issues a new message , in which case sends to every other replica . Upon receiving , updates its local DAG by adding the new message as a vertex. Let denote the DAG at replica and let be the set of vertices such that there is a path from to in . The construction satisfies the following properties in every infinite execution:
If a correct replica issues , then every correct replica eventually adds to .
If a replica adds a vertex to , then was previously issued by replica .
For every vertex , if .
If a correct replica adds to , then every correct replica eventually adds to .
Optimistic Replication with Commitment
Each replica maintains a local DAG reflecting the causality order of the exchanged messages. Given the local DAG of a replica , periodically turns its vertices into two sequences as outputs: the optimistic ordering and the irrevocable prefix , defined as follows.
Optimistic ordering. Let be the set of vertices in . The optimistic sequence is a permutation of . 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 and , if , then .
(Causal-Consistency) For every replica and all and in , if , then precedes in .
Committed prefix. On the other hand, the ordering of messages established in should be irrevocable and agreed upon by the replicas. Formally:
(Prefix Consistency) For any pair of replicas and , is a prefix of or vice-versa.
(Prefix Inclusion) For every replica , is a prefix of .
(Prefix Progress) For every correct replica, if adds to , then eventually includes in .
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 , which is embedded in every vertex. During periods in which 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 .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 ) associated with a vertex counts as a vote for a vertex issued by . If a majority of replicas vote for (the issuer of ) in the causal region of , then becomes a leader vertex and is pre-committed.
As illustrated in Figure 1 to Figure 3, the causal region of is composed of its immediate past5 previous() (the latest vertices from each replica seen by ), its immediate future next() (the earliest vertices from each replica to see ), and vertices “in between”.

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

Figure 3. Local DAG with leader vertex , where is a partial leader in the past of . The vertex can still gather support from a majority of replicas, for instance through an unseen vertex from replica , so it is a partial leader from ’s perspective (when looking in the past of ).
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.

Figure 2. Local DAG without a leader vertex. The only difference from Figure 1 is the leader output of . The vertex does not gather sufficient support within its causal region, since supports replica rather than replica .
DAG Predicate
We now describe the construction of a function that extracts a sequence of pre-committed vertices (or for short) from a local DAG . For all replicas and and all execution steps, the construction should satisfy:
or vice-versa.
If is a subgraph of , then .
Every vertex in eventually appears in the past of some vertex appearing in .
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 , denotes the set of vertices such that is the first vertex from satisfying . Analogously, denotes the set of vertices such that is the last vertex from satisfying .
Let be a set of vertices and let be the set of replicas with at least one issued vertex appearing in . The set is comprised of replicas such that every vertex from in has as the leader. A projection of over a set of replicas , written , is the set of vertices such that .
Now, we give the definition of the set of vertices . A vertex belongs to iff (there is a vertex from the issuer of in ) and one of the two following conditions is satisfied:
.
such that , and is the last vertex issued by in .
Let be two vertices issued by the same replica . Then, is the set comprised of all vertices from to (inclusive) that were issued by . If or ( was issued before ), we define . We say that precedes if both are non-empty and .
The trace-closure of , written , is the smallest set containing all possible traces for pairs of vertices in , and is formally defined as:
We define the causal region of as . Consider the first vertex and last vertex issued by a replica in . Observe that , i.e., is the trace of in the causal region of . In the following, a is a set with at least a majority of replicas.
Definition 1 (Leader). Let be a set of replicas and a vertex. We say that is a -leader if all the following requirements are satisfied:
. There is a vertex in for every replica belonging to .
. There is a vertex in for every replica belonging to .
P \subseteq\operatorname{votes}(v.\operatorname{id},\operatorname{causal\mathchar`-region}(v)). All vertices in the causal region of (that were issued by replicas belonging to ) vote for .
We say that is a leader vertex if there exists a quorum such that is a -leader.
Lemma 2. Let be a leader vertex in and be a leader vertex in such that , then either or .
Proof. If v.id = w.id, then the result is immediate. Otherwise, let be a quorum for which is a -leader in , and let be a quorum for which is a -leader in . Take . By definition of a leader, there exist and issued by in , but also and issued by in . Observe that and . 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 w.id, the two traces are disjoint. Because those vertices are issued by the same replica , either or , and the result follows from the previous observation.
Lemma 2 implies that if a vertex is a leader in graph , then there is no vertex parallel to that is also a leader in any graph .
A vertex may contain an incomplete causal region for a quorum voting for v.id, so that can potentially become a leader after adding vertices to . We capture this notion with the definition of partial leader.
Definition 3 (Partial Leader). A vertex is a partial leader if there exists a quorum such that both conditions hold:
. There is a vertex in for every replica belonging to .
Q \subseteq\operatorname{votes}(v.\operatorname{id},\operatorname{causal\mathchar`-region}(v)). All vertices in the causal region of (that were issued by replicas belonging to ) vote for v.id.
If the conditions above hold, we say that is a partial leader for . Note that a -leader vertex is also a partial leader for .
Lemma 4. If and are vertices such that and both are partial leaders in the same graph , then either or .
Proof. The result trivially holds in the case with v.id = w.id. Otherwise, let and be quorums for which and are partial leaders respectively. Take . By definition, there exist and issued by . Also, let and be the last vertices issued by in \operatorname{causal\mathchar`-region}(v) and \operatorname{causal\mathchar`-region}(w) respectively. Since every vertex in (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 votes for w.id, where v.id w.id, the two traces are disjoint and one must precede the other. Assume w.l.o.g. that precedes and suppose that . If , then , which contradicts the assumption that . On the other hand, if , then by the definitions of and trace closure, all vertices issued by after (including those within ) should belong to . This contradicts the fact that and are disjoint.
From now on, we will write (with the subscript ) to denote the causal region of according to a specific graph .
Lemma 5. Let be a leader in . Then is a partial leader in any such that .
Proof. Let be a quorum for which is a -leader in . Because , the set contains the complete traces of every replica belonging to , with every trace ending at a vertex in (observe that all traces start from a vertex in regardless of the graph). Moreover, all vertices in vote for .id. Take any replica . For any other graph containing , the trace of in is either incomplete or it ends at . Therefore it is a subset of the trace in . Also, for all replicas in , their traces vote for .id. Thus satisfies the conditions to be a partial leader.
Proposition 6. Consider two graphs and at replicas and respectively. Let . For every vertex appearing in both graphs: .
Proof. Because , contains every vertex (and edges) belonging to . Moreover, from the properties of the communication component, is the same for every vertex appearing in both graphs. In particular, is the same in and . Consider any replica with a vertex in . The trace of in starts from and ends at a vertex . Let be the last vertex from in . It follows that either or , thus . And since this holds for every such replica , .
Lemma 7. Consider two graphs and at replicas and respectively, such that . Let be a vertex that appears in both and . If is a partial leader in , then it is also a partial leader in .
Proof. Let be a quorum for which is a partial leader in . Observe that whenever a graph contains , it holds that . Since is a subgraph of , (by Proposition 6). Moreover, because is a partial leader in , all vertices in vote for .id. Therefore, all vertices in also vote for .id, which implies that is a partial leader in .
Let be a set of vertices, the projection of onto , denoted , is the induced subgraph6 of containing only the vertices belonging to . We define .7
Definition 8 (Pre-Committed Set). Let be the predicate: is a leader vertex in . Also, let be the predicate: is a partial leader in . The set of pre-committed vertices of is built according to Algorithm 1. The algorithm computes by applying the following rules:
Add every leader vertex to .
Recursively add to such that holds for any .
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 hold in for some vertex and hold in for some vertex . Then either holds in or holds in .
Proof. Both and are leaders. Thus from Lemma 2, either or . Assume w.l.o.g. that . Then and by Lemma 5, is also a partial leader in , meaning holds in .
Lemma 10. The set of pre-committed vertices of a graph is totally ordered by .
Proof. Consider a particular call of get_pre_committed() 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 be the set at the end of round (either lines 3 or 7). We show by induction on the number of rounds that is totally ordered by .
At the end of round 0, is entirely comprised of leader vertices. Thus, by Lemma 2, is totally ordered by .
Assume that by the end of round , is totally ordered by . Suppose that there exist such that . There are two cases to consider: either (1) (w.l.o.g.) was first added to in round and was added to in an older round, or (2) both and were added to in round . We address each case in the following.
Case (1). was added to in round and was added in a previous round. Let be a vertex satisfying:
.
was added to in round ().
is the smallest round in which there exists a vertex , added to in round , such that .
Since was added to in round , by construction of Algorithm 1, there exists a vertex (first added in round ) for which holds, and was used in line 6 to add to . We say that was added to from the past of . It follows that and that is a partial leader in .
Because both and belong to , by the induction hypothesis, either or . If , then , contradicting the assumption that . So it must be that . But is a partial leader in , so by Lemma 4, cannot be a partial leader in while being parallel to . This in turn implies (by Lemma 5) that is not a leader vertex.
Since is not a leader, it was added to from the past of another vertex , which was added in round (observe that is a partial leader in ). By the inductive hypothesis ( is totally ordered by ), either or vice-versa. If , then . Because is a partial leader in , that would imply (by Lemma 7) that is also a partial leader in , contradicting the fact that it isn’t. So it must be that and that .
Now, both and belong to , and cannot be parallel to ( is the smallest round in which a vertex parallel to exists). If , then , contradicting the assumption that . Let . Because is a partial leader in , by Lemma 7, it is also a partial leader in . Therefore, both and are partial leaders in . By Lemma 4, either or vice-versa, which contradicts the assumption that .
We conclude that no such vertex exists. Thus, for a round , there is no vertex added to in round such that .
Case (2). Both and were added to in round . Let and be the vertices used to add and to respectively. Then, and were added in round , and is a partial leader in (respectively, is a partial leader in ). By the inductive hypothesis, either or (since is totally ordered by ). Suppose w.l.o.g. that . If , then , contradicting the assumption that . On the other hand, . So if , Lemma 7 would imply that is a partial leader in together with , contradicting Lemma 4. Therefore, . This is exactly Case (1), which leads to a contradiction.
Conclusion. Assuming that there exist and in such that at the end of round leads to a contradiction in both cases (1) and (2). We conclude that is totally ordered by . Since the value returned by get_pre_committed is the final value of , and is totally ordered by at the end of every round, the set of pre-committed vertices is totally ordered by . ◀
Lemma 11. Let and be the sets of pre-committed vertices from and respectively. Then, .
Proof. If either or is empty, the result is immediate. Otherwise, let and be the last pre-committed vertices (with respect to ) in and respectively. Since and are both totally ordered by (Lemma 10), and exist. Moreover, both must be leaders in their respective graphs by construction. Thus, either or . Assume w.l.o.g. that and suppose that there is a vertex satisfying: is the last vertex in (according to ) such that .
By Lemma 5, if is a leader in , then it is a partial leader in . Thus holds and should have been added to in the first while loop iteration of Algorithm 1 (line 6). If is not a leader in , then there is for which holds, and was added to at line 6 by using . But is the last vertex in that does not belong to , so . Consider the iteration in which was added to . Then, in the following iteration, is true and is added to .
We conclude that there is no such vertex . Therefore, . ◀
Now, we define as the permutation of such that precedes in iff .
Theorem 12. For all and it holds that .
Proof. If any of or is an empty sequence, then the result is immediate. Otherwise, let and be the set of pre-committed vertices of and respectively ( is a permutation of and is a permutation of ). By Lemma 11, either or vice-versa. Assume w.l.o.g. that . Observe that every vertex that appears in also appears in . Let be the last vertex in (by construction, is a leader in ), and suppose that . Then, there is a vertex in that precedes and it does not appear in (nor in ). Let be the last vertex appearing in such that and does not appear in . If is a leader vertex in , then holds and would have been added to at line 6 of Algorithm 1. This means that would appear in , a contradiction. Otherwise, there exists a vertex for which holds, and was used in line 6 to add to . Since is the last in to satisfy and , either or (both cannot be true at the same time, since is the last vertex of ). We consider each case in the following.
If , then . It follows from Lemma 7 that is a partial leader in , since it is a partial leader in . Therefore, should have been added to at line 6 of Algorithm 1 ( is true), a contradiction. Now, let , and consider the iteration of the while loop (Algorithm 1) in which was added to . In the next iteration, holds, and should have been added to , a contradiction.
We conclude that no such vertex exists, therefore .
Theorem 13. If is a subgraph of , then .
Proof. If is empty, then the result is immediate. Otherwise, let be the last vertex appearing in . By construction, is a leader vertex in , thus it is also a leader in . So and appears in . Since the sequence ends at , and because (Theorem 12), it follows that .
The following liveness results hold in every infinite execution.
Theorem 14. If a correct replica issues a vertex , then eventually appears in the causal past of some vertex pre-committed by .
Proof. From the communication component, every correct replica eventually receives , and correct replicas periodically issue new vertices. Also, if a correct replica adds a vertex to its local DAG, then every correct replica eventually does so. There exists an event after which all queries output by at correct replicas return the same correct replica (Eventual Accuracy and Eventual Agreement). As a consequence, every new vertex issued by a correct replica has as a leader after . Let be an event after satisfying: the last vertex received from each correct replica has as its leader, and every subsequent vertex receives from correct replicas also has as its leader (note that such an event exists since replicas periodically issue new vertices). Now, let be the event in which the last correct replica receives , and let be the later of and . After , eventually issues a new vertex for which and there is a quorum of replicas in that vote for . From the communication component, is eventually received and included in the past of a newly issued vertex from every correct replica. Such vertices are then received by , which gathers enough support from to pre-commit , where 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 (get_uncommitted) and (get_committed). The algorithm repeatedly uses a topological sorting to produce a totally ordered sequence from an input graph.
In order to generate and , calls get_committed() and get_uncommitted() respectively. The function get_committed iterates through vertices from in order. At each iteration, the next pre-committed vertex is used as a reference for sorting with the topological sorting , but only the vertices in 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 that are not yet committed) is sorted using , and the resulting sequence is concatenated with the committed prefix.
Algorithm 2 Code for replica - 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 (line 2), which, by Theorem 12, satisfies for all and , implying Prefix Consistency. Prefix Inclusion is satisfied by construction (line 12). By Theorem 14, every vertex issued by a correct replica is eventually committed by . Thus, if a vertex is received by , will eventually issue a vertex with 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 (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 . Therefore the committed sequence is consistent with the partial order determined by . The uncommitted tail (sequence of vertices not yet committed) from line 11 is also ordered according to . 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 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 oracle.
Commitment latency. We analyze the case of a stable leader replica, whose identifier is output by at a majority of replicas for a sufficiently long period, as the commitment protocol cannot make progress otherwise. Consider a vertex issued by a stable leader replica , whose past already contains support from a quorum of replicas. The vertex can be committed at any replica within two message delays: one for 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 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]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]Paulo Sérgio Almeida. Approaches to conflict-free replicated data types. ACM Computing Surveys, 57(2):1–36, 2024.DOI
- [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]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]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]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]Sebastian Burckhardt, Alexey Gotsman, Hongseok Yang, and Marek Zawirski. Replicated data types: specification, verification, optimality. ACM SIGPLAN Notices, 49(1):271–284, 2014.
- [8]Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011.DOI
- [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]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]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]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]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]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]Gregory Z Gutin and Jørgen Bang-Jensen. Digraphs: Theory, Algorithms and Applications. Springer-Verlag London, 2009.
- [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]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]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]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]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]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]Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Oper. Syst. Rev., 44(2):35–40, 2010.
- [23]Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications, 1978.
- [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]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]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]Louise E Moser and Peter M Melliar-Smith. Byzantine-resistant total ordering algorithms. Information and Computation, 150(1):75–111, 1999.DOI
- [28]Yasushi Saito and Marc Shapiro. Optimistic replication. ACM Computing Surveys (CSUR), 37(1):42–81, 2005.DOI
- [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]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]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]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]Werner Vogels. Eventually consistent. Commun. ACM, 52(1):40–44, 2009.
- [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