# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 2 Methodology  
Our filesystem model, defined in Section 3, is arguably simple, but it retains all important structural properties of real filesystems. It is this simplicity that allows us to exploit a rich and intriguing algebraic structure [12; 18] which eventually leads to the claimed theoretical results. In Section 7 we discuss some possible extensions of the filesystem model. Depending on the data communicated by the replicas, synchronizers are categorized as either _state-based_ or _operation-based_[1; 16]. In state-based synchronization replicas send their current versions of the filesystem, or merely the differences (called _diff_/s) between the current states and the last known synchronized state [19]. Operation-based synchronizers transmit the complete log (or trace) of all operations performed by the user [13]. The synchronization method of this paper is reminiscent of operation-based one, but can also be considered, with similar overhead, to be state-based. A set of virtual filesystem operations (commands) will be defined in Section 3. Each of these commands have a clear and intuitive operational meaning, but are not necessarily available to the end-user. The current state of the filesystem is described by a special--called _canonical_--sequence of virtual commands, which transforms the original filesystem to the actual replica. The _update detector_ can generate this canonical sequence from the operations performed by the user on the replica (operation-based) as well as from the differences between the original and final state (state-based). On Figure 1 these sequences correspond to the information in \(\alpha\) and \(\beta\) passed to the reconciler. Filesystem synchronization must resolve all conflicts between the replicas. Conflict resolution, however, should be \"intuitively correct,\" i.e., discarding all changes made by both replicas is not a viable alternative. The majority of commercially or theoretically available synchronizers do not present a rationale to explain their concrete conflict resolution approach [16]. Two notable exceptions are [10] and [9] which describe high-level consistency philosophies. In [10] the main principles are (1) _no lost update_: preserve all updates on all replicas because these updates are equally valid; and (2) _no side effects_: such as a merge where objects unexpectedly disappear. While these principles intuitively make sense, it is easy to see that neither could possibly be upheld for every conflict; even the authors provide counterexamples. In [9] the relevant consistency requirements are worded as follows:  
* _intention-confined effect_: operations applied to the replicas by the synchronizer must be based on operations generated by the end-user; and
* _aggressive effect preservation:_ the effect of compatible operations should be preserved fully; and the effect of conflicting operations should be preserved as much as possible. These requirements are in fact variations of the OT consistency model, see for example the notion of intention preservation in [4]. (We note that the other two OT principles--convergence and causality preservation--do not apply to filesystem synchronizers.) In agreement with R1 and R2 we _declare_ what a synchronized state is, rather than present an algorithm which generates it. Our declaration can be outlined as follows. Suppose that the two replicas \(\Phi_{1}\) and \(\Phi_{2}\) are represented by the canonical sequences \(\alpha\) and \(\beta\), respectively, that is, \(\Phi_{1}=\alpha\Phi\) and \(\Phi_{2}=\beta\Phi\), where \(\alpha\Phi\) is the result of applyingthe command sequence \(\alpha\) to \(\Phi\). The _synchronized_ or _merged state_\(\Psi\) is determined by the canonical sequence \(\mu\) as \(\Psi=\mu\Phi\) such that  
* \(\mu\) is applicable to the original filesystem \(\Phi\),
* every command in \(\mu\) can be found either in \(\alpha\), in \(\beta\), or in both, and
* \(\mu\) is maximal, i.e., no canonical sequence adding more commands to \(\mu\) can satisfy both C0 and C1.