# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 4 Canonical Sequences and Sets
### Canonical Sets  
An important consequence of Theorem 1 is that the semantics of a canonical sequence is uniquely determined by the commands it contains. This is expressed formally in the following Proposition. **Proposition 4** ([12], Theorem 14). : _If the canonical sequences \(\alpha\) and \(\beta\) contain the same commands, then they are semantically equivalent, that is, \(\alpha\Phi=\beta\Phi\) for every filesystem._  
Proof. : In fact, \(\alpha\) and \(\beta\) can be transformed into each other using the commutativity rules given in Proposition 2(a), see ([12], Lemma 10). **Definition 4** (Canonical set). : _The set \(A\) of internal commands is canonical if_  
1. _it does not contains null commands,_
2. _no two commands in_ \(A\) _are on the same node, and_
3. _the set_ \(A\) _is_ \(\ll\)_-connected, meaning that if two of its commands are on comparable nodes, then they are connected by an_ \(\ll\)_-chain whose elements are in_ \(A\)_._  
Commands in a canonical sequence form a canonical set by Theorem 1. In the other direction, a canonical set can be ordered in many ways to become a canonical sequence--the only requirement is (c1) which requires that the order honors the relation \(\ll\). This can be achieved by using, e.g., topological sort. Any two such orderings give semantically equivalent sequences, as was proved in Proposition 4. Consequently we can, and will, use canonical sets in places where command sequences are required with the implicit understanding that the commands in it are ordered in an appropriate fashion. For example, we write \(A\Phi\) to mean \(\alpha\Phi\) where \(\alpha\) contains the elements of \(A\) in an order which honors \(\ll\). Canonical sets play an essential role in reconciliation (Section 5) and conflict resolution (Section 6). One of their crucial properties is, as we have seen, that their commands can be executed in different orders while preserving their semantics--a variant of the _commutativity principle_ of CRDT [20]. Proposition 5 discusses the special case when a subset of the commands should be moved to the beginning of the execution line. Then we define and investigate _clusters_ in a canonical set, and observe that the clusters can be freely rearranged, and even intertwined. **Definition 5**. : _For a canonical set \(A\) we write \(B\Subset A\) to indicate that \(B\) is not only a subset of \(A\) but can also be moved to the beginning while keeping the semantics, namely \(A\equiv B\circ(A\smallsetminus B)\)._  
**Proposition 5**. : _Let \(A\) be a canonical set and \(B\subseteq A\). Then \(B\Subset A\) if and only if \(\sigma\in A\), \(\tau\in B\) and \(\sigma\ll\tau\) imply \(\sigma\in B\). If \(B\Subset A\) then both \(B\) and \(A\smallsetminus B\) are canonical._  
Proof. : An ordering of \(A\) does not break every filesystem if and only if it honors \(\ll\), see ([12], Lemma 10). Consequently, if \(A\equiv B\circ(A\smallsetminus B)\) then this split must honor \(\ll\), which is exactly the stated condition. If this condition holds, then \(A\) has an ordering which honors \(\ll\) and in which \(B\) precedes \(A\smallsetminus B\). For the second part it suffices to check that both \(B\) and \(A\smallsetminus B\) are \(\ll\)-connected. However, it is immediate from the condition and from the fact that \(A\) is \(\ll\)-connected. The \(\ll\) relation connects commands in a canonical set \(A\). The _clusters_ of \(A\) are the components of this connection graph. All commands in a cluster are constructors, or all commands are destructors, or the cluster has a single element matching \(\langle\bullet,\mathbb{F},\mathbb{F}\rangle\). Accordingly, we call the cluster _constructor_, _destructor_, or _editor_, respectively. Nodes of the commands within a cluster form a connected subtree of the namespace \(\mathbb{N}\), and the topmost elements of the subtrees are pairwise incomparable.