0569846 20230418232832.520230309235959.9 85140367648 000903720300005 10.1556/012.2022.01529 23 s. P cav_un_epca*02557370081-690659209-231Akadémiai Kiadó file synchronization algebraic model confluence rewriting system cav_un_auth*0447301 Csirmaz E. P. HU cav_un_auth*0398469 Csirmaz Laszlo UTIA-B Matematická teorie rozhodování Department of Decision Making Theory MTR MTR HU Ústav teorie informace a automatizace AV ČR, v. v. i. http://library.utia.cas.cz/separaty/2023/SI/csirmaz-0569846-preprint.pdf https://akjournals.com/view/journals/012/59/3-4/article-p209.xml GA19-04579S GA ČR CZ cav_un_auth*0380558 With distributed computing and mobile applications becoming ever more prevalent, synchronizing diverging replicas of the same data is a common problem. Reconciliation – bringing two replicas of the same data structure as close as possible without overriding local changes – is investigated in an algebraic model. Our approach is to consider two sequences of simple commands that describe the changes in the replicas compared to the original structure, and then determine the maximal subsequences of each that can be propagated to the other. The proposed command set is shown to be functionally complete, and an update detection algorithm is presented which produces a command sequence transforming the original data structure into the replica while traversing both simultaneously. Syntactical characterization is provided in terms of a rewriting system for semantically equivalent command sequences. Algebraic properties of sequence pairs that are applicable to the same data structure are investigated. Based on these results the reconciliation problem is shown to have a unique maximal solution. In addition, syntactical properties of the maximal solution allow for an efficient algorithm that produces it. WOS BA 10000 10100 10101 2023 2 RVO:67985556 https://hdl.handle.net/11104/0341180 S n.a. Article Mathematics C MATHEMATICS 0.8 0.2 18.5 0.00054 0.379 570 0.351 0.700 20 Q3 38.6 Q3 Q3 0.66 Q2 38.6 2022 85140367648 SCOPUS PUBMED 000903720300005 WOS cav_un_epca*0255737 Studia Scientiarum Mathematicarum Hungarica 0081-6906 1588-2896 Roč. 59 3-4 2022 209 231 Akadémiai Kiadó