Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)
Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)
复制标题
DOI：
10.14778/3436905.3436906
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Long Gong;Ziheng Liu;Liang Liu;Jun Xu;Mitsunori Ogihara;Tong Yang
中科院分区：
文献类型：
--
作者：
Long Gong;Ziheng Liu;Liang Liu;Jun Xu;Mitsunori Ogihara;Tong Yang
集合协调是在许多网络、系统和数据库应用中出现的基本算法问题。在这个问题中，两个大的对象集合A和B（比特币，文件，记录等）分别存储在两个不同的网络连接的主机上，我们分别将其命名为Alice和Bob。Alice和Bob相互通信以学习A ΔB，A和B之间的差，并且作为结果，协调的集合A优于B。当前的集合协调方案基于可逆布隆过滤器（IBF）或纠错码（ECC）。前者的计算复杂度为O（d），其中A的基数为ΔB，但通信开销很大，是理论最小值的几倍。后者具有接近理论最小值的低通信开销，但具有高得多的O（d2）的计算复杂度。在这项工作中，我们提出了奇偶校验位图草图（PBS），一个基于ECC的集协调方案，得到更好的两个世界：PBS既有一个低的计算复杂度ofO（d）就像基于IBF的解决方案和一个低的通信开销大约是理论最小值的两倍。这项工作的一个单独的贡献是一个新的严格的分析框架，可用于精确计算的各种性能指标和接近最佳的参数调整PBS。
Set reconciliation is a fundamental algorithmic problem that arises in many networking, system, and database applications. In this problem, two large setsAandBof objects (bitcoins, files, records, etc.) are stored respectively at two different network-connected hosts, which we name Alice and Bob respectively. Alice and Bob communicate with each other to learnAΔB, the difference betweenAandB, and as a result the reconciled setA∪B.Current set reconciliation schemes are based on either invertible Bloom filters (IBF) or error-correction codes (ECC). The former has a low computational complexity ofO(d), wheredis the cardinality ofAΔB, but has a high communication overhead that is several times larger than the theoretical minimum. The latter has a low communication overhead close to the theoretical minimum, but has a much higher computational complexity ofO(d2). In this work, we propose Parity Bitmap Sketch (PBS), an ECC-based set reconciliation scheme that gets the better of both worlds: PBS has both a low computational complexity ofO(d)just like IBF-based solutions and a low communication overhead of roughly twice the theoretical minimum. A separate contribution of this work is a novel rigorous analytical framework that can be used for the precise calculation of various performance metrics and for the near-optimal parameter tuning of PBS.