# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 6 Synchronization by Conflict Resolution
### The Synchronization Algorithm
#### Complexity of Algorithm 1  
Apart from the time and space requirements of Algorithm 2, the five operations here require computing the union, intersection and difference of sets. Using hashing techniques, these operations can be performed both in time and space linear in the input size. Inputs of the main Algorithm 2 are the _disjoint_ refluent canonical sets \(A^{o}\) and \(B^{o}\), and the optional target merger \(M^{o}\) of \(A^{o}\) and \(B^{o}\). The goal is to produce a merger \(M\). If \(M^{o}\) is given, then, at the end, \(M\) and \(M^{o}\) must be equal. The algorithm maintains two command sets \(A\) and \(B\), initially set to \(A^{o}\) and \(B^{o}\). During execution these sets satisfy the following invariants:  
1. \(A\Subset A^{o}\), \(B\Subset B^{o}\), consequently \(A\) and \(B\) are refluent canonical subsets of \(A^{o}\) and \(B^{o}\);
2. all mergers of \(A\) and \(B\) are mergers of \(A^{o}\) and \(B^{o}\);
3. if \(M^{o}\) is specified, then \(M^{o}\) is a merger of \(A\) and \(B\). Figure 6: Outline of Algorithm 1. Given the input \((A^{o},B^{o},M^{o})\), extract the common part \(C\) of \(A^{o}\) and \(B^{o}\), and call Algorithm 2 with the reduced sets. Finally, add \(C\) to the returned \(M^{\prime}\) to generate the output \(M\). In each iteration one or more commands are deleted either from \(A\) or from \(B\) until only the commands of the merger remain. **Algorithm 2** (Synchronization of disjunct sets). : _Initialize:_ Set \(A^{o}\to A\) and \(B^{o}\to B\). _Iterate:_ Choose \(\sigma\in A\) and \(\tau\in B\) such that \((\sigma,\tau)\) is a conflict. If no such pair exists, go to Finish. If \(M^{o}\) is given, choose a conflict so that either \(\sigma\) or \(\tau\) is in \(M^{o}\). _Conflict resolution:_ Out of \(\sigma\) and \(\tau\), choose the _winner_ and the _loser_ commands. If \(M^{o}\) is given, let the winner be the one in \(M^{o}\). If \(\sigma\) is the winner, delete all commands from \(B\) which are in conflict with \(\sigma\) (including \(\tau\)). If \(\tau\) is the winner, delete all commands from \(A\) which are in conflict with \(\tau\). Go back to Iterate. _Finish:_ Return \(A\cup B\) as the merger. Execution of Algorithm 2 is illustrated in Figure 5. The initial command sets are \(A=\{\sigma_{1},\ldots,\sigma_{5}\}\) and \(B=\{\tau_{6},\ldots,\tau_{5}\}\). In the first iteration \(\tau_{7}\in B\) is the winner; therefore, commands in \(A\) which are in conflict with \(\tau_{7}\) (\(\sigma_{1}\) and \(\sigma_{2}\)) are removed from \(A\). In the next iteration the winner is \(\sigma_{4}\in A\), and \(\tau_{9}\) and \(\tau_{5}\) are removed from \(B\). In the last iteration \(\sigma_{3}\) is removed from \(A\), thus the remaining sets are \(A=\{\sigma_{4},\sigma_{5}\}\) and \(B=\{\tau_{6},\tau_{7},\tau_{8}\}\). The returned merger is \(A\cup B\). **Correctness of Algorithm 2. ** After the initialization step all three invariants hold. The algorithm terminates as in each iteration the total number of remaining conflicts strictly decreases. When it terminates, the returned set \(A\cup B=M\) is a merger of the original command sets \(A^{o}\) and \(B^{o}\). This is because at that point there are no conflicts between \(A\) and \(B\), thus, by Corollary 1, \(M\) is a merger of \(A\) and \(B\)--in fact, the only one--, and then the second invariant guarantees that \(M\) is also a merger of \(A^{o}\) and \(B^{o}\). If \(M^{o}\) was submitted to the algorithm, then the third invariant ensures \(M=M^{o}\). Thus we only need to show that the iteration preserves all three invariants. Suppose there is a conflict \((\sigma,\tau)\) between \(A\) and \(B\), and the winner of the conflict is \(\sigma\in A\). _Invariant 1_. Commands in conflict with \(\sigma\) are deleted from \(B\), thus \(B\) is replaced by the set  
\[B^{\text{ok}}_{\sigma}=\{\tau^{\prime}\in B:\;(\sigma,\tau^{\prime})\text{ is not a conflict}\}.\]  
Proposition 14 (see the discussion following the proof) and the invariant imply \(B^{\text{ok}}_{\sigma}\Subset B\Subset B^{o}\).