Set reconciliation achieves minimal data overhead with fast updates and decoding
Linear Set Reconciliation with $O(d)$ Additive Redundancy
Data Structures and AlgorithmsInformation Theory
Summary
Set reconciliation is about two parties quickly finding what items they don’t share between their collections without sending all their data. The authors found a way to represent these differences using a very close to the smallest possible number of bits, while still allowing quick updates and fairly fast decoding. They used clever linear algebra and a new method to gradually recover missing parts step-by-step. This method works well for large sets and small differences, making the process more efficient.
What this means in practice
- •For distributed storage engineers: Improve synchronization protocols by exchanging minimal difference data with fast encoding and decoding methods for distributed storage systems.
- •For network protocol developers: Design lightweight data reconciliation protocols that minimize communication overhead while supporting real-time updates in networked devices.
Authors
Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou
Abstract
In set reconciliation, two parties holding sets $A, B \subseteq [n]$ with $|A \triangle B| \le d$ seek to recover their symmetric difference from short $\mathbb{F}_2$-linear sketches, which is equivalent to recovering a $d$-sparse vector $x = \mathbf{1}_{A \triangle B} \in \mathbb{F}_2^n$ from its syndrome $Hx \in \mathbb{F}_2^m$. While the information-theoretic counting bound requires $L(n,d) := \log \sum_{i=0}^d \binom{n}{i} = d\log(n/d) + Θ(d)$ bits, existing polynomial-time schemes either use at least $d\lceil\log(n+1)\rceil$ bits (algebraic sketches, leaving an $Ω(d\log d)$-bit gap) or incur a multiplicative $(1+δ)L(n,d)$ overhead (peeling-based sketches), raising the question of whether $L(n,d) + O(d)$ bits is achievable with fast updates and decoding. We construct a public-coin randomized $\mathbb{F}_2$-linear sketch of length $L(n,d) + O(d) + λ\log^{O(1)} n$ that recovers each fixed input of weight at most $d$ with probability at least $1 - 2^{-λ}$, with $\log^{O(1)} n$ update time and $d\exp(O((\log\log n)^2)) = dn^{o(1)}$ worst-case decoding time. In particular, for $n \le 2^{\operatorname{polylog}(d)}$ and $λ\le d^{1-Ω(1)}$, this achieves $L(n,d) + O(d)$ bits with $\operatorname{polylog}(d)$ update time and $d^{1+o(1)}$ decoding time. Our construction encodes $d$ permuted rows via randomly scaled Pinsketch syndromes and sketches the resulting bit array column by column. Decoding columns sequentially from prefix predictions cancels recovered rows and exposes undecided rows as decoder-side hints, reducing each column to a hinted sparse recovery problem that we solve via a recursive sketch, HintSketch.