# Synchronizing Many Filesystems in Near Linear Time
## 5 Theory
### Characterizing Refluent Sets
The filesystem contains different files at the non-empty nodes \(/i/j/k\), and contains directories at all other non-empty nodes. Typical parameter values are \(T=2\) and \(S=10\). The set of command sequences to be synchronized also depends on the number of users (replicas), which varies between \(2\) and \(S-1\). User \(u\) for \(0\leq u\leq S-1\) makes the following extensive changes on the filesystem:

1. Deletes all existing files at \(/i/u/k\) for all \(i\) and \(k\);
2. Removes (the now empty) directories at \(/i/u\) for all \(i\);
3. For each \(x\) in \((u-1,u,u+1)\) modulo \(S\) and for all \(i\) and for all \(j\
eq u\) changes the file at \(/i/j/x\) (if exists) to a directory;Under each newly created directory creates \(S\) new files with unique content. These files are placed at the nodes with paths \(/i/j/\times/l\), where \(0\leq l<S\). Depending on the parameter values \(S\) and \(T\), the number of necessary filesystem commands achieving these changes varies between 100 and 8000 per user. The instructions were chosen so that there are both a large number of conflicts and also a large number of non-conflicting command pairs, forcing any conflict-based synchronizer to spend quadratic time, even to check the existence of conflicts. The command sequences have many symmetries to ensure that the order in which the commands or command pairs are processed has little or no effect on the running time. In the experiments, we tried 20 different filesystems with the parameter \(S\) running from 5 to 14 (inclusive), \(T\) running from 1 to \(\left[(S-1)/2\right]\), and the number of users running from 2 to \(S-1\), inclusive. The general synchronization Algorithm 7 from Section 6 was called on the resulting collection of sequences to generate the first and the first three possible synchronized states. Each run was repeated 10 times to smooth out the effects of other programs running on the same server. Figure 3 depicts the average time used to generate a single synchronizing command set. The input size on the \(x\) axis is the total number of different commands in the sequences to be synchronized. The average running time on the \(y\) axis is in seconds. The non-optimized Python program was running on a desktop machine with an Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz processor and 8 G memory. The different colors represent the number of replicas. The results confirm that the running time is subquadratic in the total input size and does not depend on the number of replicas. ## 8 Conclusions

This paper presented a provably correct synchronization algorithm running in subquadratic time, which can synchronize an arbitrary number of replicas. The existence of such an algorithm was a long-standing open problem [12] in the fields of operation transformation (OT) [5] and conflict-free replicated data types (CRDT) [9]. Our work is based on the algebraic theory of filesystems (ATF) [14], which, in many respects, resembles both OT and CRDT. Instead of traditional filesystem commands, ATF uses operations enriched with contextual information similarly to OT and CRDT. It also favors commutativity, but instead of requesting all operations to be commutative, their non-commutative part can be isolated systematically and handled separately. As a consequence, similarly to OT and CRDT, ATF can deal with command sets instead of sequences, where the execution order is not specified, but the semantics of executing the commands _in some order_ is defined unambiguously. The underlying filesystem model, while arguably simplistic, retains the most important high-level and platform-independent properties of real-life filesystems; see Section 2.1 for a more detailed discussion. The two most prominent omissions of this model are the lack of _directory attributes_ (the model handles all directories as equal), and _links_ breaking the

Figure 3: Running time for generating the synchronized state on several synthetic data sets.