# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 5 The Reconciler--Synchronizing Two Replicas
The synchronized states shown on Figure 4 correspond to the mergers \(M_{1}=\{\sigma_{5},\tau_{6},\tau_{7},\tau_{8},\tau_{9}\}\), \(M_{2}=\{\sigma_{4},\sigma_{5},\tau_{6},\tau_{7},\tau_{8}\}\), and \(M_{3}=\{\sigma_{2},\sigma_{3},\sigma_{4},\sigma_{5},\tau_{6}\}\), respectively. Altogether there are six mergers of \(A\) and \(B\) depending on how many levels of the directory erasures in \(A\) are kept. To get \(\Psi_{1}\) from the replica \(\Phi_{1}\) we first roll back the commands \(\sigma_{1}\), \(\sigma_{2}\), \(\sigma_{3}\) and \(\sigma_{4}\) in this order (commands in the set \(A\smallsetminus M_{1}\)), which restores the four directories. Then we apply the commands \(\tau_{6}\), \(\tau_{7}\), \(\tau_{8}\)from the other command set \(B\) to set the file values. Getting \(\Psi_{1}\) from the second replica requires fewer commands. First roll back \(\tau_{5}\) (the only member of \(B\smallsetminus M_{1}\)) restoring the directory at \(n_{5}\), then apply \(\sigma_{5}\) to erase this directory. The proof of Theorem 2 uses some intricate properties of canonical sets and mergers which we prove first. Proposition 8: _Let \(A\) and \(B\) be refluent canonical sets with \(\tau\in A\), \(\sigma\in A\cup B\) and \(\sigma\ll\tau\). Then \(\sigma\in A\)._  
Proof: Let \(\sigma\), \(\tau\) be on nodes \(n\) and \(m\), respectively, and \(\Phi\) be any filesystem on which both \(A\) and \(B\) work. The value \(\Phi(n)\) is the input value of \(\sigma\), and \(\Phi(m)\) is the input value of \(\tau\). Now \(\sigma\ll\tau\) matches either the pattern \(\langle n,\mathbb{DF},\mathbb{O}\rangle\ll\langle\uparrow n,\mathbb{D}, \mathbb{FO}\rangle\) or the pattern \(\langle\uparrow m,\mathbb{OF},\mathbb{D}\rangle\ll\langle m,\mathbb{O}, \mathbb{FD}\rangle\), see Definition 1. If \(A\) has no command on node \(n\), then executing \(\tau\) would break \(\Phi\) as \(\Phi(n)\) still has its original value. Thus let \(\sigma^{\prime}\in A\) be on node \(n\). The input value of \(\sigma^{\prime}\) is the same as that of \(\sigma\), moreover \(\sigma^{\prime}\ll\tau\) (as \(A\) is canonical and \(\sigma^{\prime}\) and \(\tau\) are on parent-child nodes). Then the output values of \(\sigma^{\prime}\) and \(\sigma\) are also equal since they are either both \(\mathbb{O}\) or \(\mathbb{D}\), thus \(\sigma=\sigma^{\prime}\). A similar statement holds for mergers, but the proof is more involved. Proposition 9: _Let \(A\) and \(B\) be refluent canonical sets, \(M\subseteq A\cup B\) be a merger with \(\tau\in M\), \(\sigma\in A\cup B\) and \(\sigma\ll\tau\). Then \(\sigma\in M\)._  
Proof: Let \(\sigma\) and \(\tau\) be a lowest counterexample to the claim, and \(n\) and \(m\) be their respective nodes. By \"lowest\" we mean that there is no other counterexample pair \(\sigma^{*},\tau^{*}\) where the node of \(\sigma^{*}\) would be below \(n\). The argument of the proof of Proposition 8 gives that if \(M\) has a command on \(n\) (the node of \(\sigma\)), then \(\sigma\in M\). Thus \(\sigma\) cannot be added to \(M\) only if \(M\) already contains a command \(\sigma^{\prime}\) on a node \(n^{\prime}\) such that \(n^{\prime}\) and \(n\) are comparable and \(\sigma^{\prime}\) and \(\sigma\) cannot be connected by an \(\ll\)-chain. If \(m\) and \(n^{\prime}\) are comparable, then there is an \(\ll\)-chain in \(M\) between \(\tau\) and \(\sigma^{\prime}\) as both are in \(M\). As no command in \(M\) is on \(n\), the node \(n\) cannot be between \(m\) and \(n^{\prime}\), but then \(\sigma\ll\tau\ll\cdots\ll\sigma^{\prime}\) is an \(\ll\)-chain in \(M\) connecting \(\sigma\) and \(\sigma^{\prime}\), a contradiction. (Note that the chain between \(\tau\) and \(\sigma^{\prime}\) cannot be in the other direction.) Therefore \(m\) and \(n^{\prime}\) are uncomparable, which means that \(m\) and \(n^{\prime}\) are both below \(n\), consequently \(\sigma\) and \(\tau\) are constructors. Let \(\Phi\) be any filesystem on which both \(A\) and \(B\) work. As \(\sigma\) matches \(\langle n,\mathbb{OF},\mathbb{D}\rangle\), \(\Phi(n)\) is either empty or is a file.