Algebra of data reconciliation
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F22%3A00569846" target="_blank" >RIV/67985556:_____/22:00569846 - isvavai.cz</a>
Výsledek na webu
<a href="https://akjournals.com/view/journals/012/59/3-4/article-p209.xml" target="_blank" >https://akjournals.com/view/journals/012/59/3-4/article-p209.xml</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1556/012.2022.01529" target="_blank" >10.1556/012.2022.01529</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Algebra of data reconciliation
Popis výsledku v původním jazyce
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 allownfor an efficient algorithm that produces it.
Název v anglickém jazyce
Algebra of data reconciliation
Popis výsledku anglicky
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 allownfor an efficient algorithm that produces it.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GA19-04579S" target="_blank" >GA19-04579S: Struktury podmíněné nezávislosti: metody polyedrální geometrie</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2022
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Studia Scientiarum Mathematicarum Hungarica
ISSN
0081-6906
e-ISSN
1588-2896
Svazek periodika
59
Číslo periodika v rámci svazku
3-4
Stát vydavatele periodika
HU - Maďarsko
Počet stran výsledku
23
Strana od-do
209-231
Kód UT WoS článku
000903720300005
EID výsledku v databázi Scopus
2-s2.0-85140367648