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 allows for an efficient algorithm that produces it.
翻译:随着分布式计算和移动应用程序越来越普遍,同步不同复制同一数据是一个常见问题。对调 -- -- 使同一数据结构的两个复制尽可能接近于同一数据结构,而不压倒当地的变化 -- -- 在代数模型中进行调查。我们的方法是考虑两个简单的命令序列,描述复制件与原始结构相比的变化,然后确定每个复制件的最大次序列,然后可以传播到另一个。拟议的命令组显示功能完整,并提供了更新的探测算法,从而产生一个命令序列,将原始数据结构转换为复制,同时同时进行翻转。以对等命令序列进行重写系统的方式提供了协同战术性定性。对适用于同一数据结构的序列对等的代数特性进行了调查。根据这些结果,对调的问题显示出一个独特的最大解决办法。此外,最高级解决办法的合成特性允许一种高效的算法进行生成。