# Synchronizing Many Filesystems in Near Linear Time
## 4 Algorithms
### Generating a Merger in Near Linear Time  
Theorem 4 characterizes a merger of the jointly refluent command sets \(A_{i}\) as a maximal subset of \(\bigcup_{i}A_{i}\) without conflicts. This characterization can be turned into a greedy algorithm which generates a merger in near linear time. Actually, the algorithm finds a maximal independent vertex set of the conflict graph (discussed in Section 3.6) exploiting some special properties of this graph. According to Definition 6, commands \(\sigma\) and \(\tau\) are in conflict if either they are acting on the same node; or if their nodes are comparable, the upper command creates a non-directory, and the lower command creates a non-empty value. Loop through the commands in \(\bigcup_{i}A_{i}\) in a top-down order. At command \(\sigma\), if \(\sigma\) is marked as being in conflict with some earlier command, then skip it. Otherwise, keep \(\sigma\) and mark commands which are in conflict with \(\sigma\) as conflicting. It follows that if \(\sigma\) is not skipped, it is not in conflict with commands preceding it, and so conflicting commands are either on the same node, or below the node of \(\sigma\). To achieve the desired speed, instead of scanning all subsequent commands immediately, we use lazy bookkeeping. In essence, if \(\sigma\) is selected, we flag its node to remember to delete conflicting commands on descendant nodes. At each subsequent node, we check whether its parent has this flag. If yes, we flag that node as well and process any conflictsaccordingly. By Theorem 3, the node set of jointly refluent canonical sets is connected; thus, this flag percolates properly to the descendants. **Algorithm 5** (Generating a merger, Code 5). : _The inputs are the jointly refluent canonical sets \(A_{i}\); the output is a merger \(M\). Sort the commands in \(\bigcup_{i}A_{i}\) lexicographically and then use Algorithm 1 to create the up pointers. Add a \"delete conflicts down\" flag to the node of each command, initially unset._  
_Loop through the commands of \(\bigcup_{i}A_{i}\) in lexicographic order. At command \(\sigma\) at node \(n\), check if the node of the command up points to having the \"delete conflicts down\" flag set. If yes, then set this flag at \(n\) as well. If, additionally, \(\sigma\) creates some non-empty content (it is in conflict with a final command above it), then delete \(\sigma\). If \(\sigma\) is not deleted, then mark it as \"final\" and delete all subsequent commands on the same node \(n\). If \(\sigma\) is marked \"final\" and it creates a non-directory value, set the \"delete conflicts down\" flag at \(n\)._  
_Commands marked as \"final\" form a maximal command set without conflicts; thus, they form a merger._  
```
1 sequence\(\leftarrow\)union of commands in the command sets
2-sort sequence lexicographically by the nodes of the commands
3-add up pointers using Algorithm 1
4 foreachcommand in sequence do
5 ifcommand.node\(=\)deleteOnNode then
6 continue
7
8 ifcommand.up\(\
eq\bot\)andcommand.up.node.delConflictsDown then
9 command.node.delConflictsDown\(\leftarrow\)true
10 ifcommand.output\(\
eq\mathbb{O}\)then
11 continue
12 end if
13
14 end if
15
16
17 merger\(\leftarrow\)merger\(\cup\){command\(\}\)
18 deleteOnNode\(\leftarrow\)command.node
19 ifcommand.output\(\
eq\mathbb{D}\)then
20 command.node.delConflictsDown\(\leftarrow\)true
21
22
23 end if
24
25 end if
26
27 returnmerger
```  
**Code 5**. Given a set of jointly refluent canonical command sets, generate a merger. Unfortunately, this algorithm cannot generate all possible mergers. The only non-deterministic choice it can make is picking the winner among commands on the same node, which are not in conflict with previous commands. (Algorithm 5 chooses the first such command). Otherwise, when the algorithm encounters a command for the first time, it puts it into the final list, even if there might be mergers which do not contain this command. The more sophisticated Algorithm 7 generates all mergers in nondeterministic near linear time.