# Synchronizing Many Filesystems in Near Linear Time
## 5 Theory
### Characterizing Refluent Sets
Using Algorithm 1, add up pointers both for the commands and nodes, meaning that the up pointer of command \(\sigma\in A_{i}\) points to the command in \(A_{i}\), which is directly above \(\sigma\) (if there is such a command in \(A_{i}\)), while the up pointer at node \(n\) points to the parent of \(n\) if there is any node above \(n\) in the node set of \(\bigcup_{i}A_{i}\). Fill in the bitmaps \(I_{n}\) stored at node \(n\), the sets of which the commands belong to._  
_All four conditions of Theorem 3 can be checked by looping through the commands in lexicographic order. For condition (b), note that the precondition implies that the up pointer is filled in at \(n\), and it is enough to check that it points to \(\dagger n\). Condition (c) does not need to be checked where no up pointer points to \(\dagger n\), as then, all index sets below it are empty._  
The total processing time after sorting is clearly linear if bitmap operations can be implemented in constant time. Otherwise, \(I_{n}\subseteq I_{\dagger n}\) can be checked in time proportional to \(|I_{n}|\) (which still gives a linear total time) by following the command up links at node \(n\). Checking \(I_{\dagger n}\subseteq I_{n}\) can be performed by counting the number of command up links at node \(n\) and comparing it to the total number of elements in \(I_{\dagger n}\). ```
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 for\(i\) from 1 to number of setsdo determine the sets \(I_{n}\)
5 for each command in sets[\(i\)] do
6 command.node.index \(\leftarrow\) command.node.index \(\cup\{i\}\)
7
8 end for
9
10 end for
11
12 for each command in sequence do
13 if not the first command and previousCommand.node = command.node
14 and previousCommand.input \(\
eq\) command.input then
15 return false not refluent due to condition (a)
16
17 end if
18 if command.up \(\
eq\)\(\perp\)then
19 if command.up.node is not the parent of command.node then
20 return false not refluent due to condition (b)
21
22 end if
23
24 end if
25 if command.input \(\
eq\)\(\mathbb{O}\)then not empty
26 if command.node.index is not a superset of command.up.node.index then
27 return false not refluent due to condition (d)
28
29 end if
30
31 end if
32
33 return true the command sets are refluent

### Mergers by Conflict Resolution

This section presents a proof of the claim that the mergers are exactly the maximal conflict-free subsets. Recall from Definition 6 that two different commands in \(\bigcup_{i}A_{i}\) are in conflict if either (a) they are on the same node, or (b) they are on comparable nodes, the node on the higher node creates a non-directory and the command on the lower node creates a non-empty content. Proposition 2: _There are no conflicts in a canonical set._

Proof: A canonical set contains at most one command on each node, so assume \(\sigma\) and \(\tau\) are on comparable nodes. Then, there is an \(\ll\)-chain between them (see Definition 3); thus, either \(\sigma\ll\dots\ll\tau\), or \(\tau\ll\dots\ll\sigma\). In both cases, either the command on the higher node creates a directory, or the command on the lower node creates an empty content. Theorem 4: _Suppose the command sets \(A_{i}\) are jointly refluent. \(M\subseteq\bigcup_{i}A_{i}\) is a merger if and only if \(M\) is maximal without conflicts._

Proof: By Proposition 2, a merger does not contain conflicts; thus, it suffices to show that a maximal conflict-free set \(M\) is canonical. \(M\) contains, at most, one command on each node by condition (a) of Definition 6. Let \(\sigma\), \(\tau\in M\) be on nodes \(n\) and \(m\), respectively, such that \(n\) is above \(m\). Moreover, let \(\sigma\in A_{i}\) and \(\tau\in A_{j}\). We want to show that there is a \(\ll\)-chain in \(M\) between \(\sigma\) and \(\tau\). We know that \(\sigma\) and \(\tau\) are not in conflict.