PaperlayerView exact revision on arXiv

Source-linked AI summary

IBLTs Measure Before They Decode: Self-Sizing Set Reconciliation from Pre-Peeling Counts

Min Wu, Ji Qi, Chengdui Luo, Shudong Lu, Zhengsheng Ye, Zhengyang Wei

arXiv:2608.26537v1cs.DBcs.DC

TL;DR

IBLT reconciliation must size sketches for an unknown difference cardinality, making capacity selection costly across variable database workloads. This paper estimates the difference before decoding from the existing count channel and uses that estimate to set capacity in a second round, keeping interaction within two rounds while operating at about 2 rounds with 1.3–1.7× the oracle’s bytes.

  • Problem

    IBLT capacity must match an unknown difference cardinality that ranges widely, while failure conditioning complicates whether estimates remain unbiased.

    Source: §1 · p. 2, §2.4 · p. 7

  • Method

    The paper constructs a quadratic count-channel estimator with mapping-aware adapters for IBLT variants and handles selection bias on failed sketches.

    Source: §3 · p. 15, §3.4 · p. 20, §8 · p. 47

  • Results

    The protocol completes within 2 RTTs and holds the round count at about 2 at 1.3–1.7× the oracle’s bytes.

    Source: §8 · p. 47

  • Takeaways & Limitations

    An initial failed IBLT sketch can measure the difference and directly determine second-round capacity without extra transmitted bytes.

    Source: §8 · p. 47

    The chi-square confidence interval is asymptotic for fixed M as d →∞, while finite-sample calibration uses empirically calibrated quantiles.

    Source: §7.2 · p. 46

Abstract

from arXiv · show

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.

1 Introduction

This paper turns failed IBLTs into self-sizing reconciliation sketches: the transmitted count array estimates the unknown difference cardinality without extra bytes, enabling capacity selection within at most two round trips. It develops exact statistical guarantees, mapping-aware extensions, and production validation for database reconciliation.

Core observation

  • A pre-peeling count-array second moment gives an exactly unbiased estimate of d from the already-transmitted IBLT sketch, with no estimation-only fields or bytes.The estimator has variance 2d(d−1)/(M−1), independent of k, and admits chi-square confidence intervals.Source: §1 · p. 3

Measurement theory

  • The Plain IBLT theory establishes exact unbiasedness under arbitrary sign patterns, closed-form variance, chi-square limits, and failure-conditioned guarantees for self-sizing.These guarantees provide the statistical interface qδ after first-round decoding failure, including conditional unbiasedness under random signs and distribution-free lower-tail bounds.Source: §1 · p. 3

Mapping-aware extensions

  • Mapping-aware quadratic-form criteria yield adapters for Irregular, Rateless, and MET IBLTs, unifying estimation across variants on the failure path.The construction centers within the smallest mapping-homogeneous block and normalizes by the true mapping covariance.Source: §1 · p. 3

Self-sizing protocol

  • The self-sizing protocol maps a failed first-round estimate directly to second-round capacity, completing in at most two round trips without doubling probes.Its capacity formula accounts for recovered elements and supplies a second-round success guarantee; cost is roughly 1.3–1.7× an oracle’s bytes across d.Source: §1 · pp. 3–4

System evaluation

  • Across 41,603 NineData runs over 90 days, d spans seven orders of magnitude, motivating fail→measure→resize evaluation alongside Merkle-style localization and cross-city Redis/Pika deployment.The evaluation uses a cross-engine database sidecar, production-shape replay, and ground-truth checks of first-round success and fail→measure→resize paths.Source: §1 · pp. 2, 4

2 Plain IBLT Count Measurement

This section develops and validates plain IBLT count measurement as an exactly unbiased estimator of symmetric-difference size, with precise variance and chi-square tail characterization. It also establishes its stability under decoding failure and fixed-sign imbalance, supporting second-round capacity sizing across tested regimes.

2.1 Model and estimator

  • The centered count energy T sums squared deviations from the count-array mean, and its normalization yields an estimator with expectation d using one O(M)-time pass and O(1) extra space.The estimator is computed before peeling and does not depend on the residual core or decoding outcome.Source: §2.1 · p. 5

2.2 Exact measurement theory

  • Exact finite-M theory shows unbiasedness for arbitrary fixed sign patterns, while the normalized estimator’s variance is independent of k and sign balance.Increasing M reduces relative error as M^-1/2; RSD is about 8.9% at M = 256 and 4.4% at M = 1024.Source: §2.2 · pp. 5–6

2.3 Distributional characterization

  • For fixed M as d grows, the normalized estimator converges to a chi-square law whose skewed lower tail supports conservative capacity planning without distribution fitting or extra summaries.A finite-sample Berry–Esseen result bounds approximation error by O(M(d^-1/2)) for fixed M.Source: §2.3 · p. 6

2.4 Validity under failure conditioning

  • Failure conditioning is measurable from the mapping hypergraph’s degree structure, not difference signs, so failed sketches preserve the estimator’s exact conditional mean under random signs.Fixed-sign guarantees instead use deviation and lower-tail bounds, while deep overload transfers the chi-square law to failed instances without a random-sign model.Source: §2.4 · pp. 7–8

2.5 Quantile interface for self-sizing

  • The protocol exposes only qδ: after failure, d̂/qδ is a one-sided planning upper bound with at most δ underestimation risk; standard tiers have q0.01 ∈ [0.63, 0.95].The paper fixes δ = 0.01, targeting 99% conditional lower-tail coverage; empirical failed-only quantiles are preferred, with analytic bounds as conservative alternatives.Source: §2.5 · p. 9

2.6 Experimental validation

  • Validation spans M ∈ {64, 256, 1024, 4096}, k ∈ {3, 4}, d/M ∈ {0.4, 0.8, 1.6, 8}, five sign settings, and 106 trials across 160 configurations.The grid separates sketch-size effects on estimation variance from load effects on failure-selection bias.Source: §2.6 · pp. 9–10

All-trial (unconditional) accuracy (Theorems 2.1–2.4)

  • The empirical mean of d̂/d stays within 5 × 10^-4 of 1, measured RSD matches theory to four significant figures, and the 1% quantile matches chi-square predictions to thousandths.The symmetric normal approximation systematically underestimates the lower quantile.Source: All-trial (unconditional) accuracy… · p. 10, Table 1 · p. 10
  • Unconditional estimates remain unbiased across the full grid, with maximum deviation 4.7 × 10^-4 and measured-to-closed-form RSD ratios of 0.9981–1.0018.The result is insensitive to k, load, and sign composition, so choosing k for peeling does not require recalibration.Source: All-trial (unconditional) accuracy… · p. 10
  • At M = 64, a single observation has 18% RSD and a 1% quantile near 0.63d, improving at M = 1024 to 4.4% RSD and 0.90d.A smaller first-round sketch preserves unbiasedness but produces a wider confidence interval.Source: All-trial (unconditional) accuracy… · p. 10
  • Deep overload adds no estimation bias: with d = 4096, KS distance stays below 0.003 while RSD rises from 0.014 to 0.063 as M shrinks.With M = 64, increasing d/M reduces KS distance from 0.017 to 0.001 while RSD remains 0.175–0.178.Source: All-trial (unconditional) accuracy… · p. 12, Figure 2 · p. 12

Failure-conditioned measurement (Theorem 2.6 and Proposition 2.7)

  • The failure-conditioned mean stays within [0.9998, 1.0001] across failure rates of 3%–68%, while the failed-only 1% quantile differs from the unconditional prediction by at most 0.002.At M = 64, the unconditional cutoff has a 1.042% conditional tail probability, so production uses the failed-only empirical quantile; the other tiers remain within approximately one Monte Carlo standard error.Source: Failure-conditioned measurement… · pp. 12–13
  • In the certified deep-overload tier d/M = 8, all 10^6 trials failed, consistent with the success-probability bound ε_M,d ≤ 3.7 × 10^-6.Across the full random-sign grid, the maximum conditional-mean deviation is 0.19%, consistent with Monte Carlo error.Source: Failure-conditioned measurement… · pp. 13–14

Fixed-sign robustness (Theorem 2.6 bound and Proposition 2.8)

  • Fixed-sign experiments violate neither Theorem 2.6’s deviation bound nor Proposition 2.8’s lower-tail bound across 52 and 120 configurations, respectively.The largest empirical deviation is 31% of its bound, the minimum lower-tail coverage margin is 0.17, and observed transition-region overestimation is conservative for capacity sizing.Source: Fixed-sign robustness (Theorem 2.6… · p. 14

3 Mapping-Aware Constructions: The Unifying Theorem and Four Variant Adapters

This section develops a unifying, mapping-aware framework for IBLT cardinality measurement, using variant-specific centering, covariance, and failure-path adapters. It derives unbiased estimators and confidence-interval analyses for Irregular, Rateless, and MET IBLTs, including heterogeneous data types and decoding-failure effects.

3 Mapping-Aware Constructions: The Unifying Theorem and Four Variant Adapters

  • Theorem 3.1 shows that centering the true mapping mean and normalizing by its covariance makes a quadratic count statistic unbiased for the difference cardinality.Adapters depend only on each mapping type’s mean µ_j and covariance Σ_j; Plain’s normalization is recovered as γ = k(1 − k/M).Source: §3 · pp. 14–15

3.1 Adapter overview and the Irregular adapter

  • Irregular requires Plain’s global centering but a second-moment degree normalization; replacing it with mean-degree normalization causes systematic underestimation.The correction is 40.3% at M = 18, about 12% at M = 50, and 0.5% at M = 1024; measured and closed-form RMSE differ by at most 0.22%.Source: §3.1 · p. 16

3.2 Rateless prefix analytic adapter

  • Rateless uses cell 0 as a centering baseline and provides an exactly unbiased estimate for every received prefix, with relative variance decaying as O(1/m).The construction relies on analytically derived hit probabilities and pairwise-independent prefix indicators under the fresh-uniform model.Source: §3.2 · p. 17

Rateless simulation validation

  • Rateless estimates remain centered, halve RMSE when prefix length quadruples, and achieve coverage within 0.32 percentage points of nominal across tested conditions.The analytic estimator uses no fitted parameters; the reference sampler matches the predicted mapping statistics, while ratio-of-sums would reduce nominal-90% coverage to about 50%.Source: Rateless simulation validation · pp. 18–19, Table 5 · p. 18

3.3 MET partial-type adapter

  • MET centers separately within each cell type and supports partial-type prefixes using finite-prefix normalization, subject to a linear identifiability gate.If the gate fails, the receiver continues collecting cells or falls back without producing an estimate.Source: §3.3 · pp. 19–20

3.4 Failure conditioning for variants (Corollary 3.9)

  • Under failure selection, sign-induced bias remains zero, while random variant self-energies create a separate mapping-selection bias requiring an explicit bound.Deterministic self-energies preserve exact conditional unbiasedness; Irregular, Rateless, and partial-type MET can have mapping-dependent self-energy correlated with decodability.Source: §3.4 · p. 20
  • All adequately sampled Plain and Irregular instances remain within their analytic failure-conditioned bounds, with deviations shrinking as p_F → 1.Figure 5 reports this behavior; sparsely sampled tiers with p_F < 0.02 are marked separately.Source: §3.4 · p. 21, Figure 5 · p. 21
  • At d = 1024, Irregular shows a positive mapping-selection deviation of 1.0127 at M = 1150 and p_F = 0.192, while adequately sampled points stay within bounds.The observed deviation is about 14 Monte Carlo standard errors and approaches the noise floor as p_F → 1.Source: §3.4 · p. 21
  • Plain’s deterministic self-energy leaves only fixed-sign cross-term deviations, whereas Irregular’s i.i.d. signs eliminate the sign channel and expose random self-energy mapping effects.The two panels therefore isolate the distinct conditional-deviation mechanisms predicted by Corollary 3.9.Source: §3.4 · p. 21
  • The four adapters expose {b_d, CI}; Plain and Rateless use analytic intervals, while Irregular and MET use failed-only empirical quantiles.Corollary 3.9 establishes conditional-mean validity, and MET extends the decomposition after weights normalize each element’s expected self-energy to one.Source: §3.4 · p. 21

4 Self-Sizing Protocol

The self-sizing protocol uses a failed fixed-capacity IBLT to measure the unknown difference, compute a safe second-round capacity in one step, and finish within two RTTs. Its calibrated guarantees and cost evaluation show reliable recovery while staying close to an oracle across difference sizes.

4.4 Core protocol flow

  • The exchange has a 1-RTT fast path on first-round success and a fixed 2-RTT fail→measure→resize path using a fresh second-round sketch, otherwise entering FALLBACK.The receiver saves counts, computes M2, removes already recovered elements, and optionally performs joint peeling.Source: §4 · p. 22, §4.4 · pp. 24–25, Figure 6 · p. 25

4 Self-Sizing Protocol

  • The fixed 2-RTT main path bounds interaction cost despite cross-datacenter RTT, while its main tradeoff is the extra capacity multiplier 1/qδ for lower-tail safety.Scan and transfer costs remain workload-dependent, but batching keeps the two-round latency contribution small.Source: §4 · p. 22, §4.7 · p. 27

4.1 Two-round mechanism and protocol state

  • The receiver must save pre-peeling counts because peeling rewrites them, making post-peeling values measure only the residual core rather than the full difference cardinality.The same first-round sketch therefore supports decoding, measurement, and second-round sizing before decoding mutates its counts.Source: §4.1 · p. 22, §4 · p. 22

4.2 Capacity formula and success guarantee

  • The protocol sets M2 from the estimate using α = β/qδ, guaranteeing conditional failure probability at most δ + ηdec(β) with a fresh independent hash.The two risk budgets separately cover statistical underestimation and finite-length decoder failure; no iterative probing is required.Source: §4.2 · p. 23

4.3 Joint peeling and first-round residual state

  • Joint peeling of the first-round residual core cannot reduce success: whenever second-round-only peeling succeeds, replaying its sequence succeeds jointly without extra transmitted bytes.The deployed capacity remains based on standalone β, while residual-state reuse provides runtime margin.Source: §4.3 · p. 24

4.5 Configuration and operating boundaries

  • Configuration requires δ, M1, qδ, and β; the two rounds must encode the same elements with independent mappings, while overflow or missing qδ produces REJECT.Over-budget second-round estimates exit directly to FALLBACK instead of requesting another sketch.Source: §4.5 · pp. 25–26

4.6 Success-rate calibration

  • At α = 1.6, failed-only second-round success reaches 99.901% for M1 = 512 and 99.336% for M1 = 256, rising to 99.855% at α = 1.8.These results realize approximately 99.9% second-round success at measured operating points despite a 99% lower-tail design target.Source: §4.6 · p. 26, Figure 7 · p. 27

4.7 Protocol cost under unknown difference cardinality: regret versus oracle

  • 1.3–1.7× byte regret keeps self-sizing near the oracle with about 2 rounds, while blind doubling reaches 12 rounds at d = 10^5 and Strata-first pays 8–20× at small d.With M1 = 64, self-sizing remains stable across d; Strata-first’s one-round advantage is limited to d ≤100 and disappears for M1 ≥256.Source: §4.7 · pp. 27–28, Figure 8 · p. 28

5 System Evaluation and Applicability

This section evaluates self-sizing IBLTs across production-scale relational and cross-city key-value workloads, comparing their cost and applicability with Merkle-style localization under varying difference profiles and operating assumptions. It also examines production deployment, exact recovery, and second-round capacity sizing.

5.1.2 Difference semantics and protocol state

  • The sidecar saves fingerprints during the first scan, so a failed first round can re-bucket the same fixed input view locally without rescanning before the second round.The network carries only sketches, control messages, and final differences; capacity analyses use multiset dms, while drow represents changed business rows.Source: §5.1.2 · p. 30

5.2.1 The fraction of equal reconciliations drops sharply with table size

  • Among production runs, only 1.3% above 10^8 rows were equal; 89% completed in a single first-round interaction yet contained less than 0.2% of observed differences, while 95.1% of the most expensive 0.1% had differences.The production logs come from the Merkle-style localization currently in service; the self-sizing IBLT has not run on those online tasks, so its outcomes are trace-driven analysis.Source: §5 · p. 28, §5.2.1 · p. 31

5.2.2 Difference cardinality spans seven orders of magnitude with no gap

  • Non-zero difference cardinality ranges from median 24 to p99 194,698 and maximum 4.41 × 10^7, with no natural breakpoint for fixed capacity tiers.This smooth seven-order-of-magnitude distribution makes per-run capacity sizing necessary.Source: §5.2.2 · p. 32

5.2.3 Reconciliation cost concentrates in a very narrow tail

  • The cheapest 90% of runs account for under 3% of cumulative time, whereas the most expensive 5% account for 81%, and the median run lasts 3 seconds versus nearly 3 hours at p99.Long-standing differences carry 96.4% of positive-difference time, concentrating recovery cost in persistent cases.Source: §5.2.1 · p. 31, §5.2.3 · p. 32

5.2.4 Differences cluster in the key space with within-segment scatter

  • Differences cluster in only 3–24 of 100 primary-key-rank buckets, with additional gaps inside affected segments, rather than being uniformly scattered.The evidence covers one complete sharded run across seven table–task combinations and does not provide row-level Jaccard or lookup amplification.Source: §5.2.4 · p. 33

5.3.3 End-to-end cost and its composition

  • At 10 Mbps, self-sizing IBLT leads Merkle-style localization by 1.55× on P1 and 1.25× on P2, while Merkle-style is about 12 seconds faster on P3.At 100 Mbps, all gaps fall within run-to-run noise: 2.5%, 4.3%, and 0.1%.Source: §5.3.3 · p. 36, Figure 12 · p. 36
  • Self-sizing IBLT is 35% cheaper on large cost-body tables under limited bandwidth while staying within 10% of Merkle-style in low-difference workloads.Across 22.5–100 ms RTT and 10–100 Mbps bandwidth, run-specific measurement avoids advance knowledge of d and per-table refinement tuning.Source: §5.3.3 · pp. 36–37

5.3.4 The two methods’ worst cases are asymmetric

  • Scattered differences raise Merkle-style cost by 278% at 100 Mbps and to 18,502 s at 10 Mbps/22.5 ms, whereas IBLT rises only 2%–9%.IBLT transfer remains pinned by measured bd and can reject an over-budget second-round capacity before transmission by entering FALLBACK.Source: Figure 13 · p. 37, §5.3.4 · pp. 37–38

5.4 Cross-city KV field deployment

  • The China Mobile deployment evaluates Redis and Pika across real cross-city links, hash-bucketed key spaces, migration and lag scenarios, and continuously changing data.The setup uses production infrastructure and production-scale key-shape statistics while verifying Redis→Redis and Redis→Pika paths against fault-injected ground truth.Source: §5.4 · p. 38, §5.4.1 · p. 38

5.4.1 Deployment configuration, correctness, and the shared scan cost

  • All six scenario groups recovered the expected differences exactly, while bd deviated from truth by −2.6% to +8.1% and required no second expansion.The shared 4.89-million-key scan took about 28.1 s, accounting for 93.7%–99.1% of IBLT end-to-end time; d = 1 to 937 changed runtime only from 28.7 to 29.6 s.Source: §5.4.1 · pp. 38–39

5.4.2 Three representative difference ranges

  • At about 4 × 10^4 differences, IBLT finishes in about 80 s versus Merkle-style’s 512–523 s, while medium-range IBLT remains about 29–30 s versus Merkle-style’s about 121 s.For d = 0/1, both methods remain near the approximately 28 s scan baseline; G6’s online-change observation window differs by about 4.6×.Source: §5.4.2 · p. 39, Table 10 · p. 39

5.4.3 Key-space structure determines localization cost

  • Hash bucketing scatters differences across buckets, making Merkle-style cost grow approximately linearly, whereas IBLT avoids shared ordering, aligned boundaries, and sorting.In this deployment, Merkle-style remains faster for extremely few clustered differences, with the ordering changing around d ≈5–10; IBLT reads each side once in storage order.Source: §5.4.3 · p. 41

6 Related Work

This section positions self-sizing IBLTs against prior reconciliation, cardinality-estimation, failed-sketch, and consistency-localization methods. Its distinction is measuring from the decoding sketch itself, including after failure, without estimation-only bytes.

6.1 Set reconciliation and IBLTs

  • Unlike prior IBLT protocols that configure capacity externally, self-sizing IBLTs estimate the difference cardinality from the decoding structure itself.Earlier methods use separate estimators or prior knowledge, whereas this construction reuses the transmitted sketch.Source: §6.1 · p. 42

6.2 Approaches to unknown difference cardinality

  • Self-sizing uses the existing decoding sketch within two rounds, unlike separate pre-estimators, blind retries, or incremental rateless transmission.The first fixed-capacity sketch provides the estimate without extra measurement fields or transmitted bytes; against Rateless IBLT on a 609M-row snapshot, the incremental encoder was ∼48× slower and peaked at ∼93 GiB memory versus a few tens of MiB.Source: §6.2 · pp. 42–43

6.3 Estimating difference cardinality from counters

  • Compared with PBS’s independent Tug-of-War counters, the IBLT estimator has the same per-observation variance but reuses reversible decoding cells, adding zero estimation-only bytes.The analysis further supplies exact mean and variance, a chi-square limit, and failure-conditioned lower-tail sizing; unlike Guo–Li CBF [2013], it retains reversible decoding and supports capacity far below d in deep overload.Source: §6.3 · p. 43

6.4 Information in failed IBLT sketches and peeling theory

  • Unlike prior failed-IBLT analyses that use listed keys, peeling output, or failure events, this work reads pre-peeling count energy and proves guarantees conditioned on failure.Failure measurability preserves unbiasedness under independent signs and mappings, while additional results bound conditional bias, transfer the chi-square law when failure is typical, and provide a distribution-free lower tail.Source: §6.4 · p. 44

6.5 Consistency verification in database and storage systems

  • Merkle-style localization compares partitioned checksums hierarchically, whereas self-sizing IBLT costs one O(N) scan plus O(d) sketching and lookups, independent of difference locations.The crossover and representative clustered and near-uniform regimes are evaluated in §5.4 and Appendix R.Source: §6.5 · pp. 44–45

7 Scope and Limitations

The paper’s conclusions require an ideal independent mapping model, signed unclipped counters, and unit-weight or separately derived weighted semantics. Precision and deployment also depend on validated configurations, consistent scan inputs, and operational fallback beyond the estimator’s range.

7.1 Model and channel assumptions

  • The unit-weight model counts fingerprints, while repeated frequency differences target F2; expectation identities persist, but weighted variance and confidence intervals require separate derivations.Updates contribute two independently mapped fingerprints, whereas multiple copies of one key share a mapping and violate element independence.Source: §7.1 · p. 45
  • The analysis assumes independent elements, uniformly chosen distinct cells, ideal hashing, non-adversarial keys, and independent signs and mappings for exact conditional-unbiasedness.Adversarial deployments require keyed hashing and a corresponding adversarial model.Source: §7.1 · p. 45
  • Measurement requires signed, unclipped, lossless counters with sufficient width; overflow or saturation destroys the second moment and must produce REJECT.At d/M = 1111 and k = 3, per-cell counts reach about 1.7 × 10^4, while the centered signal is about 58; without overflow, b̂d stays within ±2.2%.Source: §7.1 · p. 45

7.2 Precision, configuration, and operating range

  • The first-round estimator has about 18% relative standard deviation at M1 = 64 and a 1% quantile near 0.63d, so high-confidence sizing needs a large capacity multiplier α.The chi-square interval is asymptotic for fixed M; the operating range instead uses empirically calibrated quantiles with a finite-sample certificate, while the explicit worst-case constant is too conservative for calibration.Source: §7.2 · pp. 45–46

7.3 System prerequisites and evidence scope

  • The two-round protocol requires rehashing cached first-round fingerprints or rereading the same logical snapshot; online rescans of a changing table fall outside its assumptions.Same-instant semantics require external write quiescence, MVCC, storage snapshots, or a common replication position; the protocol does not provide consistency.Source: §7.3 · pp. 46–47
  • Beyond the estimator’s range, the first-round result is only a computable FALLBACK signal, and choosing manual inspection, a full snapshot, partition comparison, or direct rebuild is operationally external.System evidence covers workload distribution, method cost, and cross-environment reproduction, while production logs use true d and online decisions use b̂d.Source: §7.3 · p. 47

8 Conclusion … B Proof of Theorem 2.1 (Exact Unbiasedness)

The paper presents self-sizing IBLTs that measure the difference cardinality before decoding, combining an unbiased statistical estimator, mapping-aware extensions, and a two-round capacity-setting protocol. Its evaluation demonstrates practical gains, while identifying scope limits and future theoretical work.

Family-level mappings and adapters

  • The estimator is exactly unbiased, has closed-form variance and chi-square confidence intervals, remains valid after first-round failure, and extends to Irregular, Rateless, and MET IBLTs.The mapping-aware theorem unifies the estimate interface across these IBLT families while accounting for failure-conditioned selection.Source: §8 · p. 47

Failure conditioning and the protocol

  • After a first-round failure, the protocol computes second-round capacity in one step, finishes within 2 RTTs, and provides the second-round success probability in (4.2) without extra transmitted bytes for joint peeling.Its interaction cost is bounded at two rounds, while scan, hashing, transfer, capacity, and link costs remain workload-dependent.Source: §8 · p. 47

8 Conclusion

  • Self-sizing holds the round count near 2 at 1.3–1.7× the oracle’s bytes, whereas blind doubling grows logarithmically with difference cardinality and Strata-first is costly for small differences.These are the byte-regret comparisons reported against the two alternative strategies.Source: §8 · p. 47
  • Across deployments, differences span seven orders of magnitude; self-sizing matches Merkle-style localization within ten percent at low differences, leads under bandwidth constraints, and keeps IBLT wall-clock nearly flat as d grows from 1 to 937.The evidence combines a 90-day NineData profile with cross-engine comparison and cross-city Redis/Pika deployment results.Source: §8 · p. 47
  • The theory and evaluation target scan-expensive request/response deployments with signed, unclipped count channels; weighted-frequency variance, joint-capacity reduction, Rateless stopping, and unsigned-channel limits remain open.These limitations define the current scope and future-work agenda.Source: §8 · p. 47
  • Self-sizing IBLTs estimate the unknown difference cardinality before decoding, so failed sketches and incomplete prefixes remain useful measurements rather than wasted work.The construction addresses the capacity mismatch inherent in set reconciliation by extracting information already present in the decoding structure.Source: §8 · p. 47

A Complete Notation

  • The notation defines A and B, capacities M, M1, and M2, mapping degree k, difference cardinality d, count vectors, and the estimator’s mapping quantities for the paper’s reconciliation model.It also establishes column-vector conventions and the meanings of expectation, variance, covariance, and trace.Source: A Complete Notation · p. 51, Plain IBLT and the core estimator · p. 51

B Proof of Theorem 2.1 (Exact Unbiasedness)

  • For the exact-unbiasedness proof, each element contributes a deterministic diagonal self-overlap, while independent elements have hypergeometric overlap with expected value k^2/M; squared signs preserve the result for every sign pattern.The argument therefore also covers the fully one-sided case d− = 0.Source: B Proof of Theorem 2.1 (Exact… · p. 53

C Proof of Theorem 2.2 (Exact Variance)

The proof derives the exact variance by showing that only identical unordered cross-term pairs contribute after centering. Normalization by γ removes the shared signal-noise scale, yielding a variance independent of the sign pattern and supporting Corollary 2.3.

Variance decomposition

  • The diagonal contribution is the deterministic constant dγ, so all randomness in T comes from centered cross terms.Since each cross term has zero mean, Var(T) is obtained by expanding the centered square and summing pair contributions.Source: C Proof of Theorem 2.2 (Exact Variance) · pp. 53–54

Pairwise covariance analysis

  • Only identical unordered pairs survive the variance expansion; distinct pairs are pairwise uncorrelated, including pairs sharing one element.The proof separates pairs by overlap: disjoint pairs are independent, while one-shared-element pairs have zero conditional cross-term mean.Source: C Proof of Theorem 2.2 (Exact Variance) · p. 54

Normalization

  • Dividing b_d = T/γ cancels the k and M−k factors exactly, because both signal and noise scale with γ = k(1−k/M).The normalized variance is therefore independent of sign balance, since surviving sign factors appear only as (s_xs_y)^2 = 1.Source: C Proof of Theorem 2.2 (Exact Variance) · p. 54

Corollary 2.3

  • For d ≥ 1, Theorems 2.1 and 2.2 give E[b_d] = d and Var(b_d) = 2d(d−1)/(M−1), yielding Corollary 2.3.The corollary follows directly by combining the estimator’s expectation with the exact normalized variance.Source: C Proof of Theorem 2.2 (Exact Variance) · p. 54

D Proof of Theorem 2.4 (Chi-Square Limit) … F Supplementary Results for the Plain Estimator Validation (§2.6)

The proofs establish the estimator’s chi-square limit, exact conditional unbiasedness under random signs, and failure-conditioned validity for arbitrary fixed signs. Supplementary validation covers the full parameter grid, finite-sample error, safety bounds, and second-round decoding success.

D Proof of Theorem 2.4 (Chi-Square Limit)

  • Theorem 2.4 derives an isotropic Gaussian limit on the centered subspace, whose squared norm yields a normalized χ2_(M−1) law.The proof uses covariance isotropy, a Lindeberg–Feller triangular-array CLT, continuous mapping, and normalization; its limiting variance is 2/(M−1).Source: D Proof of Theorem 2.4 (Chi-Square… · p. 55

Exact conditional unbiasedness under random signs

  • Under random signs, the estimator is exactly conditionally unbiased after conditioning on successful peeling: E[b̂_d | F] = d.This follows because the conditional expectation given the mappings equals d, while the success event is measurable from those mappings.Source: Exact conditional unbiasedness under… · p. 56

Conditional mean deviation under fixed signs

  • For fixed signs, the conditional-mean analysis combines conditional expectation with Theorem 2.2’s variance 2d(d−1)/(M−1).The supplied proof passage states that the result is obtained by dividing by p_F and substituting Theorem 2.2’s variance.Source: Conditional mean deviation under fixed… · p. 56

Chi-square inheritance when failure is typical

  • When failure is typical, the failure-conditioned estimator retains the chi-square limit, with total-variation error ε_M,d = dk(1−k/M)^(d−1) tending to zero.The argument bounds successful peeling by the existence of a degree-1 cell, then transfers the unconditional limit through conditioning.Source: Chi-square inheritance when failure is… · p. 57
  • The failure-conditioned chi-square limit requires no random-sign model: it holds for every deterministic sign sequence fixed independently of mapping randomness, including fully one-sided signs.Random signs are needed only for the exact finite-sample conditional-mean identity, not for distributional inheritance under failure.Source: Chi-square inheritance when failure is… · p. 57

F Supplementary Results for the Plain Estimator Validation (§2.6)

  • The supplementary validation checks estimator mean, variance, and interval coverage against Theorems 2.1–2.4 across the full parameter range.It also examines failure-conditioned distribution shape, quantile stability, fixed-sign safety bounds, and their connection to second-round decoding success.Source: F Supplementary Results for the Plain… · pp. 57–58
  • All supplementary grid values, except distribution-shape figures, come from 106 independent trials per cell.The distribution-shape figures state their own semantics in their captions.Source: F Supplementary Results for the Plain… · p. 58

F.1 Full-grid validation of the unconditional measurement (Theorems 2.1–2.4) … Q Cov(C)

The supplementary validation confirms that the quadratic estimator matches its unconditional theory across all 160 configurations and remains reliable on failed decodes, while mapping-aware adapters preserve unbiasedness across IBLT variants. These results support using the failed-only lower quantile to size the second-round sketch and clarify the calibration required beyond Plain IBLTs.

F.1 Full-grid validation of the unconditional measurement (Theorems 2.1–2.4)

  • The variance prediction is exact across all 160 configurations, with measured-to-predicted RSD ratios from 0.9981 to 1.0018 and mean error shrinking from 0.00047 to 0.00005 as M grows.The largest chi-square approximation error is 0.0257 at (M, d) = (64, 26), consistent with finite-d asymptotic error.Source: Figure F.1 · p. 58, §F.1 · p. 58
  • Chi-square quantile errors shrink from about 0.0040/0.0023/0.0039 at M = 64 to about 0.0001 at M = 4096, while interval coverage error is about 0.5 percentage points at (64, 26) and 0.02 points at M = 4096.All tiers at M ≥256 remain below 0.3 percentage points, supporting nominal-level use at protocol dimensions.Source: Figure F.2 · p. 59, Table F.2 · p. 59, §F.1 · p. 60

F.2 Failure-conditioned distribution, quantile stability, and safety bounds

  • On failed decodes, the empirical 1% lower-tail estimate is sampling-stable, differing from its 95% one-sided order-statistic lower confidence bound by at most 0.0017.The protocol therefore uses qF_0.01 directly for capacity planning, whereas Proposition 2.8 and Cantelli provide conservative distribution-free safety floors.Source: §F.2 · p. 60
  • The fixed-sign conditional-mean bound has maximum utilization 0.31 across 52 non-degenerate configurations, and the Proposition 2.8 lower-tail bound has no empirical violations across 120 configurations.The minimum coverage margin remains positive at 0.17 for M = 4096; thresholds nF ≥20 and nF ≥103 serve different stability purposes.Source: Table F.4 · p. 60, §F.2 · p. 61, Table F.5 · p. 61
  • Protocol sizing converts the failed-only quantile through α ≥ β/qδ and sends the second-round sketch with capacity M2 = ⌈α d̂⌉.The recommended multipliers and end-to-end success grid are reported in Appendix N, Tables N.1–N.2.Source: §F.2 · p. 61

G Proof of Theorem 3.1 (Mapping-Aware Construction)

  • The mapping-aware theorem requires Qμ_j = 0 for every type to eliminate sign-composition-dependent cross terms, plus tr(QΣ_j) = γ for unbiased normalization under arbitrary fixed signs.For i.i.d. random signs, cross terms vanish in expectation and only a common normalization condition is required.Source: G Proof of Theorem 3.1 (Mapping-Aware… · p. 62

Consistency check: reduction to the Plain IBLT

  • For the Plain IBLT, the adapter uses μ = (k/M)1_M and Q = I_M − M^−1 1_M1_M^⊤, recovering the normalization constant from the standard covariance form.This verifies that the mapping-aware construction reduces to the estimator developed for the Plain IBLT.Source: Consistency check: reduction to the… · p. 62

Q Cov(C)

  • An adapter must remove the true mapping mean with Q and normalize the resulting quadratic energy by tr(QΣ) under the true mapping covariance, so the Plain adapter cannot transfer unchanged to variants.The two calibration requirements explain why mapping changes require variant-specific adapters.Source: Q Cov(C) · p. 62

H Irregular Adapter Proofs and the Degenerate Boundary · Worked example at the D = M = 18 boundary

The irregular adapter normalizes centered mapping energy using the degree second moment, yielding an unbiased estimator, while the exact variance depends on the first four degree moments. At the D = M = 18 boundary, second-moment normalization avoids severe bias from elements that hit every cell, whereas sketch dimension still controls dispersion.

Proposition 3.2 (degree second-moment adapter)

Corollary 3.3 (exact variance)

  • Conditioning on shared mappings shows that cross-energy terms are uncorrelated when element pairs are disjoint or share one element.The result follows from conditional independence and Q1M = 0.Source: Corollary 3.3 (exact variance) · p. 63
  • The exact irregular variance depends only on the first four moments of the degree distribution and reduces to the Plain IBLT result when E = 0.The derivation uses uncorrelated self-energies and cross-energies for disjoint or singly shared element pairs.Source: Corollary 3.3 (exact variance) · pp. 63–64

Worked example at the D = M = 18 boundary

  • At M = 18, the 12.5% of elements with D = 18 hit every cell but contribute zero centered energy because their mappings are all-ones vectors.The centering matrix Q removes the constant direction, and D − D^2/M is also zero at D = M = 18.Source: Worked example at the D = M = 18… · p. 64
  • The corrected γirr = 2.0792 matches this zero-energy case, while γmean = 3.4847 causes a 40.3% systematic underestimation through γirr/γmean = 0.5967.The M = 18 row’s mean remains near 1 with the corrected normalization.Source: Worked example at the D = M = 18… · p. 64
  • The same boundary row has relative RMSE ≈0.34 because smaller M increases random overlap among distinct difference elements.This behavior comes from the first term 2(d −1)/[d(M −1)] of Corollary 3.3, whose size depends only on d and M.Source: Worked example at the D = M = 18… · p. 64
  • Normalization determines the estimate’s center, whereas dispersion depends on sketch dimension M and the degree-dependent self-energy term.The two effects are distinct in the worked boundary example.Source: Worked example at the D = M = 18… · p. 64

I Rateless Prefix Adapter Proofs … Mapping-statistics verification

The Rateless prefix adapter derives closed-form hit probabilities, proves pairwise independence, and uses these results for an unbiased estimator and chi-square confidence intervals. Experiments validate the mapping statistics and show that finite-(d, m) calibration error—not PRNG recursion—explains small coverage deviations, while the average-of-ratios statistic is required for valid intervals.

Lemma 3.4 (closed-form hit probability)

  • The closed-form hit probability follows from a renewal recurrence that decomposes paths by their last hit before the target, with induction verifying the candidate solution.The ceiling transformation preserves the event, and substituting the candidate into the recurrence completes the verification.Source: Lemma 3.4 (closed-form hit probability) · p. 65

Lemma 3.5 (pairwise independence)

  • Rateless prefix hit indicators are pairwise independent: Pr[Bv = 1 | Bu = 1] equals Pr[Bv = 1], yielding Pr[Bi = 1, Bj = 1] = qiqj.The proof uses backward induction and independence of fresh jumps after a path reaches an intermediate cell.Source: Lemma 3.5 (pairwise independence) · p. 66

Proposition 3.6 (analytic estimator)

  • Standardizing each cell by qi(1 − qi) makes each squared term an unbiased estimator of d, so averaging them remains exactly unbiased.For analytically known non-diagonal covariance, the generalized estimator uses the Moore–Penrose pseudoinverse; the Rateless prefix reduces to the diagonal average.Source: Proposition 3.6 (analytic estimator) · p. 66

Proposition 3.7 (asymptotic confidence interval)

  • The multivariate CLT yields a chi-square confidence interval for the average-of-ratios estimator, with rank r = m − 1 under 0 < qi < 1.Independent element hit vectors produce bounded zero-mean summands with covariance diag(qi(1 − qi)).Source: Proposition 3.7 (asymptotic confidence… · p. 66

Statistic/interval pairing (engineering implementation note)

  • The ratio-of-sums alternative has the same mean but a different weighted chi-square distribution on decreasing-q_i prefixes, so applying the stated interval can reduce nominal 90% coverage to approximately 50%.Implementations must pair the Proposition 3.7 interval with the average-of-ratios statistic.Source: Statistic/interval pairing… · p. 67

Finite-(d, m) coverage calibration and PRNG implementation check

  • Coverage stayed within 0.324 percentage points of nominal across 63 finite-(d, m) cells, while balanced-sign diagnostics stayed within 0.22 points across 18 cells.The largest systematic deficit was 0.324 points; the smallest-d/r tier averaged 0.172 points below nominal at 90%.Source: Finite-(d, m) coverage calibration and… · p. 67
  • The ideal fresh-uniform kernel and official pinned sampler deviated at the same scale, showing that finite-(d, m) calibration—not PRNG recursion—caused the residual.The fresh-uniform mechanism reproduced the smallest-d/r deficit without pinned-PRNG recursion.Source: Finite-(d, m) coverage calibration and… · pp. 67–68

Mapping-statistics verification

  • Across 522,753 cell pairs, joint-frequency deviations matched sampling noise with no systematic drift, confirming pairwise independence in both official and fresh-uniform samplers.Marginal hit frequencies also matched the closed-form qi within sampling error across 1,023 observed cells.Source: Mapping-statistics verification · p. 68

J Rateless IBLT: Production-Scale Comparison … N Self-Sizing Protocol Supplement—Capacity Configuration and Protocol Cost

This section compares self-sizing IBLT with Rateless and MET variants at production scale, including their measurement conditions, precision, and identifiability limits. It also specifies the self-sizing protocol’s capacity configuration, cost accounting, recovery semantics, and equal-budget comparison with Plain IBLT.

J Rateless IBLT: Production-Scale Comparison

  • ∼120 s versus ∼490 s and ∼5,800 s, self-sizing beats fixed-prefix and incremental Rateless methods on P1-extra, while incremental memory peaks near 93 GiB versus tens of MiB.The incremental method has the lowest wire bytes, but its O(N) mapping and scheduling state makes it slower and more memory-intensive than stateless Plain IBLT encoding.Source: J Rateless IBLT: Production-Scale… · p. 69, Table J.1 · p. 69

L MET Partial-Type Adapter: Full Statements and Validation

  • Partial MET prefixes provide analytically corrected measurement information before complete cell types arrive, and total F2 is unbiasedly identifiable exactly when the relevant linear-algebra criterion holds.Known assignment fractions can enable identification earlier, whereas unknown fractions require the general matrix adapter and may leave the total unidentifiable.Source: L MET Partial-Type Adapter: Full… · pp. 70–71, Lemma 3.8 (partial-type correction) · p. 71

Partial-type local calibration

  • 0.309% maximum relative error across 54 calibration points supports the finite-prefix correction, with no systematic drift across cell size, degree, or received fraction.The worst point has empirical mean 0.497832 versus closed form 0.499375, with standardized error |z| = 3.09.Source: Partial-type local calibration · p. 72, Table L.1 · p. 72

End-to-end incremental estimation (known-fraction path)

  • 0.36% maximum mean deviation across identifiable end-to-end prefixes shows unbiasedness, while RMSE falls from about 0.41 to 0.20 within type 1 and about 0.10 by prefix 350.The estimate becomes progressively more precise as cells arrive and need not wait for a complete-type boundary.Source: End-to-end incremental estimation… · p. 72, Table L.2 · p. 73

The identifiability state boundary

Failure-conditioning check for the Irregular instance

  • The failure-conditioning framework applies to Plain, Irregular, Rateless, and MET variants because decoding failure depends on mappings rather than independent signs, with variant-specific self-energy behavior.For Irregular IBLTs, the transition-region conditional-mean deviation reaches 1.0127 at M = 1150 and 1.0181 at M = 1175, while deep-overload deviations remain at the noise floor; this mechanism comparison is exploratory.Source: Verification of the premises for the… · p. 74, Failure-conditioning check for the… · p. 76

N Self-Sizing Protocol Supplement—Capacity Configuration and Protocol Cost

  • The supplement covers tiered capacity settings, parameter sensitivity, regret-versus-oracle cost rules, and Strata’s recovery semantics relative to Plain IBLT.It reports first-round capacities, failure-conditioned lower quantiles, second-round multipliers, and success rates, while clarifying Strata’s structural difference under the same budget.Source: N Self-Sizing Protocol… · p. 76

N.1 First-round capacity tiers and capacity multipliers … P Production Workload and Key-Rank Space Supplement

The evaluation shows that self-sizing converts first-round capacity into reliable second-round sizing, usually matching or outperforming Strata-first while improving precision and reducing expected bytes in no-difference-heavy workloads. Cross-engine replay and deployment use controlled, item-level comparisons with canonicalized records and unified timing conditions.

N.1 First-round capacity tiers and capacity multipliers

  • Recommended first-round tiers trade fixed bytes for safety margin: increasing M1 from 64 to 256 raises qδ from 0.6231 to 0.7979 and lowers the multiplier from 2.09 to 1.63.Further increases to 512 and 1024 cells lower the multiplier to 1.52 and 1.45 while costing 16 KB and 32 KB, respectively.Source: §N.1 · pp. 76–77, Table N.1 · p. 77
  • At α = 1.6, M1 = 256 reaches 99.336% second-round success, while M1 = 512 and 1024 reach 99.901% and 99.955%; α = 1.8 raises M1 = 256 to 99.855%.These measurements validate a 99% lower-tail design target, with the reported rates near 99.9% at measured operating points.Source: §N.1 · p. 77, Table N.2 · p. 77

The M1 × d crossover phase diagram

  • Self-sizing+joint uses no more bytes than Strata-first in 71 of 72 M1 × d configurations, with the sole exception at M1 = 64 and d = 105.The exception has ratio 1.02; at M1 = 128 the ratio is 0.96, and for M1 ≥256 the entire line remains at most 0.87.Source: The M1 × d crossover phase diagram · p. 78, Figure N.1 · p. 78
  • The crossover analysis finds Strata-first’s round advantage confined to a narrow small-d band, because sufficiently large M1 makes self-sizing’s first-round decodable range cover that window.Figure N.2 reports mean round difference, with negative values indicating fewer rounds for self-sizing+joint.Source: The M1 × d crossover phase diagram · p. 78, Figure N.2 · p. 79

Expected bytes when no-difference requests dominate

N.3 Strata’s recovery capability and layered capacity

  • At d = 1000, the 1024-cell Plain estimator uses 20% fewer cells than standard 1280-cell Strata while achieving substantially lower RSD; Plain commits the whole budget to one joint decoding domain.Source: §N.3 · p. 80

O.1 Verification scope

  • Verification covers Oracle↔MySQL production-shape replay and Redis↔Pika cross-city deployment, with correctness checked item by item against ground truth under unified inputs, network conditions, phase timing, and reruns.The two topologies use separate controlled setups, including a relay-based container topology and a roughly 10 Mbps, 28.8 ms RTT private-network deployment.Source: §O.1 · p. 81, §O.2 · p. 81

O.3 Cross-engine canonicalization

  • Cross-engine records are canonicalized deterministically before hashing, using type-specific formatting, fixed-separator concatenation, LOWER, and 56-bit MD5 fingerprints.Independent hash layers handle bucket placement, checksums, and fresh-round rehashing without affecting cross-engine alignment.Source: §O.3 · p. 81

P.1 Table-level sample filtering, time range, and statistical semantics … Q.1 Experiment environment and timing semantics

The evaluation covers 41,603 filtered table-level reconciliation runs over 90 days, showing that first-round IBLTs handle most runs but little total difference mass. Replay profiles and controlled cross-engine experiments use complete production-shaped logs, specified hardware and network conditions, phase-based timing, cache warm-up, and correctness checks.

P.1 Table-level sample filtering, time range, and statistical semantics

  • The log contains 41,603 row-comparison runs from 2026-04-29 to 2026-07-28 after filtering unmatched, empty, non-comparable, and keyless entries.Whole-second timing means p50 and lower quantiles should be read only as at most a few seconds.Source: §P.1 · p. 81
  • About 89.1% of runs finish within one first-round interaction, although first-round decodable records contain only 0.175% of total difference mass.Among non-zero differences, 75.1% satisfy dms ≤393 and fit a 512-cell, 16 KB IBLT; the remaining mass concentrates in records above p99.Source: §P.1 · pp. 81, 83
  • Persisting differences appear in 146 consecutive-difference episodes and carry 96.4% of positive-difference time, making recovery the dominant path for cost-heavy tables.Half of episodes appear once and resolve by the next run, one third persist through the window without repair, and no intermediate dozens-of-runs category occurs.Source: §P.1 · p. 83
  • Large tables dominate measured cost: the last two size deciles account for 99.2% of table-level time, whereas the cheapest 80% account for 0.7%.Small-table costs are mainly fixed connection, dispatch, scheduling, and logging overhead; large-table costs are dominated by scanning.Source: §P.1 · p. 83

P.2 Ground truth and block-level logs of the three replay profiles

  • The three replay profiles use complete sharded runs with approximately 100,000-row chunks, concurrency 5, a 1,000-difference lookup cap, and chunk sizes of 99,073–100,130 rows.All dirty records are pairable, and composite-key subqueries are mapped back to logical chunks using first-level boundaries.Source: §P.2 · p. 83

Q.1 Experiment environment and timing semantics

  • The replay runs on one server with 96 logical CPUs and about 2.0 TiB memory, using Oracle 11g and MySQL 8.0.46 containers matched to production resources.Each sidecar receives 8 CPUs and 8 GiB, while scan concurrency is controlled by W rather than container CPU quotas.Source: §Q.1 · p. 84
  • Four network conditions are timed per phase: direct connection, 22.5 ms RTT at 100 Mbps, 22.5 ms RTT at 10 Mbps, and 100 ms RTT at 10 Mbps.Traffic control applies latency and bandwidth in a shared network namespace without an additional user-space relay; every run includes cache warm-up and a correctness check.Source: §Q.1 · pp. 84–85
  • End-to-end timing is divided into explicitly defined phases, with each phase measured separately under the replay conditions.The experiment reports phase semantics through the phase-definition specification accompanying the timing results.Source: §Q.1 · p. 84, Table Q.1 · p. 84

Q.2 End-to-end matrix and phase composition: P1/P2/P3 … R.1 Deployment environment and evidence semantics

Across production profiles, IBLT performance is relatively stable across network tiers, while Merkle-style localization becomes costly when differences span many dirty ranges; self-sizing succeeds after one failed first round and deployment tests define its cross-city applicability. The evaluations also show that scan and production boundary-generation costs materially shape end-to-end runtime.

Q.2 End-to-end matrix and phase composition: P1/P2/P3

  • At 10 Mbps, Merkle-style is faster on P3 (137.5 s versus 149.5 s), but trails IBLT on P1 by about 360 s (1020.3 s versus 657.4 s) because dirty-range drill dominates.Both methods share a whole-table fingerprinting floor; P3 has 18 differences and near-zero drill, whereas P1’s drill rises sharply with dirty-range volume.Source: §Q.2 · pp. 85–86

Q.3 Worst case of the comparison path

  • In the stress case, Merkle-style drill-down nearly becomes whole-table retransmission, three 10 Mbps configurations fail to complete, while IBLT’s scan-dominated runtime rises only 2%–9%.The injected case increases dms from 93,130 to 154,098; IBLT transfer depends on measured difference cardinality rather than key-range distribution.Source: §Q.3 · p. 87, Table Q.5 · p. 87
  • Measurement before decoding lets extremely overloaded runs return FALLBACK without transmitting an over-budget second-round sketch.This avoids paying the localization path’s already-incurred runtime, which exceeded five hours on P1-extra.Source: §Q.3 · p. 87

Q.4 Ablation matrix: worker concurrency

  • On the P2 72-run concurrency matrix, W16 is best for IBLT, W64 gives the lowest Merkle-style median, and every repetition range stays within 15%.Higher IBLT concurrency shifts the bottleneck to MySQL, while Merkle-style gains mainly arise in boundary/checksum processing.Source: §Q.4 · p. 88, Table Q.6 · p. 88, Figure Q.2 · p. 88

Q.5 Capacity-setting actions and per-run estimates

  • With fixed M1 = 512, P1 and P2 set M2 once from the estimate and decode successfully with residual=0, while P3’s 18 differences decode in round one.The capacity rule is M2 = ⌈1.52 × 1.20 bd⌉, and recovery matches injected differences item by item.Source: §Q.5 · p. 89

Q.6 Implementation notes and optimization of the comparison baseline

  • Production Merkle-style boundary generation can dominate runtime: a 31M-row composite-key table spends nearly 30 minutes on boundary, versus about 5 s after replay optimization.The production path is serial and difficult to optimize across database engines; tables without a primary or unique key are unusable for localization.Source: §Q.6 · pp. 89–90

R Cross-City KV Field Deployment and Applicability

  • The cross-city KV deployment tests self-sizing on Redis and Pika over a 10 Mbps, 28.8 ms RTT link with approximately 4,890,077 keys and verifies recovered differences against observed scan windows.It complements relational experiments by hash-bucketing keys and evaluating a real cross-city link under online updates.Source: R Cross-City KV Field Deployment and… · p. 90, §R.1 · p. 90

R.1 Deployment environment and evidence semantics

  • R.1 fixes single-threaded scans and uses 4,096 Merkle-style buckets with self-sizing IBLT capacity M1 = 512, isolating method differences from scan-concurrency effects.Both methods therefore bear the same local scan cost, while IBLT’s comparison benefit comes from cross-city payload and rounds.Source: §R.1 · p. 90

R.2 Per-tier end-to-end data … Proportional-growth direction

The deployment results show that IBLT end-to-end time remains near the scan floor, while its estimator sets sufficient second-round capacity without additional requests. Supplementary analyses specify cross-engine hashing and canonicalization, quantify fingerprint-collision exposure, and provide conservative finite-sample guarantees and a proposed proportional-growth extension.

R.2 Per-tier end-to-end data

  • 93.7%–99.1% of IBLT end-to-end time is scan cost across G1–G2 tiers, and all six groups recover every required difference.The Redis→Redis scan floor is about 28.1 s, while Redis→Pika’s single-threaded disk scan floor is about 73–80 s; remaining IBLT times stay near their scan floors.Source: §R.2 · p. 90, Table R.2 · p. 92

R.3 Estimate deviation and second-round capacity setting

  • The largest estimate deviation is +8.1%, and M2 = ⌈1.824 bd⌉ sets sufficient second-round capacity in every triggering run without FALLBACK or REJECT.Recorded estimates map exactly to capacities 534.1→975, 932.1→1,701, and 1,132.4→2,066; no run requires another capacity request.Source: §R.3 · p. 91, Table R.3 · p. 92

R.4 Payload composition

  • Per-bucket payload averages about 126.5 KB, measured effective throughput is about 1.211 MB/s, and Merkle-style time rises from 28.3 s to 121.0 s as d increases from 1 to 937.The payload model uses 106.0 B per row, about 1,194 rows per bucket, and a 268 KB checksum vector for B = 4096; its four non-zero points deviate by at most 0.8%.Source: §R.4 · p. 91, Table R.2 · p. 92

Supplementary Material; Hash function availability across engines; Per-engine extraction of the 56-bit fingerprint

  • MD5 is built into all four evaluated engines, whereas CRC32 is exposed only by MySQL, making 56-bit MD5 the common fallback, with pairwise byte-level equivalence verification required.The replay concatenates ordered primary-key and business-value columns with CHAR(31), converts the complete canonical string to lowercase, and extracts the first 56 MD5 bits.Source: Supplementary Material · p. 93, Hash function availability across… · p. 94

Fingerprint width and collision risk

  • A 56-bit fingerprint has an expected 2.6 colliding pairs in the largest replay table, but cross-side difference collisions are estimated at only about 7 × 10−12 to 3 × 10−8 per run.Such collisions can silently miss differences when the pair straddles the two sides; deployments can widen fingerprints to 64 or 128 bits at proportional transfer cost.Source: Fingerprint width and collision risk · p. 95

Semantic normalization selected per deployment; Pairwise hash recommendation

  • Canonicalization is deployment-selected: policies such as trimming, rounding, or treating NULL as empty deliberately merge rows and therefore introduce missed differences.The evaluated default compares canonical texts byte-for-byte, with a '<NULL>' sentinel distinct from the empty string; native hashes are recommended only after fixed-sample pairwise verification.Source: Semantic normalization selected per… · p. 95, Pairwise hash recommendation · p. 96

Explicit failure-conditioned quantiles (safety floor for §2.5); Finite-sample refinement of the conditional transfer; Finite-sample Kolmogorov bound; Proof of Proposition 2.8 and explicit failure-conditioned quantiles

Proportional-growth direction

  • The proportional-growth direction targets transition loads with d/M → α and suggests MpF →∞, but it provides no protocol guarantee or empirical calibration in this paper.A quantitative de Jong route would control quadratic energy and maximum coordinate influence to establish standardized Gaussian stability, requiring sharper error control to distinguish the chi-square reference.Source: Proportional-growth direction · p. 100
Loading 2608.26537v1…