# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 4 Canonical Sequences and Sets
### The Update Detector  
Algorithms creating the canonical sets required by the reconciler (see Figure 1) are described in Propositions 6 and 7. The update detector is either _state-based_, in which case it has access to the original and modified filesystems, or it is _command-based_, in which case it has access to the exact sequence of commands used to modify the filesystem. Both update algorithms are highly effective; essentially their runtime is linear in the input size. **Proposition 6** (State-based update detector, ([12], Theorem 19)). : _Let \(\Phi\) be the original filesystem and let \(\Phi_{1}\) be the replica. The command set_  
\[A^{*}=\left\{\langle n,\Phi(n),\Phi_{1}(n)\rangle:n\in\mathbb{N}\;\;\text{and} \;\;\Phi(n)\
eq\Phi_{1}(n)\right\}\]  
_is canonical, and \(A^{*}\Phi=\Phi_{1}\)._  
Proof. : To show that \(A^{*}\) is canonical we need to check that it is \(\ll\)-connected. By ([18], Lemma 23) if \(n\prec m\) and \(\Phi\) and \(\Phi_{1}\) differ at \(n\) and at \(m\), then they must differ at every node between \(n\) and \(m\). Moreover, the differences follow one of the the patterns on Figure 2, thus these commands form the required \(\ll\)-chain. A consequence of this is that \(A^{*}\) does not break \(\Phi\), and since after executing the commands every node will have the output value from \(\Phi_{1}\), we know \(A^{*}\Phi=\Phi_{1}\). The set \(A^{*}\) can be generated by performing simultaneous depth-first searches on the visible (non-empty) parts of the filesystems \(\Phi\) and \(\Phi_{1}\). Such an algorithm runs in constant space, and the running time is linear in the total size of the visible parts of the filesystems. Figure 3 provides two examples for the result of the state-based update detector. The namespace \(\mathbb{N}\) consists of the nodes \(n_{1}\) to \(n_{9}\). The original filesystem \(\Phi\) contains directories at nodes \(n_{1}\) to \(n_{5}\) and the empty value at \(n_{6}\) to \(n_{9}\). The first replica deletes all directories, setting the empty value everywhere. The second replica stores file contents in \(n_{5}\) and in the empty nodes. The canonical command set transforming \(\Phi\) into \(\Phi_{1}\) consists of the five commands \(A=\{\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4},\sigma_{5}\}\) where \(\sigma_{i}=\langle n_{i},\mathbb{D},\mathbb{O}\rangle\) corresponding to the five differences between \(\Phi\) and \(\Phi_{1}\). The second command set also has five commands \(B=\{\tau_{5},\tau_{6},\tau_{7},\tau_{8},\tau_{9}\}\) with \(\tau_{5}=\langle n_{5},\mathbb{D},\tau_{5}\rangle\) and \(\tau_{i}=\langle n_{i},\mathcal{O},t_{i}\rangle\) for \(i>5\). The set \(A\) has a single execution order honoring \(\ll\), namely \(\sigma_{5}\), \(\sigma_{4}\), \(\sigma_{3}\), \(\sigma_{2}\), \(\sigma_{1}\). Any ordering of the commands in \(B\) honors \(\ll\), as no two commands in \(B\) are \(\ll\)-related. **Proposition 7** (Command-based update detector). : _Let \(\alpha\) be a command sequence that transforms the original filesystem \(\Phi\) into the replica \(\Phi_{1}\). The following procedure creates a canonical set \(A^{*}\) for which \(A^{*}\Phi=\alpha\Phi=\Phi_{1}\). Let \(A^{*}\) be empty initially, and iterate over the commands in \(\alpha\) from left to right. Let the next command be \(\sigma\). If there is no command in \(A^{*}\) on the same node as \(\sigma\), add \(\sigma\) to \(A^{*}\). If \(\sigma^{*}\in A^{*}\) and \(\sigma\) are on the same node, then using Proposition 1(a) replace \(\sigma^{*}\) with the single command corresponding to the composition \(\sigma^{*}\sigma\). Finally, when the iteration ends, delete the null-commands from \(A^{*}\)._  
Proof. : It is clear that on each node of the filesystem the sequence \(\alpha\) and the set \(A^{*}\) have the same effect. Consequently \(A^{*}\) is equivalent to the command set created in Proposition 6, therefore it is canonical. Figure 3: Illustrating the update detector. The nodes are, from left to right, \(n_{1}\) to \(n_{5}\) in the top row, and \(n_{6}\) to \(n_{9}\) in the bottom row.