# Synchronizing Many Filesystems in Near Linear Time
## 5 Theory
### Characterizing Refluent Sets
Since the \(A_{i}\) canonical sets are refluent, we know that the input values of the commands on the same nodes are equal. Observe that if there are any conflicts among the commands, then there is a conflict of one or more of the following special types:

1. Multiple different commands on the same node with a file input value;
2. A pair of commands matching \(\langle\!\! \(n\). It is again true that the deletions do not affect winners already chosen, and that the maximality of the merger is guaranteed. Since we know that any conflict entails a conflict of one of the above types, and as we removed all such conflicts, we also know that the merger constructed is not only maximal but also conflict-free. The algorithm sketched below realizes this idea, and thus generates all mergers in randomized near linear time. It assumes that the input command sets \(A_{i}\) are canonical and refluent. **Algorithm 7** (Generating all mergers). : _Arrange the commands in \(\bigcup_{i}A_{i}\) lexicographically and add the up pointers as in Algorithm 6. Make several passes over the commands dealing with conflicts (1)-(4) as indicated above. Each pass handles commands either in top-down order of their nodes, or in the reverse bottom-up order. Handling the command at node \(n\) (which is the parent of another node in case (2)) may result in deleting those commands at node \(n\) which satisfy a certain property, deleting all commands above \(n\) which satisfy some other property, and deleting all commands below \(n\) satisfying a third property, or some combination of these possibilities. The algorithm assumes that those deletions are performed before proceeding to the next node._

_In summary, make four passes through the commands, alternating top-down and bottom-up orders, and handle cases (1) to (4) in each pass. Return the set of the final, non-deleted commands as the merger. The correctness and that the algorithm can actually create all mergers by making appropriate choices that follow from the discussion above._

The running time is linear if each pass can finish processing in linear time. To ensure this, we keep additional flags at each node noting either that required upward deletions are performed at and above this node, or that downward deletions should be performed as necessary. Upward deletions are performed immediately following the up pointers, but they abort upon encountering a node, in which the relevant flag is already set. This ensures that each node is visited at most once for this purpose, keeping the running time linear. Flags for downward deletions are checked whenever visiting a node in a top-down pass. If the flag is set on the parent, set the flag on the current node, and delete the necessary commands there. This ensures that the latest deletions are applied just in time. During bottom-up passes, downward deletions are not performed immediately, as descendant nodes are not processed again, but rather they are delayed until the next top-down pass or an additional pass is executed for this purpose. As each flag is set at most once, the running time is guaranteed to be linear. An easily accessible implementation of this algorithm in Python can be found at [[https://github.com/cirmaz/algebraic-reconciler](https://github.com/cirmaz/algebraic-reconciler)]([https://github.com/cirmaz/algebraic-reconciler](https://github.com/cirmaz/algebraic-reconciler)) (accessed on 10 May 2023). ## 7 Empirical Results

The performance of the algorithms was tested on several synthetic data sets. These sets consist of the collection of the canonical command sequences the replicas executed on a common filesystem. This initial filesystem is determined by two integer parameters \(S\) and \(T\). It has non-empty nodes on the topmost three levels only. These nodes are labeled by the paths \(/i\), \(/i/j\) and \(/i/j/k\), where \(i\), \(j\) and \(k\) are numbers between \(0\) and \(S-1\) such that \((i,j)\) and \((j,k)\) are not farther from each other modulo \(S\) than \(T\).