MCFsyn: A Multi-Party Set Reconciliation Protocol With the Marked Cuckoo Filter
MCFsyn: A Multi-Party Set Reconciliation Protocol With the Marked Cuckoo Filter
复制标题
DOI：
10.1109/tpds.2021.3074440
复制
发表时间：
2021-11
影响因子：
5.3
通讯作者：
Lailong Luo;Deke Guo;Yawei Zhao;Ori Rottenstreich;Richard T. B. Ma;Xueshan Luo
中科院分区：
文献类型：
--
作者：
Lailong Luo;Deke Guo;Yawei Zhao;Ori Rottenstreich;Richard T. B. Ma;Xueshan Luo
多方集协调是分布式和网络化系统的关键组成部分。它自然包含两个维度，即集合表示和协调协议。然而，现有的草图数据结构已不足以同时满足多方场景带来的新需求，包括空间效率、可合并性和完整性。另一方面，现有的协调协议无法实现通信成本的全局优化。为此，在本文中，我们提出了标记布谷鸟滤波器（MCF），一种表示集合成员的数据结构。在MCF的基础上，我们实现了MCFsyn协议来协调多个集合。MCFsyn通过底层的最小生成树在参与者之间聚合和分布由mcf表示的集合信息。然后参与者通过遍历包含联合集中所有元素信息的整个MCF来识别不同的元素。对于确定的缺失元素，MCFsyn帮助参与者以最小的通信成本选择最优的发送者来获取。综合评价表明，MCFsyn在对账准确性和通信成本方面都明显优于现有的替代方案。
Multi-party set reconciliation is a key component in distributed and networking systems. It naturally contains two dimensions, i.e., set representation and reconciliation protocol. However, existing sketch data structures are insufficient to satisfy the new needs brought by the multi-party scenario simultaneously, including space-efficiency, mergeability, and completeness. The current reconciliation protocols, on the other hand, fail to achieve the global optimization of communication cost. To this end, in this article, we propose the marked cuckoo filter (MCF), a data structure for representing set members. Grounded on MCF, we implement the MCFsyn protocol to reconcile multiple sets. MCFsyn aggregates and distributes sets information represented by MCFs along with an underlying minimum spanning tree among the participants. The participants then identify the different elements by traversing the overall MCF which contains the information of all elements in the union set. For the identified missing elements, MCFsyn helps the participants to choose the optimal senders to fetch with the minimum communication cost. Comprehensive evaluations indicate that MCFsyn significantly outperforms existing alternatives in terms of both reconciliation accuracy and communication cost.