# Synchronizing Many Filesystems in Near Linear Time
## 2 Definitions
### Canonical Sets and Sequences
: _The command set \(A\) is canonical if the following three conditions hold:_  
* \(A\) _does not contain null commands;_
* \(A\) _contains at most one command on each node;_
* \(A\) _is_ \(\ll\)_-connected._  
_The command sequence \(\alpha\) is canonical if the commands in \(\alpha\) form a canonical set and, additionally, \(\alpha\) honors \(\ll\)._  
For example, the set consisting of the three commands \(\langle\
icefrac{{}}{{a}}/\
icefrac{{}}{{b}},\mathbb{D},\
icefrac{{}}{{f_{ \mathrm{S}}}}\rangle\), \(\langle\
icefrac{{}}{{a}}/\
icefrac{{}}{{c}},\
icefrac{{}}{{f_{\mathrm{S}}} }\rangle\), and \(\langle\
icefrac{{}}{{a}}/\
icefrac{{}}{{c}},\
icefrac{{}}{{f_{\mathrm{S}}} }\rangle\) is not canonical for two reasons: the third command is a null command, and the second and the third commands are on the same node. The following command set is also not canonical:  
\[\{\langle\
icefrac{{}}{{a}}/\
icefrac{{}}{{b}}/\
icefrac{{}}{{c}}/\
icefrac{ {}}{{d}},\
icefrac{{}}{{f_{\mathrm{S}}}},\mathbb{O}\rangle,\langle\
icefrac{{} }{{a}},\mathbb{D},\
icefrac{{}}{{f_{\mathrm{S}}}}\rangle,\langle\
icefrac{{} {a}}/\
icefrac{{}}{{b}},\mathbb{D},\mathbb{O}\rangle\,\}\]  
as its first and last elements are not \(\ll\)-connected (the second and third elements are \(\ll\)-connected). Adding the command \(\langle\
icefrac{{}}{{a}}/\
icefrac{{}}{{b}}/\
icefrac{{}}{{c}},\mathbb{D}, \mathbb{O}\rangle\) to this set makes it canonical. **Theorem 1** ([PERSON], [13]). :
* _If two canonical sequences share the same command set, then they are semantically equivalent. Actually, they can be transformed into each other using commutativity rules._
* _Canonical sequences are non-breaking._
* _Every non-breaking sequence_ \(\alpha\) _can be transformed into a canonical sequence_ \(\alpha^{*}\supseteq\alpha\) _(that is,_ \(\alpha\) _and_ \(\alpha^{*}\) _have the same effect on filesystems that_ \(\alpha\) _does not break, but_ \(\alpha^{*}\) _might work on more filesystems)._
* _Canonical sets can be ordered to honor_ \(\ll\)_, that is, to become canonical sequences._  
As an example, the only order honoring the \(\ll\) relation of the canonical set  
\[E=\{\langle\
icefrac{{}}{{a}}/\
icefrac{{}}{{b}}/\
icefrac{{}}{{c}}/\
icefrac{ {}}{{d}},\
icefrac{{}}{{f_{\mathrm{S}}}},\mathbb{O}\rangle,\langle\
icefrac{{} {a}},\mathbb{D},\
icefrac{{}}{{f_{\mathrm{S}}}},\langle\
icefrac{{}}{{a}}/ \
icefrac{{}}{{b}},\mathbb{D},\mathbb{O}\rangle,\langle\
icefrac{{}}{{a}}/ \
icefrac{{}{b}}/\
icefrac{{}}{{c}},\mathbb{D},\mathbb{O}\rangle\,\} \tag{1}\]  
is the one which executes them \"bottom up\" starting with the command on \(\
icefrac{{}}{{a}}/\
icefrac{{}}{{b}}/\
icefrac{{}}{{c}}/\
icefrac{{}}{{d}}\) and ending with the command on node \(\
icefrac{{}}{{a}}\). Using Algorithm 1 as an auxiliary tool, Algorithm 2 in Section 4 checks, in near linear time, whether a command set \(A\) is canonical. Algorithm 3 arranges a canonical set into a canonical sequence. By virtue of Theorem 1_(a)_ and _(d)_, the semantics of canonical sequences is determined by the unordered set of their commands, even if their order cannot be recovered uniquely (this happens when the set contains commands on incomparable nodes). Thus, when only the semantics is concerned, a canonical sequence can, and will, be replaced by the set of its commands. For example, when we write \(A\Phi\), where \(A\) is a canonical command set, we mean that commands in the set \(A\) should be applied in some (or any) \(\ll\)-honoring order to the filesystem \(\Phi\). Similarly, \(A\circ B\) means that, first, the commands in \(A\) are applied in some \(\ll\)-honoring order, followed by the commands in \(B\), again in some \(\ll\)-honoring order. The property that commands in a canonical set can be executed in different orders while preserving their semantics is a variant of the _commutativity principle_ of CRDT [20]. Definition 4 below discusses a special case of the reordering when a subset of the commands is to be moved to the beginning of the execution line.