Algebra of data reconciliation
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Algebra of data reconciliation
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GA19-04579S" target="_blank" >GA19-04579S: Conditonal independence structures: methods of polyhedral geometry</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Studia Scientiarum Mathematicarum Hungarica
ISSN
0081-6906
e-ISSN
1588-2896
Volume of the periodical
59
Issue of the periodical within the volume
3-4
Country of publishing house
HU - HUNGARY
Number of pages
23
Pages from-to
209-231
UT code for WoS article
000903720300005
EID of the result in the Scopus database
2-s2.0-85140367648