# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 4 Canonical Sequences and Sets
### Canonical Sequences  
Informally, canonical sequences are the \"clean\" versions of non-breaking command sequences. The initial definition is a mixture of syntactical and semantical properties. Proposition 3 defines an algorithm which converts any sequence into a canonical one purification, and Theorem 1 gives a complete syntactical characterization. An important consequence of this characterization is that the semantics of a canonical sequence is determined uniquely by the unordered set of commands it contains. It means that the order of the commands--up to semantical equivalence--can be recovered from their set only. **Definition 2** (Canonical sequences). : _A command sequence is canonical if_  
Figure 2: Structure of an up (left) and down (right) \(\ll\)-chain. Black arrows point to the parent node and red arrows show the execution order \(\ll\). _it does not contain null commands, that is, a command of the form_ \(\langle n,x,x\rangle\)_,_ _(b) no two commands in the sequence are on the same node, and_ _(c) it is non-breaking._  
Conditions (a) and (b) are clearly syntactical, and can be checked by looking at the commands in the sequence. In Theorem 1 below we give a purely syntactical characterization of canonical sequences. Before stating the theorem we show that canonical sequences are the \"clean\" versions of arbitrary command sequences. **Proposition 3** ([18], Theorem 27). : _For every non-breaking command sequence \(\alpha\) there is a canonical sequence \(\alpha^{*}\) such that \(\alpha\sqsubseteq\alpha^{*}\), that is, if \(\alpha\) does not break \(\Phi\), then both \(\alpha\) and \(\alpha^{*}\) have the same effect on \(\Phi\)._  
Proof. : Null commands can be deleted from \(\alpha\) as they do not change the filesystem (but may break it). Suppose \(\alpha\) has two commands on the same node. Choose two which are closest to each other; let these be \(\sigma_{1}\) and \(\sigma_{2}\), both on node \(n\). The output value of \(\sigma_{1}\) must be the same as the input value of \(\sigma_{2}\) (as \(\alpha\) is non-breaking and the value at node \(n\) does not change between \(\sigma_{1}\) and \(\sigma_{2}\)). If \(\sigma_{1}\) and \(\sigma_{2}\) are not next to each other, then using Proposition 2, either \(\sigma_{1}\) can be moved forward by swapping it with the immediately following command (which, by assumption, is on a different node), or \(\sigma_{2}\) can be moved backward by swapping it with the immediately preceding command. If none of those swaps can be done, then \(\alpha\) would break every filesystem. Eventually \(\sigma_{1}\) and \(\sigma_{2}\) can be moved next to each other. In this case, however, Proposition 1 implies that \(\sigma_{1}\sigma_{2}\) can be replaced by a simple command. This proof is constructive and specifies a quadratic algorithm which transforms any non-breaking sequence into a canonical one. To state the purely syntactical characterization of canonical sequences we need further definitions. **Definition 3**. : _Let \(\alpha\) be a command sequence. (a) \(\alpha\)_hors \(\ll\), if for commands \(\sigma,\tau\in\alpha,\sigma\) precedes \(\tau\) whenever \(\sigma\ll\tau\). (b) \(\alpha\) is \(\ll\)-connected, if for any two commands \(\sigma,\tau\in\alpha\), either \(\sigma\,\parallel\,\tau\), or \(\sigma\) and \(\tau\) are connected by an \(\ll\)-chain (see Definition 1) whose elements are in \(\alpha\)._  
**Theorem 1** (Syntactical characterization of canonical sequences). : _A command sequence is canonical if and only if (a) it does not contain null commands, (b) no two commands in the sequence are on the same node, (c1) it honors \(\ll\), and (c2) it is \(\ll\)-connected._  
Proof. : Let \(\alpha\) be a canonical sequence according to Definition 2. To see that if either (c1) or (c2) fails then \(\alpha\) breaks every filesystem, use induction on the length of \(\alpha\). This shows that if \(\alpha\) contains commands on nodes \(n\) and \(m\) which lie on the same branch, then \(\alpha\) must contain commands on every node between \(n\) and \(m\) in the right order.