# Synchronizing Many Filesystems in Near Linear Time
## 3 Filesystem Synchronization
### Mergers Can Be Created via Conflict Resolution  
Synchronizers typically work by identifying and resolving conflicts until no conflicts remain. While Definition 5 specifies the synchronized state directly, clearly two commands are in conflict if they cannot occur together in the same canonical set. In our case, however, a weaker notion of conflict also works.  
Definition 6: The commands \(\sigma,\tau\in\bigcup_{i}A_{i}\) are in conflict if either of the following is true:  
1. They are different commands on the same node.
2. The node of \(\sigma\) is above the node of \(\tau\), \(\sigma\) creates a non-directory and \(\tau\) creates non-empty content.  
Comnands \(\tau=\langle\sfrac{\mathsf{a}}{\mathsf{b}}\sfrac{\mathsf{a}}{\mathsf{b}}, \sfrac{\mathsf{b}}{\mathsf{z}}\rangle\) and \(\rho_{2}=\langle\sfrac{\mathsf{a}}{\mathsf{b}}\sfrac{\mathsf{b}}{\mathsf{z}}, \sfrac{\mathsf{b}}{\mathsf{z}}\rangle\) from the example above are in conflict, as they are different commands on the same node. Command \(\sigma_{3}=\langle\sfrac{\mathsf{a}}{\mathsf{a}},\sfrac{\mathsf{b}}{\mathsf{ z}},\sfrac{\mathsf{b}}{\mathsf{z}}\rangle\) creates a non-directory; thus, it is in conflict with every command below it, which creates a file--that is, all commands in \(A_{2}\) and \(A_{3}\)--but it is not in conflict with \(\sigma_{1}=\langle\sfrac{\mathsf{a}}{\mathsf{b}}\sfrac{\mathsf{b}}{\mathsf{ c}},\sfrac{\mathsf{b}}{\mathsf{c}},\sfrac{\mathsf{b}}{\mathsf{c}}\rangle\) and \(\sigma_{2}=\langle\sfrac{\mathsf{a}}{\mathsf{b}},\sfrac{\mathsf{b}}{\mathsf{ D}},\sfrac{\mathsf{b}}{\mathsf{D}},\sfrac{\mathsf{b}}{\mathsf{D}}\rangle\), which create empty content.  
By Proposition 2, canonical sets (and thus mergers) do not have conflicts at all, while Theorem 4 claims that a maximal command set of \(\bigcup_{i}A_{i}\) without conflicts is a merger. The synchronizer, having received the command sets \(A_{i}\), can create a _conflict graph_, whose vertices are the commands in \(\bigcup_{i}A_{i}\) and edges connect conflicting commands. Mergers correspond to the maximal independent vertex sets of this graph. Creating a merger via conflict resolution can therefore be performed using the following procedure: pick an edge of the graph representing a conflict between, say, \(\sigma\) and \(\tau\). Choose either \(\sigma\) or \(\tau\) as the winner, and delete all vertices connected to the winner (i.e., those vertices which cannot be in the same merger as the winner). When there are no more edges, the remaining vertices form a maximal independent set, a merger.  
Using this conflict graph, the synchronizer can make smart decisions, a feature which is painfully missing in commercial and other theoretical synchronizers. When choosing the conflict to be resolved and the winner of the conflict, the decision can take into account not only local information (the conflicting command pair) but also the effect of the decision on other conflicts.  
Creating and manipulating the conflict graph can be done in quadratic time [28]. As this graph has a very special structure and not too many edges, the actual running time could be better. As our main interest in this paper was developing subquadratic algorithms, we did not pursue this line of research further. Using the conflict resolution strategy, Algorithm 5 in Section 4 creates a merger in near linear time. Unfortunately, this algorithm, as explained later, cannot generate all mergers in nondeterministic linear time. For that task, we need further ideas explored in Section 6.