IDEAS home Printed from https://ideas.repec.org/a/gam/jftint/v15y2023i6p198-d1159463.html
   My bibliography  Save this article

Synchronizing Many Filesystems in Near Linear Time

Author

Listed:
  • Elod P. Csirmaz

    (Alfréd Rényi Institute of Mathematics, 1053 Budapest, Hungary)

  • Laszlo Csirmaz

    (Alfréd Rényi Institute of Mathematics, 1053 Budapest, Hungary
    Institute of Information Theory and Automation, CZ-182 00 Prague, Czech Republic)

Abstract

Finding a provably correct subquadratic synchronization algorithm for many filesystem replicas is one of the main theoretical problems in operational transformation (OT) and conflict-free replicated data types (CRDT) frameworks. Based on the algebraic theory of filesystems, which incorporates non-commutative filesystem commands natively, we developed and built a proof-of-concept implementation of an algorithm suite which synchronizes an arbitrary number of replicas. The result is provably correct, and the synchronized system is created in linear space and time after an initial sorting phase. It works by identifying conflicting command pairs and requesting one of the commands to be removed. The method can be guided to reach any of the theoretically possible synchronized states. The algorithm also allows asynchronous usage. After the client sends a synchronization request, the local replica remains available for further modifications. When the synchronization instructions arrive, they can be merged with the changes made since the synchronization request. The suite also works on filesystems with a directed acyclic graph-based path structure in place of the traditional tree-like arrangement. Consequently, our algorithms apply to filesystems with hard or soft links as long as the links create no loops.

Suggested Citation

  • Elod P. Csirmaz & Laszlo Csirmaz, 2023. "Synchronizing Many Filesystems in Near Linear Time," Future Internet, MDPI, vol. 15(6), pages 1-26, May.
    • Handle: RePEc:gam:jftint:v:15:y:2023:i:6:p:198-:d:1159463
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/1999-5903/15/6/198/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/1999-5903/15/6/198/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Elod P. Csirmaz & Laszlo Csirmaz, 2022. "Data Synchronization: A Complete Theoretical Solution for Filesystems," Future Internet, MDPI, vol. 14(11), pages 1-21, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Davide Tosi, 2023. "Editorial for the Special Issue on “Software Engineering and Data Science”, Volume II," Future Internet, MDPI, vol. 15(9), pages 1-2, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Davide Tosi, 2023. "Editorial for the Special Issue on “Software Engineering and Data Science”, Volume II," Future Internet, MDPI, vol. 15(9), pages 1-2, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jftint:v:15:y:2023:i:6:p:198-:d:1159463. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.