# Synchronizing Many Filesystems in Near Linear Time
## 5 Theory
### Characterizing Refluent Sets
Consider first the case when \(\sigma\) creates a directory, that is, it matches \(\langle n,\mathbb{O}\mathbb{F},\mathbb{D}\rangle\). As \(A_{i}\) and \(A_{j}\) are refluent, let \(\Phi\) be any filesystem on which both \(A_{i}\) and \(A_{j}\) work. Since \(\Phi(n)\) is not a directory, all nodes in \(\Phi\) below \(n\) are empty, in particular, \(\tau\) matches \(\langle m,\mathbb{O},\mathbb{F}\mathbb{D}\rangle\). As the canonical \(A_{j}\) does not break \(\Phi\), \(A_{j}\) must contain commands on all nodes between \(n\) and \(m\), including \(m\). If \(n\) is a parent of \(m\), then \(\tau\ll\sigma\), and we are done. If \(n\) is strictly above \(m\), then we may assume that there are no commands in \(M\) on nodes between \(n\) and \(m\), and thus no command on \(\dagger m\) either. However, \(A_{j}\) contains a command \(\tau^{\prime}=\langle\dagger m,\mathbb{O},\mathbb{D}\rangle\) (as \(A_{j}\) does not break \(\Phi\)), and \(M\cup\{\tau^{\prime}\}\) is conflict-free, contradicting the maximality of \(M\). The second case is when \(\tau\) creates an empty node, that is, it matches \(\langle m,\mathbb{D}\mathbb{F},\mathbb{O}\rangle\). Similarly to the above, \(\sigma\) matches \(\langle n,\mathbb{D},\mathbb{F}\mathbb{O}\rangle\), and then either \(\tau\ll\sigma\), or otherwise, \(A_{i}\) contains the command \(\tau^{\prime}=\langle\dagger m,\mathbb{D},\mathbb{O}\rangle\), which can be added to \(M\). Proposition 3: _Let \(A_{i}\) be canonical sets and \(M\subseteq\bigcup_{i}A_{i}\) be a merger. If none of \(A_{i}\) breaks \(\Phi\), then neither does \(M\)._

Proof: We use the conditions in Claim 1 to show that \(M\) does not break \(\Phi\). To this end, let \(\sigma=\langle n,x,y\rangle\in M\) so that \(\sigma\in A_{i}\). Since \(A_{i}\) does not break \(\Phi\), condition (a) follows. To check (b), suppose \(\sigma\) is a destructor command, \(n^{\prime}\) is below \(n\), and it is not mentioned in \(M\). If \(n^{\prime}\) is not mentioned in \(A_{i}\) either, then condition (b) holds, as \(A_{i}\) is applicable to \(\Phi\). So suppose \(\tau^{\prime}\in A_{i}\) is on the node \(n^{\prime}\). As \(\tau^{\prime}\
otin M\), there must be a command \(\tau\in M\) on node \(m\), which is in conflict with \(\tau^{\prime}\). Since \(M\) has no command on \(n^{\prime}\) (but has a command above \(n^{\prime}\)), \(m\) must be above \(n^{\prime}\). By Definition 6, \(\tau^{\prime}\) creates a non-empty content. Since \(\sigma\) and \(\tau^{\prime}\) are not in conflict (both are in the canonical set \(A_{i}\)), \(\sigma\) must create a directory. However, this contradicts the assumption that \(\sigma\) is a destructor. The case when \(\sigma\) is a constructor and \(n^{\prime}\) is above \(n\) is similar. Proposition 4: _Let \(A_{i}\) be refluent canonical sets, and \(C\subseteq\bigcup_{i}A_{i}\) be canonical. There is a merger extending \(C\)._

Proof: As commands in \(C\) are not in conflict by Proposition 2, \(C\) can be extended to be a maximal conflict-free subset of \(\bigcup_{i}A_{i}\). However, this set is a merger by Theorem 4. ## 6 Generating All Mergers

Algorithm 5 in Section 4.4 cannot generate all possible mergers in nondeterministic linear time. The modified algorithm, which creates a merger extending a given canonical subset \(C\), can, however, be used for this purpose as follows. Pick a random subset \(C\) of the commands in \(\bigcup_{i}A_{i}\) and check if \(C\) is canonical using Algorithm 2. If yes, use the modified version of Algorithm 5 to create a merger extending \(C\); otherwise, use the original version to create a merger. While this algorithm clearly generates all mergers in nondeterministic linear time, it is not satisfactory, as it blindly guesses the final merger. In this section, we develop a more appealing approach by further exploiting the structure of refluent canonical sets. Let us fix the jointly refluent canonical sets \(\{A_{i}:i\leq k\}\), and consider all nodes mentioned in the command set \(\bigcup_{i}A_{i}\).