# Synchronizing Many Filesystems in Near Linear Time
## 5 Theory
### Characterizing Refluent Sets
The running time depends only on the total number of filesystem commands (\(x\) axis), and not on the number of replicas (color). regular tree-like structure of filesystem paths. Both of these shortcomings, and how to circumvent them, are discussed below. Filesystem synchronization starts with _update detection_ run locally, which extracts information encoding the state of the modified replica as discussed in Section 3.1. In the ATF framework, this information is a _canonical command set_ describing how to construct the replica from the original filesystem. The task of the synchronizer is to create a common, merged filesystem after considering what changes have been applied to the replicas. In the ATF framework, this task amounts to creating another canonical command set, the _merger_, which transforms the original filesystem into the merged filesystem. What this merger can be is described by two simple and intuitively appealing principles: the _intention-confined effect_, where operations in the merger should come from those supplied by the replicas, and _aggressive effect preservation_, where the merger should contain as many of those commands as possible. Definition 5 formalizes this idea and _defines_ what a synchronized state is. Sections 3.3 and 3.5 discuss that this goal-driven definition automatically implies many operational properties such that a merger command set always defines a valid synchronized state; synchronization can be achieved from the local copy by rolling back some of the local commands and executing additional ones originating from other replicas. Section 3.7 shows that with minimal effort the synchronization paradigm can be extended to tolerate replicas which do not lock their filesystem--allowing for asynchronous or optimistic synchronization [9]. Even replicas missing a synchronization cycle can later upgrade to the synchronized state. Algorithms described in Section 4 give a high-level description of a proof-of-concept implementation at [[https://github.com/csirmaz/algebraic-reconciler](https://github.com/csirmaz/algebraic-reconciler)]([https://github.com/csirmaz/algebraic-reconciler](https://github.com/csirmaz/algebraic-reconciler)) (accessed on 10 May 2023). Algorithm 5 creates a merger in linear time after sorting the canonical sets sent by the replicas. While this algorithm can make some nondeterministic decisions, it cannot generate all possible mergers. Two nondeterministic algorithms which can do so are sketched in Section 6; both of them run in near linear time. The first algorithm uses the fact that Algorithm 5 can recognize mergers. It first creates a random subset of the supplied commands blindly, and then checks if it is a merger. The second one, described as Algorithm 7, is more elaborate. It exploits the structure of refluent command sets, and can assist in the synchronization process by highlighting the consequences of different conflict resolutions. ### Node Attributes

The important task of consolidating different versions of the same document (file value) was not considered, as processing the internal structure of file contents is outside the scope of filesystem synchronization. Files different in content are considered to be different, and the synchronization algorithm forces the choosing of one or the other. There is, however, an easy way of incorporating third-party content-merging applications. This can be done by pretending that there is only one possible file content, and using the ATF framework to synchronize the _structure_ of the filesystems. When it becomes clear which nodes contain file values, check for the commands which modified the actual content there, and use the external application to determine the final file content. A similar approach can handle node attributes by considering the changes made by the replicas at some node and consolidating them. This approach, however, should be followed carefully. To illustrate the problem, consider a directory at node \(n\), which originally had the \"private\" attribute.