# Synchronizing Many Filesystems in Near Linear Time
## 1 Introduction and Related Works
This paper follows the traditional paradigm of filesystem synchronization described in, for example, [17] and illustrated in Figure 1. The starting point is a set of identical copies of the same filesystem, possibly stored at different locations, on different hardware and architectures (cloud servers, mobile devices, laptop and desktop computers with various operating systems) or using different software implementations (e.g., ext4, btrfs, ZFS, NTFS, APFS, or database file systems). Each of these replicas is edited (modified) locally. At a certain time, the diverged copies call for _synchronization_ by sending a description of the diverged state to a central server. After receiving the requests, the server computes filesystem commands, which transform each replica into a common synchronized state, and send them back to the replicas. The replicas execute the received commands on their local copy, transforming all diverged copies into a new identical synchronized state. At that point, the synchronization cycle can start again. Synchronizers typically require locking the replicas during the whole synchronization process, meaning that no modifications are allowed after the synchronization request is sent (the locked time period is indicated by the dotted lines on Figure 1). Asynchronous, or optimistic synchronization allows additional local modifications after the synchronization request is sent as depicted on the top of Figure 2. When the synchronization commands  
Figure 1: The synchronization cycle. Identical copies of the same filesystem are edited independently. Each replica sends the locally created update information to the synchronizer, which returns the commands to be executed on the local copy to update it to a common synchronized state. arrive from the server, those commands are modified to reflect the additional changes, and then applied to the replica. The result should be the same as when performing synchronization without the additional changes, and then applying them to the synchronized filesystem afterwards--as indicated at the bottom of the figure. The main focus of this paper is filesystem synchronization, or the synchronization of data stored in the nodes of a tree or directed acyclic graph. The stored data are considered to be an indivisible unit, and the task of consolidating different versions of the same data is not considered. It should be solved by other methods specifically tailored to this task. Some practical aspects of data synchronization are not touched and are out of the scope of this paper. Managing user access and permissions, when and how to allow file sharing and collaboration are especially important due to security considerations [1]. Additionally, file synchronization should use very strict security protocols to ensure that data are safely protected and secured at all times and to make data leaks and malicious access less likely. Synchronizers should also minimize network traffic. Unlike the popular Isync utility [18] available for comparing and synchronizing files, there is currently no such \"middleware\" utility for general datasets [19]. Hopefully our work is a small step in that direction. The rest of this paper is organized as follows. Section 2 recalls the building blocks of the algebraic theory of filesystems, including the filesystem model, the augmented filesystem commands and their basic properties. This section does not contain new results, and its purpose is to give the reader a comprehensive summary of the topic, on which the rest of the paper relies. For more intuition, explanation and examples, please consult [14]. Section 3 is a high-level overview of how filesystem synchronization can be handled in the algebraic framework. This section _defines_ what constitutes a synchronized state of several diverged replicas, rather than providing a method of creating it. The definition automatically guarantees many desired and required properties of the merged filesystem, an indication of the strength and adequacy of the algebraic framework.