论文标题
通过平等位图草图（PBS）的空间和计算效率设置对帐
Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)
论文作者
论文摘要
集合对帐是在许多网络，系统和数据库应用程序中出现的基本算法问题。在此问题中，分别存储在两个不同的网络连接的主机上，我们将两个大的对象（比特币，文件，记录等）分别存储，我们将其命名为Alice和Bob。爱丽丝和鲍勃相互交流，学习$aδb$，a和b之间的差异，结果和解设置了$ a \ bigcup b $。 当前集合对帐方案基于可逆的布鲁姆过滤器（IBF）或错误纠正代码（ECC）。前者的计算复杂性低为O（d），其中D是$AΔB$的基数，但具有高的通信开销，比理论最小值大几倍。后者的通信开销较低，接近理论最低限度，但计算复杂性高得多，为$ O（d^2）$。在这项工作中，我们提出了一种基于ECC的集合对帐方案的奇偶校验比特图草图（PBS），该方案使两者越好：PBS既具有O（D）的低计算复杂性，就像基于IBF的解决方案和低相位的交流大约是理论最小值的两倍。这项工作的单独贡献是一种新颖的严格分析框架，可用于精确计算各种性能指标和PBS的近乎最佳参数调整。
Set reconciliation is a fundamental algorithmic problem that arises in many networking, system, and database applications. In this problem, two large sets A and B of 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 learn $AΔB$, the difference between A and B, and as a result the reconciled set $A\bigcup 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 of O(d), where d is the cardinality of $AΔ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 of $O(d^2)$. 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 of O(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.
