# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 5 The Reconciler--Synchronizing Two Replicas
It means that all nodes below \(n\) are empty, in particular \(\Phi(n^{\prime})=\mathbb{O}\), and \(\sigma^{\prime}\) changes this empty value to something else. Now suppose \(\sigma^{\prime}\in A\). As \(A\) does not break \(\Phi\), it must change the non-directory value at \(n\) to a directory, consequently \(\sigma\in A\) as well. Then there is an \(\ll\)-chain between \(\sigma\) and \(\sigma^{\prime}\) in A starting with \(\sigma\) and ending with \(\sigma^{\prime}\in M\). As \(\sigma\) was chosen to be the lowest counterexample, all elements of this chain are in \(M\), which is a contradiction again. Recall from Proposition 5 that \(B\Subset A\) if and only if \(B\subseteq A\) and there are no \(\sigma\ll\tau\) such that \(\tau\in B\) and \(\sigma\in A\smallsetminus B\). Proposition 10: _Let \(A\), \(B\) be refluent canonical sets, and \(M\) be a merger. Then \(A\cap M\Subset A\), and \(A\cap M\Subset A\)._  
Figure 4: Three possible results of synchronizing the filesystems in Figure 3.  
Proof. : Both statements follow from the combination of Propositions 8 and 9. If \(\tau\in A\cap M\) and \(\sigma\ll\tau\) with \(\sigma\in A\cup B\), then \(\sigma\in A\cap M\). Claim (a) of Theorem 2 follows immediately from Proposition 10. Let \(A_{2}=A\cap M\), \(A_{1}=A\smallsetminus M\), and \(B^{\prime}=M\smallsetminus A\). By Propositions 10 and 5 we have \(A=A_{2}\circ A_{1}\), and \(M=A_{2}\circ B^{\prime}\). Thus  
\[M=A_{2}\circ B^{\prime}\supseteq(A_{2}\circ A_{1}\circ A_{1}^{-1})\circ B^{ \prime}=A\circ A_{1}^{-1}\circ B^{\prime},\]  
and a similar reasoning gives claim (b). Recall that the notation \(\sigma\mathbin{\|}\tau\) means that the nodes which the commands \(\sigma\) and \(\tau\) are acting on are uncomparable (that is, independent). We write \(\sigma\mathbin{\|}B\) to mean that for every \(\tau\in B\) we have \(\sigma\mathbin{\|}\tau\), and \(A\mathbin{\|}B\) to mean that for every \(\sigma\in A\) we have \(\sigma\mathbin{\|}B\). Proposition 11: _Suppose that the canonical sets \(A\) and \(B\) are applicable to the filesystem \(\Phi\); moreover, \(A\smallsetminus B\mathbin{\|}B\smallsetminus A\). Then \(A\cup B\) is canonical and is applicable to \(\Phi\)._  
Proof. : First we show that \(A\cup B\) is canonical. This is so as \(A\smallsetminus B\) and \(B\smallsetminus A\) do not have commands on comparable or coinciding nodes, thus any two commands in \(A\cup B\) on comparable nodes are both in \(A\), or are both in \(B\). Second, \(A\cup B\) is applicable to \(\Phi\) when \(A\) and \(B\) are disjoint as in this case, by assumption, \(A\mathbin{\|}B\), see also ([18], Lemma 36). When \(A\) and \(B\) are not disjoint, let \(C=A\cap B\). By Proposition 8, \(C\Subset A\), thus \(A\equiv C\circ(A\smallsetminus C)\) which means \(A\Phi=(A\smallsetminus C)(C\Phi)\). Similarly, \(B\Phi=(B\smallsetminus C)(C\Phi)\). Applying the first case of this proof to the disjoint sets \(A\smallsetminus C\), \(B\smallsetminus C\) and the filesystem \(C\Phi\) shows that \((A\cup B)\smallsetminus C\) is applicable to \(C\Phi\). Since \(C\Subset(A\cup B)\) also holds, we get that \(A\cup B\) is applicable to \(\Phi\). After these preparations claim (c) of Theorem 2 can be proved as follows. Let \(A_{2}=A\cap M\) and \(B_{2}=B\cap M\). Then \(A_{2}\cup B_{2}=M\) and \(M\smallsetminus A_{2}=B_{2}\smallsetminus A_{2}\). Now \(A_{2}\Subset M\) by Proposition 10, which means that \(A_{2}\) is canonical and \(M\equiv A_{2}\circ(M\smallsetminus A_{2})=A_{2}\circ(B_{2}\smallsetminus A_{2})\), and similarly \(M\equiv B_{2}\circ(A_{2}\smallsetminus B_{2})\). We claim that \(A_{2}\smallsetminus B_{2}\mathbin{\|}B_{2}\smallsetminus A_{2}\).