# Synchronizing Many Filesystems in Near Linear Time
## 3 Filesystem Synchronization
### Synchronization  
The central server, having received the canonical sets from the replicas describing the local changes, must resolve all conflicts between the updates and generate a common, synchronized filesystem. Conflict resolution should be intuitively correct; thus, discarding all changes made by the replicas is not a viable alternative. While the majority of practical and theoretical synchronizers do not present any rationale to explain their specific conflict resolution approach [12], two notable exceptions [6; 10] describe high-level consistency philosophies. In Ref. [10], the main principles are _no lost update_ (preserve all updates on all replicas because these updates are equally valid) and _no side effects_ (do not allow objects to unexpectedly disappear). While these principles make intuitive sense, neither can possibly be upheld for every conflict. In Ref. [6], the relevant consistency requirements are _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 [4]. Note that the other two OT principles--convergence and causality preservation--do not apply to filesystem synchronizers. In keeping with the prescriptive nature of the above principles, we proceed by _defining_ what a synchronized state is, rather than creating it by some ad hoc method. Suppose that the original filesystem is \(\Phi\), and the modified filesystem at the \(i^{\text{th}}\) replica is \(\Phi_{i}=A_{i}\Phi\), where \(A_{i}\) is the canonical set submitted as input to the reconciler. The synchronized or _merged state_\(\Psi\) is determined by the canonical set \(M\) called the _merger_ such that \(\Psi=M\Phi\), where \(M\) satisfies the following two conditions:  
1. Every command in \(M\) is submitted by one of the replicas;
2. The canonical set \(M\) is maximal with respect to the first condition. The first condition ensures that the synchronization satisfies the _intention-confined effect_: there are no surprise changes in the merged filesystem. The _aggressive effect preservation_ is guaranteed by the second condition. As \(M\) is maximal, it preserves as much of the intention of the users as possible. In general, there can be many different mergers satisfying these conditions. The reconciler must choose one of them either automatically using some heuristics, or manually as instructed by the user. Observe that the canonical sets \(A_{i}\) describing the local changes are jointly refluent (see Section 2.5), as all of them can be (and were) applied to the original filesystem \(\Phi\). The formal definition of a merger is as follows. **Definition 5** (Merger). : _The merger of the jointly refluent canonical sets \(A_{1},\ldots,A_{k}\) is a maximal canonical set \(M\subseteq\bigcup_{i}A_{i}\). The corresponding synchronized state of the replicas \(A_{1}\Phi,\ldots,A_{k}\Phi\) is \(M\Phi\)._  
This definition requires the absolute minimum. Due to its simplicity, it is clear, intuitively appealing, and captures the desired properties of a synchronized state. It remains to be seen whether it is also sufficient or an oversimplification. Surprisingly, this definition is indeed sufficient. Mergers provided by Definition 5 satisfy many additional desirable properties without any further requirements. Some of these properties are discussed in the next subsections. For the rest of this section, we fix the canonical set \(A_{i}\) and the original filesystem \(\Phi\) so that the current state of replica \(i\) is the valid filesystem \(\Phi_{i}=A_{i}\Phi\). Consequently, none of the sets \(A_{i}\) breaks \(\Phi\), and therefore the command sets \(A_{i}\) are jointly refluent. As an example, suppose that \(\Phi\) contains directories at /a, /a/b, and single file at /a/b/c.