# Synchronizing Many Filesystems in Near Linear Time
## 5 Theory
### Characterizing Refluent Sets
Replica \(A\) changes this attribute to \"public\", while replica \(B\), under the impression that the directory is private, creates a file under it. When merging the attributes, the change at node \(n\) is carried over, making the directory publicly available. This, however, is clearly unacceptable. It is an interesting open problem to incorporate node attributes into the ATF synchronization paradigm. ### Filesystems on Directed Acyclic Graphs

From the user's perspective, a (hard or soft) _link_ between the nodes \(n\) and \(n^{\prime}\) is a promise, or a commitment, that the filesystem at and below \(n\) is exactly the same at and below \(n^{\prime}\). In other words, the filesystem acts as if the nodes \(n\) and \(n^{\prime}\) in the filesystem skeleton are glued together. If the filesystem has many links and the links do not form loops, then after this gluing, the skeleton becomes a directed acyclic graph (DAG) with many sources (the roots in the original skeleton). The gluing works in the other direction, too: given any DAG with one or more sources, it can be \"unfolded\" into a forest. The paths of a tree-like filesystem can be identified with the directed paths starting from a source, and two nodes are \"linked\" if the directed paths in the DAG lead to the same vertex. A DAG vertex \(v\) represents the collection of all nodes in the unfolded filesystem, which are determined by the directed paths in the DAG, which lead to \(v\). Two nodes of this unfolded filesystem are _equivalent_, written as \(n_{1}\simeq n_{2}\) if the corresponding directed DAG paths lead to the same vertex. It is clear that \(\simeq\) is an equivalence relation, and factoring the filesystem by \(\simeq\) yields the DAG. If every vertex in the DAG has a finite indegree, then the equivalence classes are also finite. Operations on a DAG-based filesystem can be mimicked on the unfolded filesystem by simply requesting that an operation performed on the DAG vertex \(v\) be done on all nodes represented by \(v\). Similarly, a command set \(A\) on the unfolded filesystem corresponds to the command set \(A/\simeq\) on the DAG-based filesystem if with every command \(\sigma\in A\) all commands \(\simeq\)-equivalent to \(\sigma\) are also in \(A\). We call these command sets \(\simeq\)-invariant. Requesting all command sets to be \(\simeq\)-invariant, the claims, propositions and theorems in this paper remain true (remark that in this case, the definition of a merger should require \(M\) to be \(\simeq\)-invariant). Similarly, all algorithms continue to work, but they must handle not commands but sets of \(\simeq\)-equivalent commands. Consequently, time estimates are no longer valid. In summary, our results and algorithms remain valid on filesystems based on arbitrary DAGs. It is an open question as to whether the algorithms can be implemented in linear time in the general case. All authors contributed equally to this work. All authors have read and agreed to the published version of the manuscript. The work of the second author (LCs) was partially supported by the ERC Advanced Grant ERMiD. The Python program generating the synthetic data sets our algorithms were tested on is available 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 25 May 2023). [PERSON] contribution for devising Algorithm 1 is gratefully acknowledged. The authors declare no conflict of interest. ## References

* (1) [PERSON]; [PERSON] Best File Syncing Solutions of 2023, 2023. Available online: [[https://www.techradar.com/best/best-file-syncing-solution](https://www.techradar.com/best/best-file-syncing-solution)]([https://www.techradar.com/best/best-file-syncing-solution](https://www.techradar.com/best/best-file-syncing-solution)) (accessed on 10 May 2023). * (2) [PERSON]; [PERSON] Cloud storage services for file synchronization and sharing in science, education and research. _Future Gener. Comput.