Semantic Conflict Model for Collaborative Data Structures DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; April 27–30, 2026; Edinburgh, UK ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Human-centered computing Computer supported cooperative work CCS: Computing methodologies Distributed algorithms CCS: Information systems Remote replication Georgii Semenov, Vitaly Aksenov Abstract . Digital collaboration systems support asynchronous work over replicated data, where conflicts arise when concurrent operations cannot be unambiguously integrated into a shared history. While Conflict-Free Replicated Data Types (CRDTs) ensure convergence through built-in conflict resolution, this resolution is typically implicit and opaque to users, whereas existing reconciliation techniques often rely on centralized coordination. This paper introduces a conflict model for collaborative data structures that enables explicit, local-first conflict resolution without central coordination. The model identifies conflicts using semantic dependencies between operations and resolves them by rebasing conflicting operations onto a reconciling operation via a three-way merge over a replicated journal. We demonstrate our approach on collaborative registers, including an explicit formulation of the Last-Writer-Wins Register and a multi-register entity supporting semi-automatic reconciliation. 1. Introduction Digital collaboration environments provide a shared workspace that enables multiple users, teams, or organizations to work together toward a common goal ( 12 ) . Implementing highly available groupware systems, however, is challenging due to the need to tolerate network partitions and enable isolated work, as is common in version concurrency control systems. To address these challenges, users are allowed to collaborate asynchronously by producing optimistic transactions that are applied locally to their data replicas, and eventually propagated to other replicas ( 11 ) . This approach has been revisited as eventual state-machine replication ( 7 ) . The core part of such systems is the synchronization algorithm, which ensures convergence to a single state once all contributions have been integrated. During synchronization, conflicts arise when concurrent operations, i.e., that are not causally related, interfere with one another. This may be captured semantically, for example, as operations violating each other’s intents ( 4 ; 17 ) or as operations being non-commutative ( 21 ) . The common emergence of conflicts, however, is in the ambiguity of how operations should be integrated into a shared history. Crucially, the multi-dimensionality of this ambiguity elevates conflict resolution to a distinct collaborative subtask, concerned with coordinating and reconciling parallel commitments, a process referred to as articulation work ( 12 ) . One widely adopted approach to conflict resolution is exemplified by conflict-free replicated data types (CRDTs) ( 14 ) , which rely on semilattice structures or on the commutativity of operations. CRDTs provide strong eventual consistency through resolution strategies that are embedded directly into the data type definition, as captured in Add-Wins Sets and Last-Writer-Wins Registers ( 14 ) . Multi-Value Registers ( 14 ) take a different stance by retaining all concurrently written values and thereby deferring their resolution. Nevertheless, conflict resolution in CRDTs generally remains implicit, opaque to users, cannot be supervised, and is generally non-native to application-specific semantics. A second, more expressive class of approaches is based on reconciliation techniques ( 16 ) , which treat conflict resolution as an application-level procedure that integrates concurrent transactions in a semi-automatic manner. Typical strategies include computing an execution order that minimizes violated constraints ( 10 ) or maximizes the number of preserved operations ( 13 ) . These techniques usually rely on a centralized reconciliation phase with global knowledge of all operations, which makes them poorly suited to local-first ( 6 ) collaboration scenarios, where replicas must continue to make progress independently on local copies. This limitation motivates the need for reconciliation middleware that operates without a central coordinator, provides explicit convergence guarantees, and treats conflict resolution as a first-class collaborative activity, that is, as a form of articulation work. This paper presents a novel conflict model for collaborative data structures that enables local-first conflict resolution through the reconciliation of operations. Conflicts are identified using entails and discards dependencies, which relate each operation to its logical premises, and conflicting operations are rebased onto a new reconciling operation. We illustrate the model through several examples of collaborative registers and their formal definitions, including the Last-Writer-Wins Register as an instance of a CRDT with automated conflict resolution, and a calendar event as an example of a multi-register entity supporting complex operations. 2. System Model We consider a shared memory M which is modeled as a set of n pre-initialized registers. Each register M_{i} has its basis of actions A_{i} , which is formally a set of all allowed atomic operations on the register. We define an operation o=[a_{1},a_{2},\ldots,a_{k}] as a contiguous sequence of action instances a_{i}\in\bigcup^{n}A_{i} on the registers with the transactional semantics, i.e., executing an operation o is equivalent to a sequential uninterruptible execution of all its actions a_{1}\circ a_{2}\circ\ldots\circ a_{k} . The state s_{i}\in S_{i} of register M_{i} is deterministically produced by an interpreter \mathcal{I}_{i} after executing a sequence of actions on the initial empty context \perp . Equality of registers is inferred from the equality of their states, i.e., x=y\Leftrightarrow s_{x}=s_{y} . Our distributed system model consists of multiple nodes with their shared memory replicas \mathcal{R}=\{r_{1},r_{2},\ldots,r_{n}\} . Operations issued on the replicas are applied locally and eventually synchronized between nodes, which are connected with an unreliable network. Local replica r of the shared memory is modeled by a local history \mathcal{H}_{r} , which is a sequence of operations, and each register x=M_{i} has a projection \mathcal{H}_{r}(x) of the history, which is a sequence of actions corresponding to x . One can provide the notion of happens-before ( 8 ) relation \prec , defined over actions and operations in the history, so that if o_{1}\prec o_{2} , then o_{1} precedes o_{2} in any history \mathcal{H}_{r} (same definition for a_{1}\prec a_{2} and \mathcal{H}_{r}(x) ). Each memory register x=M_{i} is initialized with a constructor operation c_{x} , so that \forall a\in\mathcal{H}_{r}(x)\colon a\not\in c_{x}\Rightarrow c_{x}\prec a . When an operation is applied by a replica, it is just appended to the local history \mathcal{H}_{r} . Eventually, the current replica history \mathcal{H}_{r} is published , so that it is available for pull on the other replicas. When ready to reconcile with foreign changes, replica r synchronizes-with another replica r^{\prime} by integrating operations from another replica’s published history \mathcal{H}_{r^{\prime}} into the local history, i.e., \mathcal{H}_{r}\leftarrow\mathcal{H}_{r}\sqcup\mathcal{H}_{r^{\prime}}. Complete synchronization is achieved through integrating the histories of all replicas in an arbitrary order, until they converge to the same state once all the conflicts are resolved. 3. Conflict Model A conflict model provides mechanisms for identification and resolution of conflicts in collaborative data structures. The strongest conflict model is the concurrent conflict model, i.e., operations are conflict-prone if they are concurrent in terms of happens-before relation ( 8 ) : o_{1}\parallel o_{2}\Leftrightarrow o_{1}\not\prec o_{2}\land o_{2}\not\prec o_{1} . The weaker one is the non-commutative conflict model, i.e., operations conflict if they are concurrent and non-commutative ( 14 ) . Usually, conflict resolution is captured by establishing the happens-before order between conflicting operations, so that they can be applied in a consistent manner on all replicas. In this section, we introduce a conflict model based on operation dependencies to empower the synchronization procedure in the outlined system model. 3.1. Conflict Identification Let us consider two kinds of relations over operations in the history: entails ( \vdash ) and is discarded by ( \ll ). Intuitively, entailment captures epistemic preconditions ( 19 ) of an operation: issuing a new operation relies on the presence of effects of its premises, under the assumption that their effects remain valid. Discarding, in turn, captures epistemic revision ( 2 ) : an operation may invalidate the effect of another operation, thereby operation is no longer a premise for subsequent operations. Syntactically, upon being applied, o is assigned an immutable set of premises \Gamma=\{o_{1},o_{2},\ldots,o_{n}\} that entail o , which is denoted as \Gamma\vdash o . The premises of an operation o=[a_{1},\ldots,a_{k}] are derived from the premises of its actions, i.e., \Gamma(o)=\bigcup_{j\in[1,k]}\Gamma(a_{j}) , and a_{1}\vdash a_{2} denotes that the corresponding operations a_{1}\in o_{1} and a_{2}\in o_{2} satisfy o_{1}\vdash o_{2} . Common premises of several operations are denoted as \Gamma(o_{1},o_{2},\cdots,o_{n})=\bigcap_{i=1}^{n}\Gamma(o_{i}) . Entailment implies happens-before relation, i.e., o_{1}\vdash o_{2}\Rightarrow o_{1}\prec o_{2} . Let \vdash^{*} define the reflexive transitive closure of \vdash . Then, concurrent operations may be redefined in terms of entailment as follows: o_{1}\parallel o_{2}\Leftrightarrow(o_{1}\not\vdash^{*}o_{2})\ \land\ (o_{2}\not\vdash^{*}o_{1}) . We require that each action a is associated with a monotonically non-increasing predicate vis(a,\mathcal{H}_{r}(x)) , indicating whether the effect of a is visible in the current history \mathcal{H}_{r}(x) . State is modeled as a set of actions with their visible effects. Next, we allow an action in the history to be rolled back by removing it together with all actions that transitively depend on it, i.e., \mathcal{H}_{r}(x)\setminus{a}\equiv[a^{\prime}\in\mathcal{H}_{r}(x)\colon a\centernot\vdash^{*}a^{\prime}] . Then, we define is discarded by relation as follows: a_{1}\ll a_{2}\Leftrightarrow a_{1}\vdash a_{2}\ \land\ vis(a_{1},\mathcal{H}_{r}(x)\setminus\{a_{2}\})\land\neg vis(a_{1},\mathcal{H}_{r}(x)) . Similarly, o_{1}\ll o_{2}\Leftrightarrow\exists a_{1}\in o_{1},\ a_{2}\in o_{2}\colon a_{1}\ll a_{2} , and vis(o)=\bigwedge_{a\in o}vis(a) . A conflict arises when a premise of one operation is concurrently discarded by another operation. Formally, for a set of operations \{o_{1},o_{2},\ldots,o_{n}\} , we define the set of conflicting premises as \hat{\Gamma}(o_{1},o_{2},\cdots,o_{n})=\{o^{\prime}\in\Gamma(o_{1},o_{2},\cdots,o_{n})\mid\ \exists o_{i}\neq o_{j}\colon o^{\prime}\vdash o_{i}\land o^{\prime}\ll o_{j}\} . Two operations o_{1} and o_{2} are said to be compatible if they do not have conflicting premises, i.e. o_{1}\triangleleft o_{2}\Leftrightarrow\hat{\Gamma}(o_{1},o_{2})=\varnothing . Similarly, a local history \mathcal{H}_{r} is compatible with an operation o if all operations in the history are compatible with o : \mathcal{H}_{r}\triangleleft o\Leftrightarrow\forall o^{\prime}\in\mathcal{H}_{r}\colon o^{\prime}\triangleleft o . A history \mathcal{H}_{r} is valid if it is a topological ordering of the received operations with respect to \vdash , and all pairs of operations in the history are mutually compatible: \forall o_{i},o_{j}\in\mathcal{H}_{r}\colon o_{i}\triangleleft o_{j} . To enable representation of operations with their premises, we use an entailment graph , where nodes are the operations of the local history \mathcal{H}_{r} and directed edges represent the partial order \vdash . An edge between o_{1} and o_{2} exists if and only o_{1}\vdash o_{2} . Then, topological sorting of the entailment graph induces a valid history \mathcal{H}_{r} ( 7 ) . 3.2. Conflict Resolution To support conflict resolution, we allow an operation to be rebased with respect to its premises. Then, intuitively, when a conflict occurs, conflicting operations may be rebased to a merge operation that reconciles them. Let us denote by \hat{o}\ \hat{\vdash}\ o that an operation o is rebased to \hat{o} . Formally, when \hat{o}\ \hat{\vdash}\ o , we interpret o as an empty sequence of actions and include its premises to the premises of \hat{o} , i.e., \Gamma(o)\subseteq\Gamma(\hat{o}) . Additionally, we close the entailment relation transitively under rebasing: (o_{1}\ \vdash\ o^{\prime})\land(o^{\prime}\ \hat{\vdash}\ o_{2})\Rightarrow(o_{1}\vdash o_{2}) . The incoming edges of o may be removed from the entailment graph, as its premises \Gamma(o) are transitively included in \hat{o} . That is, rebasing induces causality: o_{1}\ \hat{\vdash}\ o_{2}\Rightarrow o_{1}\prec o_{2} . To support cancellation of operations, we define a distinguished tombstone operation o_{\varnothing} . An operation rebased to o_{\varnothing} is treated as semantically null: it does not contribute effects and need not be merged into replica histories. Such rebased operations act as discontinuity markers and may be omitted from subsequent conflict detection. Now, we are ready to present the synchronization algorithm empowered by the rebase procedure: a replica r incrementally integrates operations received from another replica r^{\prime} into its local history \mathcal{H}_{r} . The procedure sync (r^{\prime}) , shown in Figure 1 , fetches the recent history \mathcal{H}_{r^{\prime}} from r^{\prime} and processes its operations in causal order. For each operation o\in\mathcal{H}_{r^{\prime}} , the algorithm proceeds as follows. First, if o has been rebased at r^{\prime} , that is, there exists \hat{o}\in\mathcal{H}_{r^{\prime}} such that \hat{o}\ \hat{\vdash}\ o , the operation o is is rolled back from the local history \mathcal{H}_{r} , i.e., o and all its transitive premises are removed. If o has been rebased to the tombstone operation o_{\varnothing} , it is treated as cancelled and skipped. If an operation is rebased in both replicas to different operations, all the rebases are applied (the corresponding merge operations \{\hat{o}_{i}\} may be stored in a Grow-only Set ( 14 ) ). If o is not already present in \mathcal{H}_{r} and is compatible with the current history, i.e., \mathcal{H}_{r}\triangleleft o , then o is appended to \mathcal{H}_{r} using apply , as the premises of o are already in \mathcal{H}_{r} due to the causal order of \mathcal{H}_{r^{\prime}} . Otherwise, if o is not present in \mathcal{H}_{r} and conflicts with it, i.e. \mathcal{H}_{r}\centernot\triangleleft o , synchronization is suspended and conflict resolution is triggered via resolve procedure. The resolution procedure resolve , described below, takes as input a local history \mathcal{H}_{r} and a conflicting remote operation o_{0}\in\mathcal{H}_{r^{\prime}} such that \mathcal{H}_{r}\centernot\triangleleft o_{0} : (1) Find all common premises \Gamma=\bigcup_{i\in[0,k]}\Gamma(o_{i}) , where o_{1},\ldots,o_{k}\in\mathcal{H}_{r} and \forall i\in[1,k]\colon o_{i}\centernot\triangleleft o_{0} . (2) Define the set of operations for conflict resolution O as operations entailed by \Gamma , i.e., O=\{x\mid\exists\bar{o}\in\Gamma\colon\bar{o}\vdash x\} . (3) Optionally, if a user participates in the conflict resolution and authorized to cancel operations, unneeded operations with their respective ancestors can be excluded before merging O . Therefore, O is partitioned into a set of operations to preserve \mathcal{D}_{\hat{o}} and operations to cancel \mathcal{D}_{\varnothing} . By default, \mathcal{D}_{\hat{o}}=O , \mathcal{D}_{\varnothing}=\varnothing . (4) Create merge operation \hat{o} with premises \Gamma(\mathcal{D}_{\hat{o}}) and a sequence of actions returned by an external reconcile procedure applied to the whole \mathcal{D}_{\hat{o}} . In general, reconcile is an interactive procedure where user manually defines desired order of actions in \hat{o} and, optionally, adds new actions or removes existing ones, as long as no new premise p , such that p\centernot{\vdash^{*}}\Gamma(o_{i}) , extends \Gamma(\hat{o}) . (5) Rebase operations in \mathcal{D}_{\hat{o}} to \hat{o} and operations in \mathcal{D}_{\varnothing} to o_{\varnothing} . apply (o) : \mathcal{H}_{r}\leftarrow\mathcal{H}_{r}\sqcup\{o\} sync (r^{\prime}) : \mathcal{H}_{r^{\prime}}\leftarrow fetch r^{\prime} \triangleright fetch recent history from r^{\prime} for each o\in\mathcal{H}_{r^{\prime}} do \triangleright in causal order if \exists\ \hat{o}\in\mathcal{H}_{r^{\prime}}\colon\ \hat{o}\ \hat{\vdash}\ o then \mathcal{H}_{r}\leftarrow\textsc{rollback}(o,\mathcal{H}_{r}) \triangleright apply recent rebasing if o_{\varnothing}\ \hat{\vdash}^{*}\ o then continue \triangleright skip cancelled operation end if end if if o\not\in\mathcal{H}_{r}\land\mathcal{H}_{r}\triangleleft o then \textsc{apply}(o) else if o\not\in\mathcal{H}_{r}\land\mathcal{H}_{r}\centernot\triangleleft o then \mathcal{H}_{r}\leftarrow\textsc{resolve}(o,\mathcal{H}_{r}) \triangleright resolve conflict end if end for Figure 1. Synchronization algorithm to integrate foreign history \mathcal{H}_{r^{\prime}} into \mathcal{H}_{r} . Synchronization algorithm to integrate foreign history $\mathcal{H}_{r'}$ into $\mathcal{H}_{r}$. o^{\prime} o_{1} o_{2} \vdash^{*} \vdash^{*} \vdash \ll \Rightarrow o^{\prime} o_{1} o_{2} \vdash^{*} \vdash^{*} \hat{o} \hat{\vdash} \hat{\vdash} \ll Figure 2. Conflict resolution of o_{1} and o_{2} with one conflicting premise o^{\prime} . Two operations $o_1$ and $o_2$ have a common premise $o'$, which entails $o_1$ and is discarded by $o_2$. After the conflict is resolved, both $o_1$ and $o_2$ are rebased to a merge operation $\hat{o}$, which discards premise $o'$. o^{\prime} o^{\prime\prime} o_{1} o_{2} o_{3} \vdash^{*} \vdash^{*} \vdash^{*} \vdash \vdash \vdash \ll \ll \Rightarrow \hat{o} o^{\prime} o^{\prime\prime} \cancel{o_{1}} \cancel{o_{2}} \cancel{o_{3}} \vdash^{*} \vdash^{*} \vdash^{*} \hat{\vdash} \hat{\vdash} \hat{\vdash} \ll \vdash Figure 3. Conflict resolution of o_{2} against o_{1} and o_{3} with two conflicting premises o^{\prime} and o^{\prime\prime} , and the merge operation \hat{o} discarding premise o^{\prime} . Two operations $o_1$ and $o_2$ have common premises $o'$ and $o''$, where $o'$ entails $o_1$ and is discarded by $o_2$, while $o''$ entails both $o_2$ and $o_3$. $o_1$ is discarded by $o''$. After the conflict is resolved, $o_1$, $o_2$, and $o_3$ are rebased to a merge operation $\hat{o}$, which discards premise $o'$. Simple cases with one and two conflicting premises are illustrated in Figures 2 and 3 respectively. For simplicity, common premises may be depicted simply as \Gamma . When several operations o_{1},o_{2} discard same premises \Gamma , it means that \exists o^{\prime},o^{\prime\prime}\in\Gamma\mid o^{\prime}\ll o_{1}\ \land\ o^{\prime\prime}\ll o_{2} . Conflicts may be resolved concurrently, i.e., it is possible for a single operation o to be rebased to different merge operations \hat{o}_{1} and \hat{o}_{2} on different replicas, as illustrated in Figure 4 . It is an expected situation, which may lead to necessity of further conflict resolution as an inevitable part of an articulation work. \Gamma o_{1} o_{2} \vdash^{*} \vdash^{*} \ll \ll \Rightarrow \hat{o}_{1} \hat{o}_{2} \Gamma \cancel{o_{1}} \cancel{o_{2}} \vdash^{*} \vdash^{*} \hat{\vdash} \hat{\vdash} \hat{\vdash} \hat{\vdash} \ll \ll Figure 4. Conflict resolution of o_{1} and o_{2} with two conflicting premises o^{\prime} and o^{\prime\prime} and a conflict resolved concurrently leading to another conflict between \hat{o}_{1} and \hat{o}_{2} . Two operations $o_1$ and $o_2$ have common premises $\Gamma$, where $\Gamma$ is discarded by both $o_1$ and $o_2$. After the conflict is resolved concurrently on two replicas, $o_1$ and $o_2$ are rebased to $\hat{o}_1$ and $\hat{o}_2$, both discarding premise $\Gamma$ once again. 3.3. Register Definition Let us discuss requirements on actions and their visibility predicates to define a register suitable for our conflict model. Definition 3.1. A register x with an action basis A is discard-complete if for every pair of its action instances a_{1},a_{2} in any history \mathcal{H}_{r}(x) of x the following holds: vis(a_{1},\mathcal{H}_{r}(x)\setminus\{a_{2}\})\land\neg vis(a_{1},\mathcal{H}_{r}(x))\Rightarrow a_{1}\ll a_{2}. Then, to define a register x=M_{i} for our shared memory model, it is sufficient to specify: • Action basis A_{i} ; • Interpretation function \mathcal{I}\colon\mathcal{H}_{r}\to S_{i} mapping local history to the state s\in S_{i} ; • Arbitrary entailment rule, defining premises \Gamma(a) for each action a\in A_{i} , depending on its semantics; • Visibility predicate vis(a,\mathcal{H}_{r}) , defining when the effect of an action is visible, so that register is discard-complete. 3.4. Correctness The presented shared memory model is not strongly convergent, as we expect conflicts to may have indefinitely arisen during synchronization. However, we may prove that if no new operations are introduced and all conflicts are resolved, the shared memory strongly converges to the same state on all replicas. We present a proof sketch which is split into two parts: firstly, we prove that the entailment graph as a graph data type satisfying strong eventual consistency (SEC) ( 15 ) (beyond reconciliation scenarios), and secondly, we show that each register converges to the same state in case all conflicts are resolved (assuming conflicts have been resolved in a centralized manner). Theorem 3.2. A graph data type, equivalent to the entailment graph G_{\vdash} , which supports operations add(\Gamma,o) (adding a new vertex o with its incoming edges \Gamma ) and rebase(o,\hat{o}) (adding an edge to o from \hat{o} not succeeding it) satisfies SEC ( 15 ) , i.e., all replicas that have delivered the same updates have the equivalent states. Proof sketch. In this proof, we will rely on the definition of add-only monotonic directed acyclic graph CRDT in ( 14 ) , which models partial order graph starting from the initial edge (i_{s},i_{f}) and provides an interface with a single method addBetween(a,o,b) , which adds a new vertex o with edges (a,o) and (o,b) . CRDTs are strongly convergent by their definition, so if we can model a data type using CRDT, it is strongly convergent as well. Let us show that the operations of G_{\vdash} may be expressed via addBetween , so G_{\vdash} is a specific case of the state-based CRDT above. Initial state may be expressed as a set of edges \{(c_{i},i_{f})\} , where c_{i} are the register constructor operations, and i_{f} is a sentinel. add(\Gamma,o) may be expressed as executing addBetween(o^{\prime},o,i_{f}) for every premise o^{\prime}\in\Gamma , and rebase(o,\hat{o}) is equivalent to performing addBetween(o^{\prime},\hat{o},o) for every premise o^{\prime}\in\Gamma(o) . ∎ Theorem 3.3. Let all replicas freeze their histories \mathcal{H}_{r_{i}} and have them published, so replica r synchronizes-with all of them, resulting in local state s produced by a local history \mathcal{H}_{r} (which is induced from the entailment graph G_{\vdash} ). After all replicas synchronize-with published \mathcal{H}_{r} , they obtain the same state s and their histories \mathcal{H}_{r_{i}}^{\prime} are inducible from G_{\vdash} . \forall i\colon\exists s\colon\forall r\in\mathcal{R}\colon s=\mathcal{I}_{i}(\mathcal{H}_{r}(M_{i})). Proof sketch. We need to prove that in absence of newly issued operations and centralized reconciliation of all replicas, which took place at r , all the replicas will acquire the same state during synchronization without calling resolve , i.e., no further conflict resolution happens. Let history \mathcal{H}^{\prime} of a replica r^{\prime} be induced , i.e., generated as a topological sort, from G_{\vdash}^{\prime} before replica r synchronized-with r^{\prime} . In terms of graphs, upon r^{\prime} receives \mathcal{H}_{r} , G_{\vdash}^{\prime}\sqsubseteq G_{\vdash} , as no new operations are made on r (and, consequently, no new entailment edges are added). Then, as we previously showed that an entailment graph may be modeled as a state-based CRDT, due to the mononocity G_{\vdash}^{\prime}\leq G_{\vdash} and the idempotence of least-upper-bound operator \sqcup ( 15 ) , G_{\vdash}^{\prime}\sqcup G_{\vdash}=G_{\vdash} . The rest we need to prove is that any history induced from G_{\vdash} produces the same state s which is modeled as a set of visible and invisible action instances. Due to discard-completeness of registers and absence of conflicts in G_{\vdash} , if a_{1} is invisible, then \exists!\ a_{2}\colon a_{1}\ll a_{2} , i.e., a_{1}\prec a_{2} . Thus, due to the happens-before order on actions that make other actions invisible in any history, all the histories produce the same state. ∎ 4. Examples In this section, we illustrate the proposed model with several register data type definitions by specifying their actions A and their visibility predicates vis(a,\mathcal{H}_{r}) . 4.1. Register Register is a data type that stores a single value with an action basis A=\{mov\} and a query val , which is instantiated with the constructor c_{x}=[mov\ 0] . Let the state s\in S be modeled as a pair (\nu,\alpha) , where \nu is the current value of the register and \alpha is the last action that set this value. Then an action a=mov\ v is applied to local register replica x_{r} with \Gamma(a)=\{\alpha(x_{r})\} and interpreted by \mathcal{I} as setting the state s to (v,a) . Getting the value is performed as follows: val=\lambda.\nu . Visibility of an action a is defined as the local state s=\mathcal{I}(\mathcal{H}_{r}(x))=(\nu,\alpha) of the register x holds the value v set by this action, i.e., vis(a,\mathcal{H}_{r}(x))\Leftrightarrow\nu=v\land\alpha=a . Any pair of concurrent operations containing mov actions corresponding to the same register instance x are in conflict. 4.2. Arithmetic Register Let us extend an integer register data type with arithmetic actions A=\{mov,add,mul\} with an interpreter \mathcal{I} producing the state s=(\omega,\nu,\alpha) , where \omega\in\{=,+,\cdot\} is the current computation mode corresponding to the actions of A , \nu is the current initial value, and \alpha is a sequence of actions performed on this value. Query val may then be derived as getting the aggregate of the actions in \alpha over \nu , i.e., val=\lambda.\ foldr\ \omega\ \nu\ \alpha . Visibility of an action a then may be defined as follows: vis(a,\mathcal{H}_{r}(x))\Leftrightarrow a\in\alpha , and \Gamma(a)=\{{last}(\alpha)\} . Let us consider an example with a register x constructed by c_{i}=[a_{0}] , a_{0}=add\ 0 , which is interpreted as the state s=(+,0,\{a_{0}\}) . A following addition action a_{1}=add\ 2 is interpreted as appending a_{1} to \alpha , i.e., s=(+,0,\{a_{0},a_{1}\}) . Similarly, a multiplication action a_{2}=mul\ 5 is interpreted as setting the computation mode \cdot with the current \nu=val and overwriting the action sequence with \{a_{2}\} , i.e., s=(\cdot,2,\{a_{2}\}) . An assignment action a_{3}=mov\ 3 modifies the state to s=(=,10,\{a_{3}\}) , but subsequent assignments are not accumulated in the action set. A similar example is shown in Figure 5 . c_{x} add\ 2 \vdash mov\ 3 add\ 4 mul\ 5 \ll \vdash \ll \vdash^{*} \vdash^{*} \vdash^{*} \Rightarrow c_{x} add\ 2 \vdash \cancel{mov\ 3} \cancel{add\ 4} \cancel{mul\ 5} mov\ 8 \varnothing \hat{\vdash} \hat{\vdash} \hat{\vdash} \ll \vdash^{*} \vdash^{*} \vdash^{*} Figure 5. Conflict resolution on arithmetic register within additive context of add\ 2 , which resulted in mov\ 8 . An arithmetic register is constructed with $c_x$ entailing $add \ 2$. Then, three concurrent operations $mov \ 3$, $add \ 4$, and $mul \ 5$ are made, where $mov \ 3$ and $mul \ 5$ discard $add \ 2$, while $add \ 4$ entails it. After the conflict is resolved, a new operation $mov \ 8$ is made, which discards $add \ 2$. Specifically, $mov \ 3$ is cancelled, while $add \ 4$ and $mul \ 5$ are rebased to be entailed by $mov \ 8$. 4.3. LWW-Register Last-Write-Wins Register is a conflict-free replicated data type ( 14 ) that prioritizes the latest value assigned to the register in case of concurrent writes. To achieve this, each write operation mov\ x\ t includes a total order timestamp t\in\mathcal{T} , usually derived from the wall-clock time of the issuing process. A query val=\{v(a)\mid t(a)=\max_{t}(\mathcal{H}_{r}(x))\} simply returns the values associated with the greatest timestamp which follows the celebrated Thomas write rule ( 18 ) . Despite LWW-Register being seen as conflict-free, still the conflict can happen, which is known as lost update problem , when a write operation effect may have never been observed by a read operation due to the presence of a more recent concurrent write operation, i.e., values are silently overwritten during synchronization. Traditionally, this nuance is ignored in favor of simplicity of the data type interface, however, it is easy to resolve such situations in entails-discards model. To identify lost updates, we specify visibility predicate as vis(a,\mathcal{H}_{r}(x))\Leftrightarrow\{a\}=\{a^{\prime}\mid t(a^{\prime})=\max_{t}(\mathcal{H}_{r}(x))\} , query val=\{v(a)\mid t(a)=\max_{t}(\mathcal{H}_{r}(x))\} , and \Gamma(a)=\{a\mid t(a)=\max_{t}(\mathcal{H}_{r}(x))\} . Conflicts may be resolved automatically by the replicas in place, when the merge operation \hat{o} simply replays the latest seen write operation. At the same time, equal greatest timestamps may be still defined as a conflict, as shown in Figure 6 , or resolved deterministically, e.g., by comparing operation identifiers. (A,0) (B,2) (C,2) (D,1) \ll \vdash \ll \vdash^{*} \vdash^{*} \vdash^{*} \Rightarrow (A,0) \cancel{(B,2)} \cancel{(C,2)} \cancel{(D,1)} (B,2) \hat{\vdash} \hat{\vdash} \hat{\vdash} \ll \vdash^{*} \vdash^{*} \vdash^{*} Figure 6. Conflicts in LWW-Register: (B,2) and (C,2) are concurrent operations with equal timestamps; (D,1) is suppressed by its siblings. TODO: add description 4.4. Multi-Register Finally, collaboration in shared memory consisting of multiple registers can be considered, which illustrates that operations may contain actions on distinct registers. Let us introduce a touch action to allow definition of custom user-defined premises for operations that span multiple registers. Action touch simply forces recent mov operation o to be included in the premises \Gamma of the issuing operation. Roughly speaking, this mechanism enables expression of custom optimistic locks on registers by referencing operations providing the currently observed values. Let us consider an example with three registers corresponding to fields of a calendar event: M_{1} is a string event title, M_{2} is a pair of the event start and the end time modeled as unix timestamps, and M_{3} is the event location. All the registers are initially instantiated by their respective constructors: c_{1}=mov\ ^{\prime}{\text{Lunch: Alice x Bob}}^{\prime} , c_{2}=mov\ {\text{1pm-1.30pm}} , c_{3}=mov\ ^{\prime}{\text{Bambi's}}^{\prime} . Assume Alice has acquired a time slot to extend the event duration until 2pm, but Bob changes the event location concurrently, i.e., o_{A}=[mov\ M_{2}\ {\text{1pm-2pm}}] exists with o_{B}=[mov\ M_{3}\ {\text{Meadow's}}] . However, Alice had optimistically assumed that the event location will not be changed by others, because, otherwise, the event duration would not have been extended in o_{A} . These operations are compatible, as they operate on different registers, but they can be simply adjusted, so that the intention conflict and optimistic assumption of Alice about the event location not changed is respected. To achieve this, Alice’s operation o_{A} includes a touch\ M_{3} action in o_{A} , so that Bob’s concurrent update o_{B} will result in a conflict, as soon as Alice receives Bob’s update, as shown in Figure 7 . c_{1} c_{2} c_{3} o_{A} \ll \vdash o_{B} \ll \vdash^{*} \vdash^{*} Figure 7. Multi-register example: Alice issues o_{A}=[touch\ M_{3},\ mov\ M_{2}\ {\text{1pm-2pm}}] , Bob issues o_{B}=[mov\ M_{3}\ {\text{Meadow's}}] . Conflict arises as the effect of c_{3} is concurrently discarded by o_{B} . 5. Related work The presented conflict model is influenced by dynamic epistemic logic ( 19 ) with a goal to revisit intention preservation property ( 17 ) firstly captured in consistency model for Operational Transformations ( 4 ) . As operation may be applied only when its premises are already present in the history, the conflict model implies a weaker form of causal delivery ( 8 ) . Support of multi-register data types accords with wait-free data structures in shared memory ( 1 ) and the composition of convergent and commutative replicated data types ( 3 ; 20 ) . The entailment graph is a monotonic semi-lattice, i.e., a state-based replicated data type (CvRDT) ( 14 ) and, noteworthy, it is used to represent the operation-based history of a data type. Mergeable replicated data types (MRDTs) ( 5 ) also present a framework for defining arbitrary data types using invertible relational specifications, where concretization functions are employed to resolve conflicts by ordering operations in a three-way merge manner ( 9 ) . However, conflicts are not explicitly represented neither in CRDTs nor in MRDTs, which complicates reasoning about the data type behavior in presence of concurrent updates in collaboration. 6. Conclusion In this work, we presented a conflict model for collaborative data types based on custom defined entails-discards semantics of operations. The next step in this research is to refine the correctness proof and explore the expressiveness of the model by revisiting known non-register CRDTs, to define a general procedure for selective undo-redo operations, and implement a software framework to define custom data types and automatically prove their correctness properties.