# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 5 The Reconciler--Synchronizing Two Replicas  
The update detector--either state-based or operation-based--passes the canonical sets \(A\) and \(B\) to the reconciler, see Figure 1. These sets describe, in a straightforward and intuitive way, how the replicas \(\Phi_{1}\) and \(\Phi_{2}\) relate to the original filesystem \(\Phi\). As discussed in Section 2, the merged filesystem is also specified by a canonical set \(M\) (that of the sequence \(\mu\)) to be applied to the original \(\Phi\). The next definition, which is the formalization of the informal discussion in Section 2 about synchronization, _declares_ when the command set \(M\) represents an intuitively correct synchronization. **Definition 6** (Merger command set). : _The merger of the canonical sets \(A\) and \(B\) is a maximal canonical set \(M\subseteq A\cup B\), meaning that no proper superset of \(M\) within \(A\cup B\) is canonical._  
Note that the merger \(M\) is not necessarily unique, and typically many different mergers exist (see the example below). This definition covers every permissible synchronization outcome which satisfies both the _intention-confined effect_\(\mathbb{R}1\) (\(M\) is a subset of \(A\cup B\)) and the _aggressive effect preservation_\(\mathbb{R}2\) (\(M\) is maximal) requirements as discussed in Section 2. When performing the actual file synchronization, one of the mergers should be chosen, either by the system or the user. Section 6 discusses how this choice can be made by successive conflict resolutions. In this section we prove that every synchronized state defined by a merger \(M\) has a clear operational characterization: both replicas can be transformed into the merged state by first rolling back some of the commands executed earlier on this replica, and then applying some commands executed on the other replica. Using the terminology of [12], the canonical sets \(A\) and \(B\) are called _refuent_ if there is filesystem on which both of them work (neither of them breaks). This condition is clearly met when \(A\) and \(B\) describe two replicas, as both are applied to their common original filesystem. **Theorem 2**. : _Let \(A\) and \(B\) be refuent canonical sets and \(M\subseteq A\cup B\) be a merger. Then_  
1. \(M\sqsupseteq A\circ A_{1}^{-1}\circ B^{\prime}\)_, where_ \(A_{1}=A\smallsetminus M\subseteq A\) _and_ \(B^{\prime}=M\smallsetminus A\subseteq B\)_,_
2. \(M\sqsupseteq B\circ B_{1}^{-1}\circ A^{\prime}\) _where_ \(B_{1}=B\smallsetminus M\subseteq B\) _and_ \(A^{\prime}=M\smallsetminus B\subseteq A\)_,_
3. _if both_ \(A\) _and_ \(B\) _are applicable to a filesystem, then so are_ \(M\)_,_ \(A\circ A_{1}^{-1}\circ B^{\prime}\) _and_ \(B\circ B_{1}^{-1}\circ A^{\prime}\)_._  
In case of synchronizing the replicas \(\Phi_{1}=A\Phi\) and \(\Phi_{2}=B\Phi\), let \(\Psi=M\Phi\) be (one of) the merged filesystem(s). According to this theorem, we have  
\[\Psi=M\Phi=(A\circ A_{1}^{-1}\circ B^{\prime})\Phi=B^{\prime}(A_{1}^{-1}\Phi_ {1}),\ \ \text{and}\]  
\[\Psi=M\Phi=(B\circ B_{1}^{-1}\circ A^{\prime})\Phi=A^{\prime}(B_{1}^{-1}\Phi_ {2}).\]  
The first line says that the replica \(\Phi_{1}\) can be transformed into the synchronized file-system \(\Psi\) first by applying \(A_{1}^{-1}\), that is, rolling back those commands in \(A\) which are not in \(M\), and then applying some further commands \(B^{\prime}\) from \(B\). The similar statement for the other replica \(\Phi_{2}\) follows from the second line. This justifies the informal statement (\(*\)) in Section 2. Theorem 2 is illustrated on the filesystems in Figure 3. The canonical sets transforming the original filesystem to the replicas are \(A=\{\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4},\sigma_{5}\}\) (where \(\sigma_{i}=\langle n_{i},\mathbb{D},\mathbb{O}\rangle\)) and \(B=\{\tau_{5},\tau_{6},\tau_{7},\tau_{8},\tau_{9}\}\) (where \(\tau_{i}=\langle n_{i},\mathbb{O}\mathbb{D},t_{i}\rangle\)), respectively.