# Synchronizing Many Filesystems in Near Linear Time
## 5 Theory
### Characterizing Refluent Sets
: _The canonical sets \(A_{i}\) are jointly refluent if and only if the following conditions hold:_  
1. _All commands on node_ \(n\) _have the same input value;_
2. _If_ \(m\) _is above_ \(n\) _and neither_ \(I_{n}\) _nor_ \(I_{m}\) _are empty, then_ \(I_{\uparrow n}\) _is non-empty as well;_
3. _If_ \(x(\uparrow n)\
eq\mathbb{D}\)_, then_ \(I_{n}\subseteq I_{\uparrow n}\)_;_
4. _If_ \(x(n)\
eq\mathbb{O}\)_, then_ \(I_{\uparrow n}\subseteq I_{n}\)_._  
Proof. : Let us remark that condition (b) is equivalent to requesting that if \(n\) and \(m\) are comparable, neither \(I_{m}\) nor \(I_{n}\) are empty, then \(I_{n^{\prime}}\) is not empty for nodes between \(n\) and \(m\). To check that the conditions are necessary, let \(\Phi\) be a filesystem, on which all \(A_{i}\) work. Then, \(\Phi(n)=x(n)\) for all nodes mentioned in \(\bigcup_{i}A_{i}\), given condition (a). Condition (b) follows from part (b) of Claim 2 applied to the refluent sets \(A_{i}\) and \(A_{j}\), where \(i\in I_{n}\) and \(j\in I_{m}\). To check (c), assume \(x(\uparrow n)\
eq D\). Then, \(\Phi(n)=\mathbb{O}\), and so if \(A_{i}\) has a command on \(n\) (that is, \(i\in I_{n}\)), then \(A_{i}\) changes \(\Phi(n)\) to a non-empty value, and thus, at the end, the filesystem must have a directory at \(\uparrow n\). As \(A_{i}\) does not break \(\Phi\) and \(\Phi(\uparrow n)\) is not a directory, it must contain a command on \(\uparrow n\), and thus \(i\in I_{\uparrow n}\), as required by (c). Similarly, if \(x(n)\
eq\mathbb{O}\) (in which case \(\Phi(\uparrow n)=\mathbb{D}\)) and \(A_{i}\) has a command on \(\uparrow n\) (that is, \(A_{i}\) sets \(\Phi(\uparrow n)\) to be a non-directory), then \(A_{i}\) must also set \(\Phi(n)\) to be empty, and thus \(i\in I_{n}\), as required by (d). For the reverse implication, it suffices to show that Claim 2 is true for every pair \(A_{i}\) and \(A_{j}\), and then apply Proposition 1. Condition (a) of Claim 2 is immediate from (a). For the rest, we first remark that if \(m\) is the parent of \(n\) and none of \(I_{m}\) and \(I_{n}\) are empty, then \(\mathfrak{tp}\,x(m)\geq\mathfrak{tp}\,x(n)\). Indeed, if \(x(m)\
eq\mathbb{D}\), then \(I_{n}\subseteq I_{m}\) by (c), and thus, there is a canonical \(A_{k}\), which has commands on both \(n\) and \(m\), consequently, we must have \(x(n)=\mathbb{O}\). Similarly, if \(x(n)\
eq\mathbb{O}\) then \(I_{m}\subseteq I_{n}\), which implies similarly that \(x(m)=\mathbb{D}\). Returning to checking conditions in Claim 2 for sets \(A_{i}\) and \(A_{j}\), suppose \(i\in I_{m}\) and \(j\in I_{n}\) and \(m\) is above \(n\). Consider the path between \(m\) and \(n\). By condition (b), there are commands on every node between \(m\) and \(n\), and by the previous paragraph, the input types on these nodes are non-increasing. If the next node below \(m\) on the \(m-n\) path is not \(\mathbb{O}\), then (d) gives that \(A_{i}\) also has a command on that node, too. Similarly, if the node immediately above \(n\) is not \(\mathbb{D}\), then by (c), \(A_{j}\) has a command on that node. Consequently, either there is a node between \(m\) and \(n\) on which both \(A_{i}\) and \(A_{j}\) have a command, or otherwise there is a command from \(A_{i}\) and a command from \(A_{j}\) on parent-child nodes such that the former has input value \(\mathbb{D}\) (as it is not in \(A_{j}\)), and the latter has input value \(\mathbb{O}\) (as it is not in \(A_{j}\)). In all cases, conditions (b) and (c) of Claim 2 hold, as required. Based on this characterization, the following algorithm checks, in near linear time, whether the canonical command sets \(A_{i}\) for \(i\leq k\) are refluent. The algorithm assumes that the sets \(A_{i}\) are canonical. **Algorithm 6** (Checking if canonical sets are refluent, Code 6). : _Create a lexicographically sorted list of the commands in \(\bigcup_{i}A_{i}\).