# Synchronizing Many Filesystems in Near Linear Time
## 2 Definitions
### Filesystem Commands  
Real-life filesystems are usually manipulated by commands such as creating or deleting files and directories, modifying (editing, appending to) a file, or moving an existing file or directory to another location. Our model contains similar commands but with some modifications, the first of which is that we only consider commands which affect the filesystem at a single node. Thus, a _move_ command should be represented as a sequence of _delete_ and _create_. Second, commands in our model include the complete new value to be stored in the filesystem. Even if file contents are just partially modified or are appended to, the full newvalue must be supplied. This allows our model to use a unified representation of all single-node commands, as they can be fully specified by the node (path), at which the command acts, and the new value (including a directory and empty value) to be stored there. Third, as was observed in [13], enriching filesystem commands with additional contextual information--in this case, the previous content at the affected node--makes them amenable to algebraic manipulation. **Definition 1** (Filesystem commands). : _A filesystem command is a triplet \(\sigma=\langle n,x,y\rangle\), where \(n\in\mathbb{N}\) is the node on which \(\sigma\) acts, \(x\) is the content at node \(n\) before \(\sigma\) is executed (the contextual information, precondition), and \(y\) is the new content._  
It is clear that every real-life filesystem command acting on a single node can be easily (and automatically) transformed into this internal representation (Definition 1). For example, \(rndir(n)\) corresponds to \(\langle n,\mathbb{D},\mathbb{O}\rangle\), which replaces the directory value at \(n\) by the empty value. The command \(\langle n,\mathbb{O},\mathbb{D}\rangle\) creates a directory at \(n\) but only if the node \(n\) has no content, that is, there is no directory or file at \(n\) (a usual requirement when creating a directory). This command reflects the usual behavior or \(mkdir\). For files \(\mathsf{f}_{1}\) and \(\mathsf{f}_{2}\in\mathbb{F}\), the command \(\langle n,\mathsf{f}_{1},\mathsf{f}_{2}\rangle\) replaces \(\mathsf{f}_{1}\) stored at \(n\) by the new content \(\mathsf{f}_{2}\). This latter command can be considered an equivalent of \(edit(n,\mathsf{f}_{2})\). As an example, creating a copy of the file /home/user/text in the same directory under the name \"copy\" and then deleting the original file is represented by the following sequence of commands:  
\[\langle\mathsf{/home/user/copy},\mathbb{O},\mathsf{f}_{o}\rangle\;\;\text{and} \;\;\langle\mathsf{/home/user/text},\mathsf{f}_{o},\mathbb{O}\rangle,\]  
where \(\mathsf{f}_{o}\) is the file content at the \"text\" node. Applying the command \(\sigma\) to a filesystem \(\Phi\) is written as the left action \(\sigma\Phi\). The command \(\sigma=\langle n,x,y\rangle\) is _applicable_ to \(\Phi\) if \(\Phi\) contains \(x\) at node \(n\), that is, \(\Phi(n)=x\) (the precondition holds), and after changing the content at \(n\) to \(y\), the filesystem still has the tree property. If \(\sigma\) is not applicable to \(\Phi\), then we say that \(\sigma\)_breaks the filesystem_. If \(\sigma\) does not break \(\Phi\), then \(\sigma\) is applicable to \(\Phi\), and its execution changes \(\Phi\) at node \(n\) only. Command sequences are applied from left to right; thus, \((\sigma\alpha)\Phi=\alpha(\sigma\Phi)\), where \(\alpha\) is a command sequence. The composition of sequences is written as the concatenation \(\alpha\beta\), but occasionally we write \(\alpha\circ\beta\) to emphasize that \(\beta\) is to be executed after \(\alpha\). A sequence breaks a filesystem if one of its commands breaks the filesystem when it is to be applied. The sequence \(\alpha\) is _non-breaking_ if there is at least one filesystem \(\alpha\) that does not break; otherwise, it is _breaking_.