# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 6 Synchronization by Conflict Resolution
### Theoretical Foundation  
In this subsection we fix the refluent canonical sets \(A\) and \(B\) and the merger \(M\) which the synchronization is supposed to reach, but is not necessarily known at the start. First we show that synchronization can be reduced to the case when \(A\) and \(B\) are disjoint (though they might contain different commands on the same node). Then we define when a command pair represents a _conflict_, and show that this notion has the expected properties: a merger \(M\) does not contain conflicting pairs, and if there are no conflicts, then \(M\) is the disjoint union of \(A\) and \(B\). The main novelty of our conflict resolution algorithm is that instead using the winner to build up the merger, it only discards the losing command from future considerations. In other words, the algorithm thins out the sets \(A\) and \(B\) until only the merger \(M\) remains. Proposition 12: _Let \(A,B\) be refluent canonical sets, and \(M\) be a merger. Then (a) \(A\cap B\Subset A\) and \(A\cap B\Subset B\), (b) \(A\cap B\subseteq M\), and (c) \(A\cap B\Subset M\)._  
Proof: Claim (a) follows from Proposition 8 since if \(\tau\in A\cap B\), \(\sigma\in A\cup B\) and \(\sigma\ll\tau\), then \(\sigma\in A\cap B\). From this and from (b) claim (c) follows, too. To prove (b) it suffices to check that \(M\cup(A\cap B)\) is canonical. First, all commands in this union are on different nodes. Both \(M\) and \(A\cap B\) are canonical, so if their union were not, then there are commands \(\sigma\in A\cap B\) and \(\sigma^{\prime}\in M\smallsetminus(A\cap B)\) on comparable nodes which are not connected by an \(\ll\)-chain in \(M\cup(A\cap B)\). Assume \(\sigma^{\prime}\in A\). There is a chain between \(\sigma\) and \(\sigma^{\prime}\) in \(A\). Since \(A\cap B\Subset A\), we know this chain has the direction \(\sigma\ll\dots\ll\sigma^{\prime}\). From this and because \(\sigma^{\prime}\in M\), we know all members of this chain are in \(M\) based on Proposition 9, which is a contradiction. Let \(C=A\cap B\) and let \(\Phi\) be a filesystem which shows that \(A\) and \(B\) are refluent, that is, both \(A\) and \(B\) work on \(\Phi\). Let \(A^{\prime}=A\smallsetminus C\), \(B^{\prime}=B\smallsetminus C\), and \(M^{\prime}=M\smallsetminus C\); observe that the command sets \(A^{\prime}\) and \(B^{\prime}\) are disjoint. By Proposition 12\(C\) is canonical and can be moved to the front of \(A\) and \(B\) and \(M_{i}\); moreover \(A^{\prime}\) and \(B^{\prime}\) and \(M^{\prime}\) are also canonical. Now \(A^{\prime}\) and \(B^{\prime}\) are refluent (both are applicable to \(C\Phi\)), and \(M^{\prime}\) is a merger for \(A^{\prime}\) and \(B^{\prime}\). The converse of the last statement is also true: if \(M^{*}\) is any merger of \(A^{\prime}\) and \(B^{\prime}\), then \(C\cup M^{*}\) is a merger of \(A\) and \(B\). Consequently it suffices to find the merger \(M^{\prime}\) of the disjoint command sets \(A^{\prime}\) and \(B^{\prime}\), and then adding the intersection \(A\cap B\) to \(M^{\prime}\). For this reason, from this point on we assume that \(A\) and \(B\) share no commands. Definition 7: Let \(A\) and \(B\) be fixed disjoint, refluent canonical sets. The pair \((\sigma,\tau)\) is a _conflict_ if \(\sigma\in A\), \(\tau\in B\) and \(\sigma\
ot\models\tau\), that is, the nodes of \(\sigma\) and \(\tau\) are comparable (including when they coincide). The _conflict graph_ is the bipartite graph with the disjoint command sets \(A\) and \(B\) as the two classes, and an edge between \(\sigma\in A\) and \(\tau\in B\) if they are in conflict. Figure 4(a) shows the conflict graph of the synchronization problem depicted on Figure 3. As an example, command \(\sigma_{5}\) is connected to \(\tau_{5}\) only, as both \(\sigma_{5}\) and \(\tau_{5}\) are on node \(n_{5}\), while \(n_{5}\) is independent of the nodes \(n_{6}\),..., \(n_{9}\) on which the other commands in \(B\) are. **Proposition 13**. : _It is impossible that both commands of the conflict \((\sigma,\tau)\) are in \(M\)._  
Proof.