Synchronizing Many Filesystems in Near Linear Time
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-co...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-05-01
|
| Series: | Future Internet |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-5903/15/6/198 |
| _version_ | 1797594739928727552 |
|---|---|
| author | Elod P. Csirmaz Laszlo Csirmaz |
| author_facet | Elod P. Csirmaz Laszlo Csirmaz |
| author_sort | Elod P. Csirmaz |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T02:26:29Z |
| format | Article |
| id | doaj.art-888d63a6d0c0434684e9957eba87f162 |
| institution | Directory Open Access Journal |
| issn | 1999-5903 |
| language | English |
| last_indexed | 2024-03-11T02:26:29Z |
| publishDate | 2023-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Future Internet |
| spelling | doaj.art-888d63a6d0c0434684e9957eba87f1622023-11-18T10:30:17ZengMDPI AGFuture Internet1999-59032023-05-0115619810.3390/fi15060198Synchronizing Many Filesystems in Near Linear TimeElod P. Csirmaz0Laszlo Csirmaz1Alfréd Rényi Institute of Mathematics, 1053 Budapest, HungaryAlfréd Rényi Institute of Mathematics, 1053 Budapest, HungaryFinding 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.https://www.mdpi.com/1999-5903/15/6/198file synchronizationalgebraic modeloptimistic synchronizationlinear complexity |
| spellingShingle | Elod P. Csirmaz Laszlo Csirmaz Synchronizing Many Filesystems in Near Linear Time Future Internet file synchronization algebraic model optimistic synchronization linear complexity |
| title | Synchronizing Many Filesystems in Near Linear Time |
| title_full | Synchronizing Many Filesystems in Near Linear Time |
| title_fullStr | Synchronizing Many Filesystems in Near Linear Time |
| title_full_unstemmed | Synchronizing Many Filesystems in Near Linear Time |
| title_short | Synchronizing Many Filesystems in Near Linear Time |
| title_sort | synchronizing many filesystems in near linear time |
| topic | file synchronization algebraic model optimistic synchronization linear complexity |
| url | https://www.mdpi.com/1999-5903/15/6/198 |
| work_keys_str_mv | AT elodpcsirmaz synchronizingmanyfilesystemsinnearlineartime AT laszlocsirmaz synchronizingmanyfilesystemsinnearlineartime |