# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 1 Introduction and Related Work  
This work is a comprehensive treatment of filesystem synchronization and conflict resolution on a simple but powerful theoretical model of filesystems. Synchronizing diverged copies of some data stored on a variety of devices and locations is an important and ubiquitous task. The last two decades have seen tremendous advancement, both theoretical and practical, in the closely related fields of distributed data storage [1, 2] and group editors [3, 4]. This progress has been based on, and has expanded significantly, two competing theoretical frameworks: Operational Transformation (OT) and Conflict-free Replicated Data Types (CRDT). OT appeared in the seminal work [5] and was refined later in [4]. The general idea is that operations are enriched with the context in which they were generated. Before applying them, they are transformed depending on the context of their origin and the context where they are to be applied. Main applications are collaborative editors, the most notable example being Google Docs [6]. The core concept of CRDT is commutativity, see [1, 2]. Basic data types with special operators are devised so that executing the operators in different orders yield the same results. Examples are counters or sets with add and delete operators. The basic types are used as building blocks in more complex applications such as collaborative editors [7], the commercial product Riak [8], and others. Both OT and CRDT have been successfully applied in a variety of synchronization tasks [9, 10]. Filesystem synchronization, however, fits very poorly into these frameworks, mainly because it works under a completely different modus operandi: constant, low latency communication in OT and CRDT versus a single data exchange in filesystemsynchronization; frequent loose synchronization with eventual convergence requirement versus a single but complete synchronization; small number of differences versus significant structural differences accumulated during an extended time period; and so on. Consequently, for a theoretical investigation of filesystem synchronization, we follow a traditional framework instead, described in e.g., [11] and depicted in Figure 1 adapted from [12]. Two identical replicas of the original filesystem \(\Phi\) are updated independently, yielding the divergent replicas \(\Phi_{1}\) and \(\Phi_{2}\). In the state-based case the _update detector_ receives the original (\(\Phi\)) and the current (\(\Phi_{1}\) or \(\Phi_{2}\)) states, and generates the update information \(\alpha\) (or \(\beta\)) describing the differences between the original filesystem and the replica. In the operation-based case the update decoder has access to the performed operations \(\alpha_{0}\) (\(\beta_{0}\)) only. The _reconciler_ receives the information provided by the update detectors and generates the synchronizing instructions \(\alpha_{1}\) and \(\beta_{1}\), respectively. These instructions, applied to the replicas \(\Phi_{1}\) and \(\Phi_{2}\), create the identical _merged state_\(\Psi\). In order to reach such a common synchronized state, existing theoretical and practical filesystem synchronizers, such as [13; 14; 10; 15; 16; 17], apply some conflict-resolution strategy. They identify all (or some) of the conflicts, then apply their strategy to the conflicts one at a time. These algorithms are typically fixed and defined by some rationale or heuristics, or dictated by the underlying technology. In contrast, we _define what comprises a synchronized state_. Intuitively, it is a maximal consistent merger of the replicas, meaning that no further changes can be applied to the merged state from those that were applied to the replicas during the update phase. Then we proceed to prove that every such maximal state (and only these states) can be reached by resolving the conflicts in some order.