  Synchronization of transaction pools (mempools) has shown potential for
improving the performance and block propagation delay of state-of-the-art
blockchains. Indeed, various heuristics have been proposed in the literature to
this end, all of which incorporate exchanges of unconfirmed transactions into
their block propagation protocol. In this work, we take a different approach,
maintaining transaction synchronization outside (and independently) of the
block propagation channel. In the process, we formalize the synchronization
problem within a graph theoretic framework and introduce a novel algorithm
(SREP - Set Reconciliation-Enhanced Propagation) with quantifiable guarantees.
We analyze the algorithm's performance for various realistic network
topologies, and show that it converges on any connected graph in a number of
steps that is bounded by the diameter of the graph. We confirm our analytical
findings through extensive simulations that include comparison with
MempoolSync, a recent approach from the literature. Our simulations show that
SREP incurs reasonable overall bandwidth overhead and, unlike MempoolSync,
scales gracefully with the size of the network.
