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.


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

0
下载
关闭预览

相关内容

专知会员服务
76+阅读 · 2021年3月16日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【泡泡一分钟】一种实用且高效的多视图匹配方法
泡泡机器人SLAM
6+阅读 · 2018年11月19日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议/SCI期刊约稿信息9条
Call4Papers
3+阅读 · 2018年1月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
14+阅读 · 2020年12月17日
Arxiv
6+阅读 · 2018年12月10日
Arxiv
7+阅读 · 2018年1月30日
VIP会员
相关资讯
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【泡泡一分钟】一种实用且高效的多视图匹配方法
泡泡机器人SLAM
6+阅读 · 2018年11月19日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议/SCI期刊约稿信息9条
Call4Papers
3+阅读 · 2018年1月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员