A Deterministic Commitment Rule over Unstructured DAGs for Optimistic Replication

A Deterministic Commitment Rule over Unstructured DAGs for Optimistic Replication João Paulo Bezerra # Université Paris-Saclay, CEA, LIST, Palaiseau, France

Petr Kuznetsov # Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France Léo Olivier # Université Paris-Saclay, CEA, LIST, Palaiseau, France

Sara Tucci-Piergiovanni #

arXiv:2610.41837v1 [cs.DC] 30 Oct 2026

Université Paris-Saclay, CEA, LIST, Palaiseau, France

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 consensus 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 Keywords and phrases Atomic Broadcast, DAG Protocols, CRDT, Optimistic Replication.

1

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

2

Deterministic Commitment over Unstructured DAGs

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 Section 2. In Section 3, we present our system model and specify the optimistic replication problem. We present the commitment framework and prove its correctness in Section 4. We give our concluding remarks in Section 5.

2

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

1

Efficient implementations of Ω can be realized with minimal communication overhead, requiring replicas to exchange only a few lightweight heartbeat messages [1, 29].

J. P. Bezerra, P. Kuznetsov, L. Olivier, S. Tucci-Piergiovanni

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.

3

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 A, one for each process. Processes communicate by exchanging messages. In each algorithm step e, 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

3

4

Deterministic Commitment over Unstructured DAGs

(or execution) e1 e2 . . . 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 e in which a process q receives a message m from a process p, then there is an event e′ preceding e in which p sends m to q. Happens-before and causality. For a given execution, an event e happens-before [23, 8] another event e′ if any of the following conditions is satisfied: 1. e and e′ occur at the same process p, and p executes step e before e′ . 2. A message m is sent in e and received in e′ . 3. There exists an event e′′ such that e happens-before e′′ and e′′ happens-before e′ . A message m causally precedes another message m′ , written m ⇝ m′ , if the event in which m is sent happens-before the event in which m′ is sent. A pair of messages m and m′ is concurrent, denoted m||m′ , if neither m causally precedes m′ nor m′ causally precedes m. 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.

3.1

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), 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 ri periodically (and forever) issues a new message m, in which case ri sends m to every other replica rj . Upon receiving m, rj updates its local DAG by adding the new message as a vertex. Let Gi denote the DAG at replica ri and let pasti (v) be the set of vertices w such that there is a path from w to v in Gi . The construction satisfies the following properties in every infinite execution: If a correct replica issues v, then every correct replica rj eventually adds v to Gj . If a replica ri adds a vertex v to Gi , then v was previously issued by replica v.id. For every vertex v ∈ Gi , w ∈ pasti (v) iff w ⇝ v. If a correct replica ri adds v to Gi , then every correct replica rj eventually adds v to Gj . 2

This assumption is only required for the commitment of messages, as it is not necessary for optimistic progress, which relies on the liveness of the underlying causal dissemination mechanism.

J. P. Bezerra, P. Kuznetsov, L. Olivier, S. Tucci-Piergiovanni

3.2

Optimistic Replication with Commitment

Each replica maintains a local DAG reflecting the causality order of the exchanged messages. Given the local DAG Gi of a replica ri , ri periodically turns its vertices into two sequences as outputs: the optimistic ordering uncommittedS i and the irrevocable prefix committedS i , defined as follows. Optimistic ordering. Let Hist i be the set of vertices in Gi . The optimistic sequence uncommittedS i is a permutation of Hist 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 ri and rj , if Hist i = Hist j , then uncommittedS i = uncommittedS j . (Causal-Consistency) For every replica ri and all m and m′ in Hist i , if m ⇝ m′ , then m precedes m′ in uncommittedS i . Committed prefix. On the other hand, the ordering of messages established in committedS i should be irrevocable and agreed upon by the replicas. Formally: (Prefix Consistency) For any pair of replicas ri and rj , committedS i is a prefix of committedS j or vice-versa. (Prefix Inclusion) For every replica ri , committedS i is a prefix of uncommittedS i . (Prefix Progress) For every correct replica, if ri adds m to Hist i , then ri eventually includes m in committedS i . In Section 4, we describe a method that uses properties of the induced graph to locally compute sequences satisfying the above properties.

4

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 f .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 v counts as a vote for a vertex w issued by rleader . If a majority of replicas vote for w.id (the issuer of w) in the causal region of w, then w becomes a leader vertex and is pre-committed.

3

A topological sorting f is a function that totally orders the vertices of a DAG, while preserving the partial order imposed by the edges. The reader may refer to [20] for a construction of such a function. 4 A vertex v is in the future of a vertex w if w ∈ past(v).

5

6

Deterministic Commitment over Unstructured DAGs

Replica a

a

a

a

a

a

va:1

va:2

va:3

va:4

va:5

Replica b

a

c

c

c

vb:1

vb:2

vb:3

vb:4

Leader

c

c

c

c

c

Replica c

vc:1

vc:2

vc:3

vc:4

vc:5

c

c

c

c

b

Replica d

vd:1

vd:2

vd:3

vd:4

vd:5

99K Causal order

Causal region of leader v

→ Same-process order

previous(v)

q

vp:n q

vp:n

Vertex n from process p, voting for q

next(v)

Leader or Partial Leader vertex

Set of vertices supporting v

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

As illustrated in Figures 1 to 3, the causal region of w is composed of its immediate past5 previous(w) (the latest vertices from each replica seen by w), its immediate future next(w) (the earliest vertices from each replica to see w), and vertices “in between”. 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 Section 4.1.

5

The precise definitions are given in Section 4.1.

Replica a

a

a

a

a

a

va:1

va:2

va:3

va:4

va:5

Replica b

a

c

c

c

vb:1

vb:2

vb:3

vb:4

c

c

c

c

c

Replica c

vc:1

vc:2

vc:3

vc:4

vc:5

c

a

c

c

b

Replica d

vd:1

vd:2

vd:3

vd:4

vd:5

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

J. P. Bezerra, P. Kuznetsov, L. Olivier, S. Tucci-Piergiovanni

7

b

Replica a

va:1 Partial leader b

b

b

c

c

Replica b

vb:1

vb:2

vb:3

vb:4

vb:5

b

b

c

c

c

vc:1

vc:2

vc:3

vc:4

vc:5

Replica c Replica d

Leader

c

c

vd:1

vd:2

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

4.1

DAG Predicate

We now describe the construction of a function V that extracts a sequence of pre-committed vertices V(Gi ) (or Vi for short) from a local DAG Gi . For all replicas ri and rj and all execution steps, the construction should satisfy: 1. Vi ⪯ Vj or vice-versa. 2. If Gi is a subgraph of Gj , then Vi ⪯ Vj . 3. Every vertex in Gi eventually appears in the past of some vertex appearing in Vi . 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, next(v) denotes the set of vertices w ∈ G such that w is the first vertex from w.id satisfying v ⇝ w. Analogously, previous(v) denotes the set of vertices z ∈ G such that z is the last vertex from z.id satisfying z ⇝ v. Let W be a set of vertices and let rep(W ) be the set of replicas with at least one issued vertex appearing in W . The set votes(ri , W ) is comprised of replicas rj ∈ rep(W ) such that every vertex from rj in W has ri as the leader. A projection of W over a set of replicas P , written W |P , is the set of vertices v ∈ W such that v.id ∈ P . Now, we give the definition of the set of vertices current(v). A vertex w belongs to current(v) iff w.id ∈ rep(previous(v)) (there is a vertex from the issuer of w in previous(v)) and one of the two following conditions is satisfied: 1. w ∈ next(v). 2. ̸ ∃z ∈ next(v) such that z.id = w.id, and w is the last vertex issued by w.id in G. Let v, w ∈ G be two vertices issued by the same replica r. Then, trace(v, w) is the set comprised of all vertices from v to w (inclusive) that were issued by r. If v.id = ̸ w.id or w ⇝ v (w was issued before v), we define trace(v, w) ≜ ∅. We say that trace(v, w) precedes trace(v′ , w′ ) if both are non-empty and w ⇝ v′ . The trace-closure of W , written T (W ), is the smallest set containing all possible traces S for pairs of vertices in W , and is formally defined as: T (W ) ≜ v,w∈W trace(v, w). We define the causal region of v as causal-region(v) ≜ T (previous(v) ∪ current(v)). Consider the first vertex w and last vertex z issued by a replica r in causal-region(v). Observe that causal-region(v)|{r} = trace(w, z), i.e., causal-region(v)|{r} is the trace of r in the causal region of v. In the following, a quorum is a set with at least a majority of replicas.

8

Deterministic Commitment over Unstructured DAGs

▶ Definition 1 (Leader). Let P be a set of replicas and v a vertex. We say that v is a P -leader if all the following requirements are satisfied: 1. P ⊆ rep(previous(v)). There is a vertex in previous(v) for every replica belonging to P . 2. P ⊆ rep(next(v)). There is a vertex in next(v) for every replica belonging to P . 3. P ⊆ votes(v.id, causal-region(v)). All vertices in the causal region of v (that were issued by replicas belonging to P ) vote for v.id. We say that v is a leader vertex if there exists a quorum Q such that v is a Q-leader. ̸ w, ▶ Lemma 2. Let v be a leader vertex in Gi and w be a leader vertex in Gj such that v = then either v ⇝ w or w ⇝ v. Proof. If v.id = w.id, then the result is immediate. Otherwise, let Q be a quorum for which v is a Q-leader in Gi , and let Q′ be a quorum for which w is a Q′ -leader in Gj . Take r ∈ Q ∩ Q′ . By definition of a leader, there exist zprev ∈ previous(v) and znext ∈ next(v) issued by r in Gi , but also z′prev ∈ previous(w) and z′next ∈ next(w) issued by r in Gj . Observe that zprev ⇝ v ⇝ znext and z′prev ⇝ w ⇝ z′next . Since all vertices in causal-region(v)|{r} vote for v.id and all vertices in causal-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 r, either znext ⇝ z′prev or z′next ⇝ zprev , and the result follows from the previous observation. ◀ Lemma 2 implies that if a vertex v is a leader in graph Gi , then there is no vertex w parallel to v that is also a leader in any graph Gj . A vertex v ∈ G may contain an incomplete causal region for a quorum Q voting for v.id, so that v can potentially become a leader after adding vertices to G. We capture this notion with the definition of partial leader. ▶ Definition 3 (Partial Leader). A vertex v ∈ G is a partial leader if there exists a quorum Q such that both conditions hold: 1. Q ⊆ rep(previous(v)). There is a vertex in previous(v) for every replica belonging to Q. 2. Q ⊆ votes(v.id, causal-region(v)). All vertices in the causal region of v (that were issued by replicas belonging to Q) vote for v.id. If the conditions above hold, we say that v is a partial leader for Q. Note that a Q-leader vertex is also a partial leader for Q. ▶ Lemma 4. If v and w are vertices such that v = ̸ w and both are partial leaders in the same graph G, then either v ⇝ w or w ⇝ v. Proof. The result trivially holds in the case with v.id = w.id. Otherwise, let Q and Q′ be quorums for which v and w are partial leaders respectively. Take r ∈ Q ∩ Q′ . By definition, there exist zprev ∈ previous(v) and z′prev ∈ previous(w) issued by r. Also, let zlast and z′last be the last vertices issued by r in causal-region(v) and causal-region(w) respectively. Since every vertex in trace(zprev , zlast ) (recall that causal-region(v)|{r} = trace(zprev , zlast )) votes for v.id and every vertex in trace(z′prev , z′last ) 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 trace(zprev , zlast ) precedes trace(z′prev , z′last ) and suppose that w||v. If zlast ∈ next(v), then v ⇝ zlast ⇝ z′prev ⇝ w, which contradicts the assumption that w||v. On the other hand, if zlast ̸∈ next(v), then by the definitions of current(v) and trace closure, all vertices issued by r after zprev (including those within trace(z′prev , z′last )) should belong to trace(zprev , zlast ). This contradicts the fact that trace(zprev , zlast ) and trace(z′prev , z′last ) are disjoint. ◀

J. P. Bezerra, P. Kuznetsov, L. Olivier, S. Tucci-Piergiovanni

From now on, we will write causal-regioni (v) (with the subscript i) to denote the causal region of v according to a specific graph Gi . ▶ Lemma 5. Let v be a leader in Gi . Then v is a partial leader in any Gj such that v ∈ Gj . Proof. Let Q be a quorum for which v is a Q-leader in Gi . Because Q ⊆ rep(next(v)), the set causal-regioni (v)|Q contains the complete traces of every replica belonging to Q, with every trace ending at a vertex in next(v) (observe that all traces start from a vertex in previous(v) regardless of the graph). Moreover, all vertices in causal-regioni (v)|Q vote for v.id. Take any replica r ∈ Q. For any other graph Gj containing v, the trace of r in causal-regionj (v) is either incomplete or it ends at next(v)|{r} . Therefore it is a subset of the trace in causal-regioni (v). Also, for all replicas in Q, their traces vote for v.id. Thus v satisfies the conditions to be a partial leader. ◀ ▶ Proposition 6. Consider two graphs Gi and Gj at replicas ri and rj respectively. Let Gi ⊆ Gj . For every vertex v appearing in both graphs: causal-regioni (v) ⊆ causal-regionj (v). Proof. Because Gi ⊆ Gj , Gj contains every vertex (and edges) belonging to Gi . Moreover, from the properties of the communication component, past(w) is the same for every vertex w appearing in both graphs. In particular, past(v) is the same in Gi and Gj . Consider any replica r with a vertex in causal-regioni (v). The trace of r in causal-regioni (v) starts from previous(v)|{r} and ends at a vertex z. Let z′ be the last vertex from r in causal-regionj (v). It follows that either z = z′ or z ⇝ z′ , thus causal-regioni (v)|{r} ⊆ causal-regionj (v)|{r} . And since this holds for every such replica r, causal-regioni (v) ⊆ causal-regionj (v). ◀ ▶ Lemma 7. Consider two graphs Gi and Gj at replicas ri and rj respectively, such that Gi ⊆ Gj . Let v be a vertex that appears in both Gi and Gj . If v is a partial leader in Gj , then it is also a partial leader in Gi . Proof. Let Q be a quorum for which v is a partial leader in Gj . Observe that whenever a graph contains v, it holds that Q ⊆ rep(previous(v)). Since Gi is a subgraph of Gj , causal-regioni (v)|Q ⊆ causal-regionj (v)|Q (by Proposition 6). Moreover, because v is a partial leader in Gj , all vertices in causal-regionj (v)|Q vote for v.id. Therefore, all vertices in causal-regioni (v)|Q also vote for v.id, which implies that v is a partial leader in Gi . ◀ Let V be a set of vertices, the projection of G onto V , denoted G|V , is the induced subgraph 6 of G containing only the vertices belonging to V . We define graph(v) ≜ G|past(v)∪{v} .7 ▶ Definition 8 (Pre-Committed Set). Let is_leader(v) be the predicate: v is a leader vertex in G. Also, let is_partial(v, w) be the predicate: v is a partial leader in graph(w). The set C of pre-committed vertices of G is built according to Algorithm 1. The algorithm computes C by applying the following rules: 1. Add every leader vertex v to C. 2. Recursively add v to C such that is_partial(v, w) holds for any w ∈ C.

6

A graph G is an induced subgraph of H if G ⊆ H and G contains all edges belonging to H such that both endpoints are vertices of G [15]. 7 Note that graphi (v) is the same for every graph Gi containing v.

9

10

Deterministic Commitment over Unstructured DAGs

Algorithm 1 Code for replica r - Computation of pre-committed set. 1: operation get_pre_committed(G) 2: 3: 4: 5: 6: 7: 8: 9:

oldC ← ∅ newC ← {v | is_leader(v)} while oldC ̸= newC do oldC ← newC newC ← {v | ∃w ∈ oldC : is_partial(v, w)} newC ← newC ∪ oldC end while return newC

▶ Lemma 9. Suppose that is_leader(v) hold in Gi for some vertex v and is_leader(w) hold in Gj for some vertex w. Then either is_partial(w, v) holds in Gi or is_partial(v, w) holds in Gj . Proof. Both v and w are leaders. Thus from Lemma 2, either v ⇝ w or w ⇝ v. Assume w.l.o.g. that w ⇝ v. Then w ∈ past(v) and by Lemma 5, w is also a partial leader in graph(v), meaning is_partial(w, v) holds in Gi . ◀ ▶ Lemma 10. The set C of pre-committed vertices of a graph is totally ordered by ⇝. Proof. Consider a particular call of get_pre_committed(G) 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 newC k be the set newC at the end of round k (either lines 3 or 7). We show by induction on the number of rounds that newC k is totally ordered by ⇝. At the end of round 0, newC 0 is entirely comprised of leader vertices. Thus, by Lemma 2, newC 0 is totally ordered by ⇝. Assume that by the end of round n, newC n is totally ordered by ⇝. Suppose that there exist v, w ∈ newC n+1 such that v||w. There are two cases to consider: either (1) (w.l.o.g.) v was first added to newC in round n + 1 and w was added to newC in an older round, or (2) both v and w were added to newC in round n + 1. We address each case in the following. Case (1). v was added to newC in round n + 1 and w was added in a previous round. Let wk be a vertex satisfying: 1. wk ||v. 2. wk was added to newC in round k (k < n + 1). 3. k is the smallest round in which there exists a vertex w′ , added to newC in round k, such that w′ ||v. Since v was added to newC in round n + 1, by construction of Algorithm 1, there exists a vertex vn (first added in round n) for which is_partial(v, vn ) holds, and vn was used in line 6 to add v to newC . We say that v was added to newC from the past of vn . It follows that v ⇝ vn and that v is a partial leader in graph(vn ). Because both vn and wk belong to newC n , by the induction hypothesis, either vn ⇝ wk or wk ⇝ vn . If vn ⇝ wk , then v ⇝ wk , contradicting the assumption that v||wk . So it must be that wk ⇝ vn . But v is a partial leader in graph(vn ), so by Lemma 4, wk cannot be a partial leader in graph(vn ) while being parallel to v. This in turn implies (by Lemma 5) that wk is not a leader vertex.

J. P. Bezerra, P. Kuznetsov, L. Olivier, S. Tucci-Piergiovanni

Since wk is not a leader, it was added to newC from the past of another vertex wk−1 , which was added in round k − 1 (observe that wk is a partial leader in graph(wk−1 )). By the inductive hypothesis (newC n is totally ordered by ⇝), either vn ⇝ wk−1 or vice-versa. If vn ⇝ wk−1 , then graph(vn ) ⊆ graph(wk−1 ). Because wk is a partial leader in graph(wk−1 ), that would imply (by Lemma 7) that wk is also a partial leader in graph(vn ), contradicting the fact that it isn’t. So it must be that wk−1 ⇝ vn and that graph(wk−1 ) ⊆ graph(vn ). Now, both wk−1 and v belong to graph(vn ), and wk−1 cannot be parallel to v (k is the smallest round in which a vertex parallel to v exists). If wk−1 ⇝ v, then wk ⇝ v, contradicting the assumption that wk ||v. Let v ⇝ wk−1 . Because v is a partial leader in graph(vn ), by Lemma 7, it is also a partial leader in graph(wk−1 ). Therefore, both wk and v are partial leaders in graph(wk−1 ). By Lemma 4, either v ⇝ wk or vice-versa, which contradicts the assumption that v||wk . We conclude that no such vertex wk exists. Thus, for a round k < n + 1, there is no vertex w′ added to newC in round k such that w′ ||v. Case (2). Both v and w were added to newC in round n + 1. Let vn and wn be the vertices used to add v and w to newC respectively. Then, vn and wn were added in round n, and v is a partial leader in graph(vn ) (respectively, w is a partial leader in graph(wn )). By the inductive hypothesis, either vn ⇝ wn or wn ⇝ vn (since newC n is totally ordered by ⇝). Suppose w.l.o.g. that vn ⇝ wn . If vn ⇝ w, then v ⇝ w, contradicting the assumption that v||w. On the other hand, graph(vn ) ⊆ graph(wn ). So if w ⇝ vn , Lemma 7 would imply that w is a partial leader in graph(vn ) together with v, contradicting Lemma 4. Therefore, vn ||w. This is exactly Case (1), which leads to a contradiction. Conclusion. Assuming that there exist v and w in newC such that v||w at the end of round n + 1 leads to a contradiction in both cases (1) and (2). We conclude that newC n+1 is totally ordered by ⇝. Since the value returned by get_pre_committed(G) is the final value of newC , and newC is totally ordered by ⇝ at the end of every round, the set of pre-committed vertices is totally ordered by ⇝. ◀ ▶ Lemma 11. Let Ci and Cj be the sets of pre-committed vertices from Gi and Gj respectively. Then, Ci ⊆ Cj ∨ Cj ⊆ Ci . Proof. If either Ci or Cj is empty, the result is immediate. Otherwise, let v and w be the last pre-committed vertices (with respect to ⇝) in Ci and Cj respectively. Since Ci and Cj are both totally ordered by ⇝ (Lemma 10), v and w exist. Moreover, both must be leaders in their respective graphs by construction. Thus, either v ⇝ w or w ⇝ v. Assume w.l.o.g. that v ⇝ w and suppose that there is a vertex v′ ∈ Ci satisfying: v′ is the last vertex in Ci (according to ⇝) such that v′ ̸∈ Cj . By Lemma 5, if v′ is a leader in Gi , then it is a partial leader in graph(w). Thus is_partial(v′ , w) holds and v′ should have been added to Cj in the first while loop iteration of Algorithm 1 (line 6). If v′ is not a leader in Gi , then there is v′′ ∈ Ci for which is_partial(v′ , v′′ ) holds, and v′ was added to Ci at line 6 by using v′′ . But v′ is the last vertex in Ci that does not belong to Cj , so v′′ ∈ Cj . Consider the iteration in which v′′ was added to Cj . Then, in the following iteration, is_partial(v′ , v′′ ) is true and v′ is added to Cj . We conclude that there is no such vertex v′ . Therefore, Ci ⊆ Cj . ◀ Now, we define Vi as the permutation of Ci such that v precedes w in Vi iff v ⇝ w. ▶ Theorem 12. For all Vi and Vj it holds that Vi ⪯ Vj ∨ Vj ⪯ Vi .

11

12

Deterministic Commitment over Unstructured DAGs

Proof. If any of Vi or Vj is an empty sequence, then the result is immediate. Otherwise, let Ci and Cj be the set of pre-committed vertices of Gi and Gj respectively (Vi is a permutation of Ci and Vj is a permutation of Cj ). By Lemma 11, either Ci ⊆ Cj or vice-versa. Assume w.l.o.g. that Ci ⊆ Cj . Observe that every vertex that appears in Vi also appears in Vj . Let v be the last vertex in Vi (by construction, v is a leader in Gi ), and suppose that Vi ̸⪯ Vj . Then, there is a vertex in Vj that precedes v and it does not appear in Vi (nor in Ci ). Let w be the last vertex appearing in Vj such that w ⇝ v and w does not appear in Vi . If w is a leader vertex in Gj , then is_partial(w, v) holds and w would have been added to Ci at line 6 of Algorithm 1. This means that w would appear in Vi , a contradiction. Otherwise, there exists a vertex w′ ∈ Cj for which is_partial(w, w′ ) holds, and w′ was used in line 6 to add w to Cj . Since w is the last in Vj to satisfy w ⇝ v and w ̸∈ Ci , either v ⇝ w′ or w′ ∈ Ci (both cannot be true at the same time, since v is the last vertex of Vi ). We consider each case in the following. If v ⇝ w′ , then graph(v) ⊆ graph(w′ ). It follows from Lemma 7 that w is a partial leader in graph(v), since it is a partial leader in graph(w′ ). Therefore, w should have been added to Ci at line 6 of Algorithm 1 (is_partial(w, v) is true), a contradiction. Now, let w′ ∈ Ci , and consider the iteration of the while loop (Algorithm 1) in which w′ was added to Ci . In the next iteration, is_partial(w, w′ ) holds, and w should have been added to Ci , a contradiction. We conclude that no such vertex w exists, therefore Vi ⪯ Vj . ◀ ▶ Theorem 13. If Gi is a subgraph of Gj , then Vi ⪯ Vj . Proof. If Vi is empty, then the result is immediate. Otherwise, let v be the last vertex appearing in Vi . By construction, v is a leader vertex in Gi , thus it is also a leader in Gj . So v ∈ Cj and v appears in Vj . Since the sequence Vi ends at v, and because Vi ⪯ Vj ∨ Vj ⪯ Vi (Theorem 12), it follows that Vi ⪯ Vj . ◀ The following liveness results hold in every infinite execution. ▶ Theorem 14. If a correct replica ri issues a vertex v, then v eventually appears in the causal past of some vertex pre-committed by ri . Proof. From the communication component, every correct replica eventually receives v, and correct replicas periodically issue new vertices. Also, if a correct replica adds a vertex w to its local DAG, then every correct replica eventually does so. There exists an event eΩ after which all queries output by Ω at correct replicas return the same correct replica rj (Eventual Accuracy and Eventual Agreement). As a consequence, every new vertex issued by a correct replica has rj as a leader after eΩ . Let eleader be an event after eΩ satisfying: the last vertex rj received from each correct replica has rj as its leader, and every subsequent vertex rj receives from correct replicas also has rj as its leader (note that such an event exists since replicas periodically issue new vertices). Now, let ev be the event in which the last correct replica receives v, and let e be the later of eleader and ev . After e, rj eventually issues a new vertex w for which v ∈ past(w) and there is a quorum of replicas in previous(w) that vote for rj . From the communication component, w is eventually received and included in the past of a newly issued vertex from every correct replica. Such vertices are then received by ri , which gathers enough support from causal-region(w)|Q to pre-commit w, where Q is a quorum containing only correct replicas, and the result follows. ◀

J. P. Bezerra, P. Kuznetsov, L. Olivier, S. Tucci-Piergiovanni

4.2

Computing the Optimistic and Committed Sequences

Algorithm 2 describes the functions used to compute uncommittedS (get_uncommitted) and committedS (get_committed). The algorithm repeatedly uses a topological sorting f to produce a totally ordered sequence from an input graph. In order to generate committedS i and uncommittedS i , ri calls get_committed(Gi ) and get_uncommitted(Gi ) respectively. The function get_committed iterates through vertices from Vi in order. At each iteration, the next pre-committed vertex v is used as a reference for sorting graph(v) with the topological sorting f , but only the vertices in graph(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 Gi that are not yet committed) is sorted using f , and the resulting sequence is concatenated with the committed prefix. Algorithm 2 Code for replica r - Computation of sequences. 1: operation get_committed(G) 2: 3: 4: 5: 6: 7: 8:

pre_committedV ← V(G) new_committedV ← () for each v ∈ pre_committedV in sequence order do to_commitV ← present(v) − present(last(new_committedV )) new_committedV ← new_committedV + f (G|to_commitV ) end for return new_committedV

9: operation get_uncommitted(G) 10: 11: 12:

comV ← get_committed(G) uncTail ← G.V − {comV } return comV + f (G|uncTail )

▷ {comV } is the set of elements belonging to comV .

13: Helper functions: 14: 15: 16:

last(sequence): Returns the last element from sequence or ⊥ if sequence = (). present(v): Returns past(v) ∪ {v} or ∅ if v =⊥. +: 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 (line 2), which, by Theorem 12, satisfies V(Gi ) ⪯ V(Gj ) ∨ V(Gj ) ⪯ V(Gi ) for all Gi and Gj , implying Prefix Consistency. Prefix Inclusion is satisfied by construction (line 12). By Theorem 14, every vertex issued by a correct replica ri is eventually committed by ri . Thus, if a vertex v is received by ri , ri will eventually issue a vertex with v in its past and commit that vertex, which guarantees Prefix Progress. ◀ ▶ Theorem 16. The sequences computed from get_uncommitted satisfy Strong EventualConsistency and Causal-Consistency.

13

14

Deterministic Commitment over Unstructured DAGs

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 f (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 f . 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. ◀

4.3

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 v issued by a stable leader replica r, 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 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 and issuing a subsequent vertex, which is application-dependent.

5

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

2

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. Paulo Sérgio Almeida. Approaches to conflict-free replicated data types. ACM Computing Surveys, 57(2):1–36, 2024.

J. P. Bezerra, P. Kuznetsov, L. Olivier, S. Tucci-Piergiovanni

3 4

5 6 7 8 9 10

11

12

13

14

15 16

17

18

19

20

21 22

Ignacio Amores-Sesar and Christian Cachin. We will dag you. In European Symposium on Research in Computer Security, pages 276–291. Springer, 2024. 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. 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. Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker. Pure operation-based replicated data types. arXiv preprint arXiv:1710.04469, 2017. Sebastian Burckhardt, Alexey Gotsman, Hongseok Yang, and Marek Zawirski. Replicated data types: specification, verification, optimality. ACM Sigplan Notices, 49(1):271–284, 2014. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011. 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. 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. 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. 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. Adam Gągol, 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. 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. Gregory Z Gutin and Jørgen Bang-Jensen. Digraphs: Theory, Algorithms and Applications. Springer-Verlag London, 2009. Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. Mahi-mahi: Low-latency asynchronous bft dag-based consensus. In 2025 IEEE 45th International Conference on Distributed Computing Systems (ICDCS), pages 549–559. IEEE, 2025. 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. 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. Maciej Kokociń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. 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. 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. Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Oper. Syst. Rev., 44(2):35–40, 2010.

15

16

Deterministic Commitment over Unstructured DAGs

23 24

25

26

27 28 29

30 31

32

33 34

Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications, 1978. 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. 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. 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. Louise E Moser and Peter M Melliar-Smith. Byzantine-resistant total ordering algorithms. Information and Computation, 150(1):75–111, 1999. Yasushi Saito and Marc Shapiro. Optimistic replication. ACM Computing Surveys (CSUR), 37(1):42–81, 2005. 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. 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. Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: Dag bft protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 2705–2718, 2022. 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. Werner Vogels. Eventually consistent. Commun. ACM, 52(1):40–44, 2009. Paweł T Wojciechowski, Maciej Kokociński, and Tadeusz Kobus. Creek: A single-order mixed-consistency replication scheme. Theoretical Computer Science, page 115927, 2026.

Related documents

• Replication without replicators#756153
• Two Holes Make a Difference: Deterministic Paging with Delay and Deadlines#1344264
• The complexity of reliable distributed storage#1407108
• State Without a Landlord: An Architecture Proposal for Peer-to-Peer Replication of Durable Workflow State#1011376
• State Without a Landlord: An Architecture Proposal for Peer-to-Peer Replication of Durable Workflow State#965395