{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:11:40Z","timestamp":1760148700082,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T00:00:00Z","timestamp":1685404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ERC Advanced Grant ERMiD"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/fi15060198","type":"journal-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T02:27:30Z","timestamp":1685500050000},"page":"198","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Synchronizing Many Filesystems in Near Linear Time"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2449-7923","authenticated-orcid":false,"given":"Elod P.","family":"Csirmaz","sequence":"first","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics, 1053 Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7530-8307","authenticated-orcid":false,"given":"Laszlo","family":"Csirmaz","sequence":"additional","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics, 1053 Budapest, Hungary"},{"name":"Institute of Information Theory and Automation, CZ-182 00 Prague, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"unstructured":"Athow, D., and Turner, B. (2023, May 10). Best File Syncing Solutions of 2023. Available online: https:\/\/www.techradar.com\/best\/best-file-syncing-solution.","key":"ref_1"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1052","DOI":"10.1016\/j.future.2017.09.019","article-title":"Cloud storage services for file synchronization and sharing in science, education and research","volume":"78","author":"Mascetti","year":"2018","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/274444.274447","article-title":"Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems","volume":"5","author":"Sun","year":"1998","journal-title":"ACM Trans. Comput. Hum. Interact."},{"unstructured":"Poltrock, S.E., and Grudin, J. (1998, January 14\u201318). Operational Transformation in Real-Time Group Editors: Issues, Algorithms, and Achievements. Proceedings of the ACM 1998 Conference on Computer Supported Cooperative Work, Seattle, WA, USA.","key":"ref_4"},{"doi-asserted-by":"crossref","unstructured":"Shao, B., Li, D., Lu, T., and Gu, N. (2011, January 19\u201323). An Operational Transformation Based Synchronization Protocol for Web 2.0 Applications. Proceedings of the ACM 2011 Conference on Computer Supported Cooperative Work, Hangzhou, China. CSCW \u201911.","key":"ref_5","DOI":"10.1145\/1958824.1958910"},{"unstructured":"Lukosch, S.G., Sarcevic, A., Lewkowicz, M., and Muller, M.J. (2016, January 13\u201316). Operational Transformation for Real-time Synchronization of Shared Workspace in Cloud Storage. Proceedings of the 19th International Conference on Supporting Group Work, Sanibel Island, FL, USA.","key":"ref_6"},{"unstructured":"Day-Richter, J. (2023, January 12). What\u2019s Different about the New Google Docs: Making Collaboration Fast. Available online: https:\/\/drive.googleblog.com\/2010\/09\/whats-different-about-new-google-docs.html.","key":"ref_7"},{"key":"ref_8","first-page":"386","article-title":"Conflict-Free Replicated Data Types","volume":"Volume 6976","author":"Petit","year":"2011","journal-title":"Proceedings of the Stabilization, Safety, and Security of Distributed Systems-13th International Symposium, SSS 2011"},{"doi-asserted-by":"crossref","unstructured":"Pregui\u00e7a, N.M. (2018). Conflict-free Replicated Data Types: An Overview. arXiv.","key":"ref_9","DOI":"10.1007\/978-3-319-63962-8_185-1"},{"unstructured":"Naor, D., Heiser, G., and Keidar, I. (2015, January 26\u201328). Merging semantics for conflict updates in geo-distributed file systems. Proceedings of the 8th ACM International Systems and Storage Conference, SYSTOR 2015, Haifa, Israel.","key":"ref_10"},{"unstructured":"Liu, E. (2021). A CRDT-Based File Synchronization System. [Master\u2019s Thesis, Norwegian University of Science and Technology].","key":"ref_11"},{"doi-asserted-by":"crossref","unstructured":"Shekow, M. (2019). Syncpal: A Simple and Iterative Reconciliation Algorithm for File Synchronizers. [Ph.D. Thesis, RWTH Aachen University].","key":"ref_12","DOI":"10.1007\/978-3-030-22496-7_1"},{"unstructured":"Csirmaz, E.P. (2016). Algebraic File Synchronization: Adequacy and Completeness. arXiv.","key":"ref_13"},{"doi-asserted-by":"crossref","unstructured":"Csirmaz, E.P., and Csirmaz, L. (2022). Data Synchronization: A Complete Theoretical Solution for Filesystems. Future Internet, 14.","key":"ref_14","DOI":"10.3390\/fi14110344"},{"doi-asserted-by":"crossref","unstructured":"Shapiro, M., Pregui\u00e7a, N., Baquero, C., and Zawirski, M. (2011). A Comprehensive Study of Convergent and Commutative Replicated Data Types, INRIA, Inria-Centre Paris-Rocquencourt. Technical Report 7506.","key":"ref_15","DOI":"10.1007\/978-3-642-24550-3_29"},{"unstructured":"Knuth, D.E. (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley. [3rd ed.].","key":"ref_16"},{"unstructured":"Osborne, W.P., and Moghe, D.B. (1998, January 25\u201330). What is a File Synchronizer?. Proceedings of the MOBICOM \u201998, The Fourth Annual ACM\/IEEE International Conference on Mobile Computing and Networking, Dallas, TX, USA.","key":"ref_17"},{"unstructured":"Tridgell, A., and Mackerras, P. (1996). The Rsync Algorithm, Australian National University.","key":"ref_18"},{"doi-asserted-by":"crossref","unstructured":"Bo\u0161kov, N., Trachtenberg, A., and Starobinski, D. (2023). Enabling Cost-Benefit Analysis of Data Sync Protocols. arXiv.","key":"ref_19","DOI":"10.1109\/MC.2023.3251195"},{"doi-asserted-by":"crossref","unstructured":"Pregui\u00e7a, N., Marques, J.M., Shapiro, M., and Letia, M. (2009, January 22\u201326). A Commutative Replicated Data Type for Cooperative Editing. Proceedings of the 2009 29th IEEE International Conference on Distributed Computing Systems, Montreal, QC, Canada. ICDCS \u201909.","key":"ref_20","DOI":"10.1109\/ICDCS.2009.20"},{"doi-asserted-by":"crossref","unstructured":"L\u00e4mmel, R., Visser, J., and Saraiva, J. (2007, January 2\u20137). Design Space of Heterogeneous Synchronization. Proceedings of the Generative and Transformational Techniques in Software Engineering II: International Summer School, GTTSE 2007, Braga, Portugal. Revised Papers.","key":"ref_21","DOI":"10.1007\/978-3-540-88643-3"},{"unstructured":"Eyers, D., and Schwan, K. (2013, January 9\u201313). Efficient Batched Synchronization in Dropbox-Like Cloud Storage Services. Proceedings of the Middleware 2013, Beijing, China.","key":"ref_22"},{"doi-asserted-by":"crossref","unstructured":"Petroni, A., Cuomo, F., Schepis, L., Biagi, M., Listanti, M., and Scarano, G. (2018). Adaptive Data Synchronization Algorithm for IoT-Oriented Low-Power Wide-Area Networks. Sensors, 18.","key":"ref_23","DOI":"10.3390\/s18114053"},{"doi-asserted-by":"crossref","unstructured":"Feng, J., Qiao, X., and Li, Y. (November, January 30). The research of synchronization and consistency of data in mobile environment. Proceedings of the 2012 IEEE 2nd International Conference on Cloud Computing and Intelligence Systems, Hangzhou, China.","key":"ref_24","DOI":"10.1109\/CCIS.2012.6664300"},{"doi-asserted-by":"crossref","unstructured":"Klophaus, R. (2010, January 1\u20132). Riak Core: Building Distributed Applications without Shared State. Proceedings of the ACM SIGPLAN Commercial Users of Functional Programming, Baltimore, MD, USA. CUFP \u201910.","key":"ref_25","DOI":"10.1145\/1900160.1900176"},{"unstructured":"Qian, Y. (2004). Data Synchronization and Browsing for Home Environments. [Ph.D. Thesis, Technische Universiteit Eindhoven].","key":"ref_26"},{"unstructured":"Zhang, Y., Dragga, C., Arpaci-Dusseau, A., and Arpaci-Dusseau, R. (2019, January 8\u20139). *-Box: Towards Reliability and Consistency in Dropbox-like File Synchronization Services. Proceedings of the 5th USENIX Conference on Hot Topics in Storage and File Systems, Renton, WA, USA. HotStorage\u201913.","key":"ref_27"},{"doi-asserted-by":"crossref","unstructured":"Even, S. (2011). Graph Algorithms, Cambridge University Press. [2nd ed.].","key":"ref_28","DOI":"10.1017\/CBO9781139015165"}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/15\/6\/198\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:45:07Z","timestamp":1760125507000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/15\/6\/198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,30]]},"references-count":28,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["fi15060198"],"URL":"https:\/\/doi.org\/10.3390\/fi15060198","relation":{},"ISSN":["1999-5903"],"issn-type":[{"type":"electronic","value":"1999-5903"}],"subject":[],"published":{"date-parts":[[2023,5,30]]}}}