田小梅，张大方，谢鲲，胡灿，杨晓波，史长琼,3

(1. 湖南大学 信息科学与工程学院，湖南 长沙410082; 2. 湖南环境生物职业技术学院 信息技术系，湖南 衡阳421005；3. 长沙理工大学 计算机与通信工程学院，湖南 长沙410114)

1 引言

在分布式系统中，假定2节点A、B分别拥有数据集合SA、SB，节点A和B进行数据交换得到并集SA∪SB的过程称集合调和[1]。也就是说，集合调和是通过分布式节点进行数据交换获得2节点数据集合并集的过程。集合中的元素可以是P2P系统中的文件块或路由协议中的链路状态分组标记等。集合调和在分布式文件分发、闲谈协议等分布式计算领域是一个重要的基本问题。一般说来，集合调和可以用于需要对无序分布式数据维护一致性的任意系统中。集合调和已广泛应用于分布式数据库与文件系统[2]、信息安全[3,4]、闲谈协议[5]、移动数据库同步[6]、资源定位系统[7]等领域。集合调和过程最关键的问题是如何高效计算集合差集的问题。集合调和中查找差集的技术亦可用于网络分布式系统中的去重过程，如数据域系统[8,9]和文件系统[10,11]，它们首先找出交集中的数据，删除重复数据并用指针代替，从而达到节约空间的目的。

很明显，完成集合调和的最直接方法就是节点B直接传输集合SB给节点A，节点A计算得到并集SA∪SB。在大规模系统中，集合SB数据量非常庞大，直接传输集合SB要消耗大量的带宽。因此，目前大多数方法都是先通过某种方法计算出差集 SB-SA，节点B仅传输SB-SA给节点A，从而节约了带宽使用量。……