# Synchronizing Many Filesystems in Near Linear Time
## 2 Definitions
### Filesystems  
The filesystem model reflects the most important high-level aspects of real-world filesystems. It is a mixture of identity- and path-based models [10; 12]. The contents of the filesystem are stored at _nodes_, which are identified, or labeled, by a set of fixed and predetermined paths. The collection of all (virtually) available nodes is fixed in advance (while in a real-world filesystem, only a restricted subset of those paths is present). No path operations are considered; in particular, our model does not support the creation or deletion of _links_. In the basic case, no links are allowed at all; thus, the namespace--the set of available nodes or paths--forms a collection of rooted trees. An actual filesystem populates this fixed namespace with values. If \(\Phi\) is a filesystem, the value stored at node \(n\) is denoted by \(\Phi(n)\). Valid filesystems are required to have the _tree property_ all the time, meaning that along any branch starting from a root node, there must be zero or more _directories_, zero or one _file_, followed by _empty_ nodes only. If \(\Phi\) does not have the tree property, then we say that \(\Phi\) is _broken_.  
Formally, the paths form a forest-like _namespace_: a set \(\mathbb{N}\) endowed with the partial function \(\uparrow:\mathbb{N}\rightarrow\mathbb{N}\) returning the parent of every non-root node, while this function is not defined on roots. If \(n=\uparrow m\) then \(n\) is the parent of \(m\), and \(m\) is a child of \(n\). For two nodes \(n,m\in\mathbb{N}\), we say that \(n\) is above \(m\), or \(n\) is an ancestor of \(m\), and write \(n\prec m\), if \(n=\uparrow^{i}m\) for some \(i\geq 1\). As usual, \(n\prec m\) denotes \(n\prec m\) or \(n=m\). As the parent function \(\uparrow\) induces a tree-like structure on \(\mathbb{N}\), the relation \(\preccurlyeq\) is a partial order. Two nodes \(n,m\in\mathbb{N}\) are _comparable_ if either \(n\preccurlyeq m\) or \(m\preccurlyeq n\), and they are _incomparable_ or _independent_ otherwise.  
In practice, nodes of the filesystem are labeled by _complete paths_, where directory names are separated by the slash character. Thus, the root has the label \(/\); nodes \(/\)a, \(/\)/\(\times\)ax are on the first level just under the root; and \(/\)a/b/cc/d is (the label of) a node on level four, whose ancestors are \(/\)a/b/cc, \(/\)a/b, \(/\)a, and \(/\). The implementation of the algorithms also follows this convention.  
As indicated above, the value stored by a filesystem at a node can be a _directory_, can be _empty_ or can be a _file_. The type of this value is denoted by \(\mathbb{D}\), \(\mathbb{O}\) and \(\mathbb{F}\), respectively, corresponding to these possibilities. Regarding notation, we also use \(\mathbb{D}\) for the directory value, and \(\mathbb{O}\) for the empty value (where \(\mathbb{O}\) means \"no value\", not to be confused with a file which has no content). When the node value is a file, then the node stores the complete file content (including the possibility that this content is empty). While this filesystem model allows only one directory value and only one empty value (see the discussion in Section 8 on relaxing this limitation), there are many different possible file values of type \(\mathbb{F}\) representing different file contents. The value types are _ordered_, with \(\mathbb{O}\) being the lowest, and \(\mathbb{D}\) being the highest, written as \(\mathbb{O}<\mathbb{F}<\mathbb{D}\). The type of the filesystem value \(x\) is denoted by \(\mathsf{tp}(x)\).