# Synchronizing Many Filesystems in Near Linear Time
## 5 Theory
### Characterizing Refluent Sets  
**Claim 2**: _The canonical sets \(A\) and \(B\) are refluent if and only if the following conditions hold: (a) If \(\sigma\in A\) and \(\tau\in B\) are on the same node, then their input values are the same. (b) If \(\sigma,\tau\in A\cup B\) are on comparable nodes, then for each node \(n^{\prime}\) between them, there is a command in \(A\cup B\) on \(n^{\prime}\). (c) Suppose \(\sigma,\tau\in A\cup B\) are on nodes \(\tau n\) and \(n\), respectively. If one of the sets mentions \(n\) but not \(\tau n\), then the input of \(\sigma\) is \(\mathbb{D}\); if one of the sets mentions \(\tau n\) but not \(n\), then the input of \(\tau\) is \(\mathbb{O}\)._  
Proof. : The conditions are necessary. It is clear for (a). For the other two conditions, suppose \(A\) can be applied to \(\Phi\). Observe that according to Claim 1, if \(A\) has a command on node \(n\) but not on nodes above \(n\), then on nodes above \(n\), the filesystem must contain directories; if there are no commands in \(A\) below \(n\), then all nodes below \(n\) must be empty. For the other direction, we use Claim 1, too. Set the content at each node mentioned in \(A\cup B\) to the common input value. Additionally, set the content to directory at each node above a non-empty node and set the content to empty below every non-directory node. Furthermore, for each constructor command in \(A\cup B\) on node \(n\), set every node above \(n\) not mentioned in \(A\cup B\) to a directory. Similarly, for each destructor command in \(A\cup B\) on node \(m\), set every node below \(m\) not mentioned in \(A\cup B\) to empty. Observe that values at nodes in \(A\cup B\) do not change due to (b) and (c). These assignments produce a valid filesystem which satisfies the conditions of Claim 1. **Proposition 1**: _If the canonical sets \(A_{i}:i\leq k\) are pairwise refluent, then they are jointly refluent._  
Proof. : Mimicking the proof of Claim 2, construct the filesystem \(\Phi\) as follows. Start with all empty nodes. For each command in \(A_{i}\), set the value at the node of the command to its input value. Each node obtains the same value, as the sets \(A_{i}\) are pairwise refluent. For the same reason, if a node obtains a non-empty value, then all nodes above it can be set to be a directory. Next, if \(\sigma\in A_{i}\) is a destructor and \(n^{\prime}\) below \(n\) is not mentioned in \(A_{i}\) but \(n^{\prime}\) is not empty, then it is set by some \(A_{j}\), and then \(A_{i}\) and \(A_{j}\) are not refluent. Finally, if \(\sigma\in A_{i}\) is a constructor, and \(n^{\prime}\) is above \(n\), not mentioned in \(A_{i}\), then \(n^{\prime}\) should be set to a directory. If it cannot be done because either \(\Phi(n^{\prime})\) has been set to a different value, or some nodeabove \(n^{\prime}\) has been set to a non-directory, then again we obtain \(A_{j}\) such that \(A_{i}\) and \(A_{j}\) are not refluent. **Claim 3**. : _Suppose the canonical sets \(A\) and \(B\) are refluent. Then \(A\cap B\) is an initial segment of \(A\). In particular, \(A\equiv(A\cap B)\circ(A\smallsetminus B)\)._  
Proof. : Suppose \(A\cap B\) is not empty and let \(\sigma\) be one of the common commands. By Claim 2, if \(\tau\in A\) and \(\tau\ll\sigma\), then \(\tau\) must be in \(B\) as well. Thus, \(A\cap B\) contains a command, which is an initial segment both in \(A\) and in \(B\). Delete this command from \(A\) and \(B\) and apply this claim recursively to the remaining commands. Algorithm 6 below checks whether the collection \(\{A_{i}:i\leq k\}\) of canonical sets is jointly refluent using the characterization proved in Theorem 3. For stating the theorem, define, for any node \(n\in\mathbb{N}\) and for \(i\leq k\), the index set \(I_{n}\) as  
\[I_{n}=\{i:\text{there is a command in $A_{i}$ on node $n$}\}.\]  
Assuming further that all commands in \(\bigcup_{i}A_{i}\) on node \(n\) have the same input value, this common value is denoted by \(x(n)\). **Theorem 3**.