Practical Set Reconciliation

Practical Set Reconciliation
复制标题

实用的设置调节

DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
A. Trachtenberg
A. Trachtenberg
中科院分区：
--
文献类型：
--
作者：
Y. Minsky;A. Trachtenberg

文献摘要

被引文献

相似文献

我们考虑的问题，有效地协调两个类似的不同主机。这个问题的动机是在一个八卦协议的数据交换问题，但也有其他的应用程序，包括PDA数据库的同步和维护路由表，在面对主机故障。以前的研究结果已经提出了算法的设置和解，是近最佳的通信复杂性，但计算复杂性是立方的差异的数量。我们提出并分析了一种新的算法，预期的计算和通信的复杂性，是线性的集合之间的差异被调和。我们还提供了实验结果，从该算法的实施。部分由ARPA/RADC基金F30602-96-1-0317、AFOSR基金F49620-00-1-0198、美国国防高级研究计划局（DARPA）和美国空军研究实验室空军材料司令部（协议编号F30602-99-1-0533）、国家科学基金会基金9703470和英特尔公司的基金支持。本文所载的观点和结论是作者的观点和结论，不应被解释为必然代表这些组织或美国政府的官方政策或认可，无论是明示还是暗示。Ari Trachtenberg的工作是基于美国国家科学基金会资助的工作，资助号为CCR-0133521
We consider the problem of efficiently reconciling two similar sets held by different hosts. This problem is motivated by the problem of data exchange in a gossip protocol, but also has other applications including synchronization of PDA databases and maintenance of routing tables in the face of host failures. Previous results have presented algorithms for set reconciliation that are nearly optimal in terms of communication complexity, but have computational complexity that is cubic in the number of differences. We present and analyze a novel algorithm that has expected computational and communication complexity that is linear in the number of differences between the sets being reconciled. We also provide experimental results from an implementation of this algorithm. Supported in part by ARPA/RADC grant F30602-96-1-0317, AFOSR grant F49620-00-1-0198, Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory Air Force Material Command USAF under agreement number F30602-99-1-0533, National Science Foundation Grant 9703470, and a grant from Intel Corporation. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of these organizations or the U.S. Government. The work of Ari Trachtenberg is based upon work supported by the National Science Foundation under NSF Grant No. CCR-0133521