Practical Rateless Set Reconciliation

本文介绍了一种名为Rateless Invertible Bloom Lookup Tables(Rateless IBLT)的集合对比协议，它是我们所知道的第一种在广泛场景下实现低计算成本和近乎最优通信成本的集合对比协议，用于两个持有固定长度比特串的参与方运行协议以了解彼此缺失的字符串，这是许多分布式系统中的基本任务。Rateless IBLT基于一种新颖的编码器，将集合差异逐步编码成一个无限的编码符号流，类似于无速率错误纠正码。我们将Rateless IBLT与最先进的集合对比方案进行比较，并展示了显著的改进。与计算成本类似的非无速率方案相比，Rateless IBLT的通信成本降低了3-4倍，与类似通信成本的方案相比，计算成本降低了2-2000倍。我们通过将其应用于同步以太坊区块链的状态来展示Rateless IBLT的真实世界效益，并展示了与生产中使用的系统相比，完成时间降低了5.6倍，通信成本降低了4.4倍。

Rateless IBLT试图解决分布式系统中的集合对比问题，即两个参与方持有固定长度的比特串，运行协议以了解彼此缺失的字符串。

Rateless IBLT基于一种新颖的编码器，将集合差异逐步编码成无限流的编码符号，类似于无速率纠错码。

Rateless IBLT是第一个在广泛的场景下实现低计算成本和接近最优通信成本的集合对比协议。它可以处理1到数百万个集合差异，几个字节到兆字节的比特串，以及潜在对手注入的工作负载。与现有方案相比，Rateless IBLT的通信成本降低了3-4倍，计算成本降低了2-2000倍。作者通过将其应用于以太坊区块链的状态同步，展示了Rateless IBLT的实际效益。

在这个领域中的相关研究包括：Set reconciliation with nearly optimal communication complexity（By Oded Goldreich, et al.）和Efficient Set Reconciliation without Prior Context（By Michael Mitzenmacher, et al.）