# Synchronizing Many Filesystems in Near Linear Time
## 2 Definitions
### Canonical Sets and Sequences  
Commutativity is a core concept in command-based synchronization [17], where, in fact, the task is to determine in what order (and which) modifications made to other replicas can be applied to a particular replica. If two modifications or commands commute, that is, their result does not depend on the order in which they are applied, then they do not represent conflicting updates to the data, as they can be seen as independent. Unsurprisingly, then, commutativity plays a central role in CRDT (see [8; 9]), where basic data types with special operators are devised so that executing the operators in different orders yields the same results. While not all filesystem commands commute, non-commutative pairs can be isolated systematically. If \(\sigma\) and \(\tau\) are on different nodes which are not in parent-child relation, then they commute (\(\sigma\tau\) and \(\tau\sigma\) are semantically equivalent). An example of this is creating a file in some directory and editing another existing file. The affected nodes where the changes are made are independent. If \(\sigma\) and \(\tau\) are non-null commands on parent-child nodes, then either \(\sigma\tau\) breaks every filesystem, or, necessarily, \(\sigma\ll\tau\). If a command \(\sigma\) on node /a/b/c is followed immediately by another command \(\tau\) on the node /a/b/c/d successfully, then \(\sigma\) must create a directory at /a/b/c (whose location previously was either empty, or contained a file); thus /a/b/c/d is empty, so \(\tau\) must create either a file or a directory there. Consequently, we have \(\sigma\ll\tau\) by Definition 2. Consecutive commands on the same node either break every filesystem (if the second command requires a different value than the output of the first command), or can be replaced by a single command (while extending the semantics). These easy facts imply some strong and intricate structural properties of non-breaking command sequences. Exploring and using these properties made possible the complete and thorough investigation of the synchronization process of two diverged replicas in [14], as well as devising the first provably correct subquadratic synchronization algorithm in this paper. Intuitively, a canonical sequence is just the \"clean\" version of a non-breaking command sequence. An important property of canonical sequences is that their semantics is determined uniquely by the set of commands they contain, see Theorem 1. Command sets that can be arranged into canonical sequences are also called canonical. For the formal definitions, we need two more notions. A command sequence \(\alpha\)_honors_\(\ll\), if for any two commands \(\sigma\), \(\tau\in\alpha\), \(\sigma\) precedes \(\tau\) in the sequence whenever \(\sigma\ll\tau\). The command set \(A\) is \(\ll\)_-connected_ if for any two commands \(\sigma\), \(\tau\in A\); if \(\sigma\) and \(\tau\) are on different comparable nodes, then they are connected by an \(\ll\)-chain (Definition 2) consisting of commands in \(A\). In particular, if \(A\) is \(\ll\)-connected and \(\sigma\), \(\tau\in A\) are on the comparable nodes \(n\) and \(m\), then \(A\) has commands on each node between \(n\) and \(m\). **Definition 3** (Canonical sets and sequences).