Skip to Main content Skip to Navigation
Conference papers

Syncpal: A Simple and Iterative Reconciliation Algorithm for File Synchronizers

Abstract : Today file synchronizers are tools often used to facilitate collaboration scenarios and data management across multiple devices. They replicate the file system, e.g. from a cloud storage to a device disk, achieving convergence by only transmitting detected changes. A popular variant available in a plethora of products are state-based file synchronizers such as the Dropbox client. They detect operations by computing the difference between a previously persisted state and the respective current state. However, state-based synchronization is difficult because we need to detect and resolve conflicting operations as well as the propagation order of non-conflicting operations. This work presents Syncpal, an algorithm that reconciles two divergent file systems using an iterative approach. It first handles conflicts, one at a time, making sure that resolving one conflict does not negatively affect other ones, while avoiding conflicts whenever possible. It then finds order dependencies (and breaks cycles) between the remaining non-conflicting operations to avoid the violation of operation preconditions during propagation. This work is relevant for file synchronizer researchers and developers who want to improve their products with an algorithm whose iterative nature reduces the overall complexity and the probability of bugs. In addition to our proposed algorithm and a formal analysis of the underlying problem, our validation approach for the proposed algorithm includes the presentation of a full-scale implementation of an exemplary file system model.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-02319573
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, October 18, 2019 - 9:48:04 AM
Last modification on : Tuesday, October 19, 2021 - 12:49:45 PM
Long-term archiving on: : Sunday, January 19, 2020 - 1:40:34 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Marius Shekow. Syncpal: A Simple and Iterative Reconciliation Algorithm for File Synchronizers. 19th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS), Jun 2019, Kongens Lyngby, Denmark. pp.1-18, ⟨10.1007/978-3-030-22496-7_1⟩. ⟨hal-02319573⟩

Share

Metrics

Record views

75