# Synchronizing Many Filesystems in Near Linear Time
## 1 Introduction and Related Works  
Synchronizing diverged copies of some data stored on a variety of devices and/or at different locations is an ubiquitous task. The last two decades saw a proliferation of practical and theoretical works addressing this problem. According to [1], \"file synchronization is a feature usually included with backup software in order to make is easier to manage and recover data as and when required\". File synchronization is usually delivered through cloud services. Dedicated file synchronizing solutions frequently come with additional tools not just for managing the saved data but also to allow for file sharing and collaboration with stored files and documents. These cloud storage services are easily accessible for the end user because the service front ends are very well integrated into web clients as well as desktop and mobile environments. Simple user interfaces hide the complex and sophisticated service back ends [2]. Collaboration services are frequently integrated into the \"cloud storage\" environment. For example, Google Docs is an application layer integrated into Google Drive storage, Office 365 is integrated with One Drive storage and Dropbox Paper service is an extension of Dropbox storage. To address the emerging challenges in the more specific fields of distributed data storage and collaborative editors, two competing theoretical frameworks emerged: operational transformation (OT) and conflict-free (or commutative) replicated data types (CRDT). OT appeared in the seminal work of [3] and was refined later, among others, in [4; 5; 6]. The main applications are collaborative editors, the most notable example being Google Docs [7]. CRDT emerged as an alternative with a stronger theoretical background, see [8; 9]. Both OT and CRDT have been applied successfully in a variety of synchronization tasks,including file synchronizers [6; 10; 11]. Finding a provably correct, subquadratic synchronization algorithm, however, has remained one of the main open problems both in OT and CRDT [12]. The algebraic theory of filesystems [13; 14] introduced algebraic manipulations of filesystem commands, and provided the foundations for automated checking of certain filesystem properties. It is reminiscent of both OT [6] and CRDT inasmuch as, instead of pure traditional filesystem commands, it uses operations enriched with contextual information. While these operations are not fully commutative--as would be requested by CRDT [15]--the non-commutative parts can be isolated systematically and handled separately. In [14], this framework is used successfully to create a provably correct theoretical filesystem synchronizer for two replicas together with a complete analysis of all possible synchronized states. The present work extends [14] significantly by the following:  
* Providing the theoretical foundation for synchronizing an _arbitrary number_ of replicas;
* Developing, for the first time, a provably correct synchronization algorithm which works in _linear time_ after an initial sort, and thus in subquadratic total running time;
* Allowing _asynchronous usage_, namely, after requesting synchronization, the local replicas need not be locked;
* Allowing for _late corners_ when a replica can be upgraded to the synchronized state without providing the local changes;
* Generalizing the traditional tree-like filesystem skeleton to arbitrary _acyclic graphs_, thus extending the applicability of the synchronization algorithm. In this paper, we will use the term _near linear_ to mean \"linear up to a logarithmic factor\". Thus, sorting requires near linear time [16], and the total time required by the above synchronization algorithm is also near linear.