Search papers, labs, and topics across Lattice.
This paper introduces a novel approach to set reconciliation using Invertible Bloom Lookup Tables (IBLTs) that measures the unknown difference cardinality \(d\) before decoding, thereby optimizing communication efficiency. By employing a quadratic statistic over cell counts, the method provides an unbiased estimate of \(d\) without additional data transmission, and this estimate remains valid even in the event of decoding failures. The authors validate their approach through extensive profiling of over 41,000 reconciliation runs in a real-world cloud environment, demonstrating significant improvements in efficiency compared to traditional methods.
IBLTs can now measure unknown data differences before decoding, eliminating wasted resources and enhancing efficiency in set reconciliation.
Set reconciliation recovers the symmetric difference $A\triangle B$ with communication far below the data volume. Invertible Bloom Lookup Tables (IBLTs) are a standard tool, but their capacity must match the unknown difference cardinality~$d$. In database deployments, $d$ spans orders of magnitude, so undersizing causes rescans or replays while oversizing wastes network and memory. We show that an IBLT measures $d$ before decoding. Each cell count records how many difference elements map to it; a quadratic statistic over the count array gives an exactly unbiased estimate with no extra transmitted bytes. The estimate remains valid after decoding failure because it is read from the same sketch. For standard IBLTs, we derive exact mean and variance formulas and chi-square confidence intervals. The same chi-square law governs failed instances in deep overload. A mapping-aware theorem extends the construction to Irregular, Rateless, and MET IBLTs through per-variant adapters. Our self-sizing protocol uses a first-round failure to compute the second-round capacity in one step, completing within two interaction rounds with an explicit success-probability guarantee. We profile 41{,}603 reconciliation runs over 90 days at NineData Cloud, compare end-to-end against Merkle-style localization in a cross-engine replay of production tables, and deploy across Redis and Pika in China Mobile. The first round therefore turns an unknown difference cardinality into a measurement it has already paid for.
