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

Database reconciliation must choose IBLT capacity despite widely varying, initially unknown difference cardinality. The paper estimates d directly from the IBLT count channel, extends the estimator across IBLT variants, and uses a failed first round to resize in one step. The resulting protocol completes within two round trips, with production profiling and deployment evidence supporting its system scope.

  • Problem

    Database reconciliation faces unknown difference cardinality spanning orders of magnitude, while capacity undersizing causes rescans and oversizing wastes network and memory.

  • Method

    A mapping-aware quadratic statistic estimates d from the same IBLT count channel, with adapters for Irregular, Rateless, and MET variants and failure-conditioned analysis.

  • Results

    The self-sizing protocol computes second-round capacity after first-round failure and holds interaction to 2 RTTs at roughly 1.3–1.7× the oracle’s bytes.

  • Takeaways & Limitations

    The first reconciliation round becomes both a decoding attempt and a measurement, allowing capacity to be set from the sketch already transmitted.

  • Takeaways & Limitations

    The chi-square interval is asymptotic for fixed M as d grows, while operating calibration uses empirical quantiles and a conservative finite-sample certificate.

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

Set reconciliation uses IBLTs to recover differences efficiently, but unknown difference cardinality makes capacity selection costly in database workloads. This paper reuses the failed sketch to estimate the difference and size a second attempt within two round trips.

  • Set reconciliation recovers A△B with communication far smaller than transmitting both sets, and IBLTs are a standard tool.
  • Database verification scans and fingerprints every record, so choosing IBLT capacity too small causes rescans while choosing it too large wastes bandwidth and memory.The measured difference cardinality spans seven orders of magnitude across 41,603 NineData runs, with d = 0 in 56.4% of runs and differences in 98.7% of cost-dominant tables.
  • Merkle-style localization is cheap for clustered differences but can approach whole-table transfer when differences are scattered.
  • A pre-peeling quadratic statistic over IBLT counts gives an exactly unbiased estimate of d without extra transmitted bytes, including after decoding failure.Its variance is 2d(d−1)/(M−1), independent of hash count k, and fixed-M asymptotics provide chi-square confidence intervals.
  • A mapping-aware construction extends the estimator to Irregular, Rateless, and MET IBLTs through variant-specific adapters.The construction centers within the smallest mapping-homogeneous block and normalizes by the mapping covariance.
  • The self-sizing protocol reads the estimate after first-round failure, computes second-round capacity directly, and completes in at most two round trips.Compared with blind doubling and Strata-first, it uses roughly 1.3–1.7× the oracle byte cost across the range of d.

2 Plain IBLT Count Measurement

The Plain IBLT count channel provides an exactly unbiased estimate of the difference cardinality, with precision governed by table size and validity preserved when decoding fails. Its distribution supports chi-square-based tail calibration, while experiments confirm the theoretical accuracy across loads, mappings, and sign compositions.

  • Exact measurement: The normalized estimator is exactly unbiased for finite M, d, and k, regardless of the balance between the two difference sides.The expectation remains d under arbitrary sign patterns, so no separate cardinality sketch is needed.
  • Precision: Its relative error decreases as M^-1/2, with RSD about 8.9% at M = 256 and 4.4% at M = 1024.Roughly quadrupling the table dimension halves the typical relative error.
  • Distribution and confidence: The chi-square limit captures the estimator’s right-skewed distribution and provides more accurate lower-quantile calibration than a symmetric normal approximation.The normal approximation systematically underestimates lower quantiles, whereas the chi-square prediction tracks empirical quantiles closely.
  • Validity after failure: Failure conditioning preserves the measurement under random signs, while the chi-square shape remains predictive in deep overload and empirical transition-regime tests.At d/M = 8, the success-probability bound was at most 3.7 × 10^-6; transition-regime conditional means ranged from 0.9998 to 1.0001.
  • Validity after failure: The certified chi-square transfer applies in deep overload, but near the peeling transition the analytic conditional-shape guarantee is vacuous and failed-only empirical quantiles are used.For k = 3, the bound becomes nonvacuous around d/M = 4.5–6.1, while d/M ≤ 1.6 remains outside its guarantee.
  • Empirical validation: Across 160 configurations, the maximum mean deviation was 4.7 × 10^-4 and the measured-to-theoretical RSD ratio stayed within [0.9981, 1.0018].The agreement showed no systematic drift with k, load, or sign composition, and k = 3 and k = 4 had matching RSDs.
  • Empirical validation: At M = 64, the estimator had 18% RSD and a 1% quantile near 0.63d, improving to 4.4% and 0.90d at M = 1024.The trade-off is precision: smaller first-round sketches remain unbiased but produce wider confidence intervals.

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

A mapping-aware theorem turns pre-decoding count energy into an unbiased difference-cardinality measurement across Plain, Irregular, Rateless, and MET IBLTs. Variant-specific adapters center the appropriate baseline and normalize by mapping covariance, while failure-path analysis supplies conditional estimates and intervals.

  • Unifying theorem: Theorem 3.1 constructs unbiased quadratic count estimators from each variant’s mapping mean and covariance.The hit vector’s mean and covariance determine how to remove stable write patterns and convert centered energy into the number of difference elements.
  • Adapter design: Correct adapters first center within the smallest mapping-homogeneous block, then normalize by the true mapping covariance.Plain uses global centering; Irregular uses degree moments, Rateless uses per-symbol hit probabilities, and MET centers per cell type.
  • Irregular adapter: Irregular’s adapter preserves Plain’s global centering while changing only the normalization constant, and its estimator is unbiased.The validation uses the original Irregular degree distribution across multiple sketch dimensions and sign compositions.
  • Validation: 0.22% is the maximum relative difference between measured and closed-form Irregular RMSE, with no systematic drift across sign balance.The same closed form gives 5.5% RMSE at M = 1024 for a decode-scale batch with d = 1024.
  • Rateless adapter: Rateless prefixes gain measurement degrees of freedom as cells arrive, with relative variance decaying as O(1/m).The effective degrees of freedom are r = m −1, so longer received prefixes improve estimation without presetting capacity.
  • Failure conditioning: Conditional validity separates deterministic self-energy, which remains exactly unbiased, from random self-energy, which requires an explicit relative-deviation bound.Random self-energy creates a mapping-selection channel correlated with decodability; sign-channel effects remain zero under the stated conditions.
  • Failure conditioning: The four adapters share a failure-path interface, while interval construction differs between Plain/Rateless and Irregular/MET.Plain and Rateless use analytic intervals; Irregular and MET use failed-only empirical quantiles, with conditional deviations shrinking as failure probability approaches one.

4 Self-Sizing Protocol

The protocol uses a failed first-round IBLT to estimate the unknown difference cardinality and size a fresh second-round sketch in one step. It completes in at most two round trips while providing conditional success guarantees and near-oracle byte cost across varying d.

  • 4 Self-Sizing Protocol: The receiver estimates d from the failed first-round sketch, computes second-round capacity, and requests one fresh sketch.The first round is also the measurement used for sizing; first-round success provides a 1-RTT fast path.
  • 4.1 Two-round mechanism and protocol state: Pre-peeling counts must be saved before decoding because peeling rewrites them to represent the residual core rather than the full difference.The estimate is independent of how far peeling proceeds, so the order cannot be reversed.
  • 4.2 Capacity formula and success guarantee: The second-round capacity uses a failure-conditioned lower-quantile multiplier and a decoder operating point to bound conditional failure by δ + ηdec(β).The fresh independent hash makes the decoder guarantee apply uniformly over qualifying first-round failure histories.
  • 4.5 Configuration and operating boundaries: Joint peeling cannot reduce success probability when the first-round residual core and second-round sketch encode the same unknown elements.It adds no transmitted bytes, while the independently decodable second-round sketch preserves the standalone guarantee.
  • 4.6 Success-rate calibration: 99.901% failed-only second-round success is reached at α = 1.6 and M1 = 512, while the tightest tier reaches 99.855% at M1 = 256 and α = 1.8.These conditional rates avoid inflation from first-round trials that decode easily.
  • 4.7 Protocol cost under unknown difference cardinality: regret versus oracle: Self-sizing stays at about 2 rounds and 1.3–1.7× oracle bytes, versus 2.0–3.1× bytes and logarithmically growing rounds for blind doubling.Strata-first incurs 8–20× byte regret at small d because of its fixed 40 KB summary; its round advantage disappears for d ≥ 10^3.

5 System Evaluation and Applicability

Production evidence shows reconciliation workloads vary sharply in difference size and cost, while differences cluster in key space. Cross-engine replay and deployments show self-sizing IBLT reuses the initial scan, sizes capacity after failure, and recovers correctly with bounded interaction rounds.

  • End-to-end comparison: A 600M-row, approximately 93,000-difference profile placed self-sizing IBLT against the production Merkle baseline under network constraints.The evaluation compared actual replay and deployment execution with trace-driven production analysis, whose online logs did not run self-sizing IBLT.
  • Production workload: 1.3% of runs above 10^8 rows were equal, while 98.7% had differences; 89% of all runs completed in one round but contained less than 0.2% of observed differences.These results motivate a failure-conditioned measurement path for the difference-heavy runs.
  • Production workload: The most expensive 5% of runs carried 81% of cumulative table-level time, while the cheapest 90% accounted for under 3%.The extreme tail included median single-run times of 5.17 hours and median tables of 6.0 × 10^8 rows.
  • Production workload: Differences occupied only 3–24 of 100 key-rank buckets, with further scatter inside those clustered segments.The observed pattern was consistent with failures affecting particular worker-served key ranges, though the inferred fault sources were reported separately.
  • Protocol paths: All three production profiles recovered injected differences item by item, with P3 using the 1-RTT fast path and P1/P2 sizing one second-round capacity after failure.P3 ran directly at M1 = 512; P1 and P2 read pre-peeling counts, resized once, rehashed, and jointly peeled.
  • End-to-end comparison: The shared full-table scan dominated end-to-end cost, while self-sizing added almost nothing above that unavoidable floor.On P1, scanning exceeded nine tenths of self-sizing IBLT time; subtraction, peeling, and recovery together were single-digit percentages.

6 Related Work

Prior approaches either add a separate estimator, retry with larger sketches, or incrementally transmit symbols. This paper instead extracts cardinality from the decoding sketch itself and uses that measurement for self-sizing.

  • Existing protocols configure IBLT capacity using a separate estimator or prior knowledge of the difference cardinality.
  • Blind doubling avoids extra estimation structures but adds rounds whose database cost often includes another full-table scan.
  • Rateless IBLTs avoid preset capacity through incremental symbol transmission, assuming the sender can produce symbols on demand.
  • Self-sizing reads a mapping-aware second-moment estimate from the already transmitted first-round IBLT, adding no estimation-only bytes.
  • On a 609M-row production snapshot, the incremental Rateless encoder was approximately 48× slower and used approximately 93 GiB endpoint memory versus a few tens of MiB for self-sizing.
  • The paper derives exact mean and variance, a chi-square limit, and failure-conditioned lower-tail guarantees for its estimator.

7 Scope and Limitations

The guarantees apply within explicit mapping, channel, snapshot, configuration, and workload boundaries. Several extensions and operational decisions remain outside the paper’s supported scope.

  • The weighted frequency model preserves expectation identities, but its exact variance and confidence intervals require separate derivations.
  • The theory assumes independent ideal-random mappings, k distinct cells per element, and non-adversarial keys; random-sign conditional guarantees additionally require signs independent of mappings.
  • Measurement requires signed, unclipped, losslessly represented counts with sufficient counter width; overflow or saturation destroys the second moment and triggers rejection.
  • Changing the hash mapping, sketch structure, or operating range requires re-obtaining the failure-conditioned lower quantile for that configuration.
  • The chi-square confidence interval is asymptotic for fixed M as d grows, while practical operation uses empirically calibrated quantiles with finite-sample certification.
  • Exact recovery is relative to the scan-window input sets; same-instant semantics require external consistency mechanisms that this protocol does not provide.
  • Beyond the resource boundary, choosing manual inspection, a full snapshot, partition comparison, or direct rebuild is an operational decision outside the paper.

8 Conclusion

The paper turns the IBLT’s pre-decoding count state into a cardinality measurement and uses it to size reconciliation dynamically. It establishes statistical guarantees, extends the interface across IBLT variants, and completes the main protocol within two rounds.

  • The decoding sketch measures the unknown difference cardinality before decoding, so failed sketches retain useful information rather than being discarded.
  • The estimator is exactly unbiased with closed-form variance, admits a chi-square confidence interval, and remains valid after first-round failure.
  • A mapping-aware theorem extends the estimate interface to Irregular, Rateless, and MET IBLTs through variant-specific adapters.
  • After a first-round failure, the protocol computes second-round capacity in one step and completes within 2 RTTs, with a stated success-probability guarantee.
  • Self-sizing keeps the interaction count near 2 at 1.3–1.7× the oracle’s bytes, while blind doubling requires logarithmically growing rounds.
  • The evaluation profiles 41,603 production runs over 90 days and examines workload, cost, and cross-environment behavior.
  • The evaluation focuses on scan-expensive request/response deployments with signed, unclipped count channels; weighted-model intervals and other extensions remain future work.

C Proof of Theorem 2.2 (Exact Variance)

The exact variance proof centers the pre-peeling count energy and expands its pairwise mapping contributions. Diagonal terms are deterministic, cross terms are analyzed by hypergeometric overlap, and normalization removes the mapping scale.

  • The diagonal contribution is deterministic because each element maps to exactly k distinct cells.
  • For distinct elements, overlap counts follow a hypergeometric distribution with mean k^2/M.
  • Pairs sharing no element have zero covariance because their mappings are mutually independent.
  • Pairs sharing one element are pairwise uncorrelated after conditioning on the shared mapping.
  • Only identical unordered element pairs survive the double-sum expansion, because squared sign products equal one.
  • Dividing the count energy by γ normalizes away the factors involving k and M−k, yielding a variance independent of k and sign balance.
  • The resulting exact estimator variance is Var(bd) = 2d(d −1)/(M −1).

D Proof of Theorem 2.4 (Chi-Square Limit)

The proof derives the chi-square limit by showing that centered count fluctuations converge to an isotropic Gaussian on an (M−1)-dimensional subspace, whose squared norm yields the limit. It then transfers this law to failed instances through total-variation control.

  • Gaussian limit: The centered count vector is a sum of independent bounded mapping vectors with zero mean and covariance proportional to the centering projection.The Lindeberg–Feller triangular-array CLT applies even for fixed, non-identical sign sequences.
  • Gaussian limit: The centered subspace has dimension M−1, so the Gaussian limit has M−1 independent coordinates with common variance.An orthonormal basis of the subspace makes the limiting coordinates i.i.d. normal.
  • Chi-square mapping: The quadratic centered energy is the squared norm of the projected count vector, so the continuous mapping theorem gives its chi-square limit.The projection identity Q^2 = Q converts T into ||QC||^2.
  • Normalization: For fixed M, the normalization identity matches the relative-variance limit 2/(M−1) implied by the exact finite-sample variance.This connects the asymptotic chi-square scale to Theorem 2.2.
  • Failure conditioning: Conditioning on decoding failure preserves the chi-square law asymptotically because the failure event removes an asymptotically negligible fraction of mappings.The total-variation distance between conditional and unconditional laws is controlled by the failure probability.
  • Failure conditioning: The inheritance argument applies to every deterministic sign sequence fixed independently of mapping randomness, including arbitrary fixed sign compositions.Multiplying mapping vectors by fixed signs preserves the relevant mean, covariance, boundedness, and independence properties.

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

The full-grid experiments validate the unconditional estimator across 160 configurations: exact mean and variance formulas agree with measurements, while chi-square interval accuracy improves with sketch dimension and load.

  • Full-grid design: 160 configurations cover four M tiers, two k tiers, five sign compositions, and four load tiers for the full-grid validation.The study checks variance accuracy, worst-case error, chi-square convergence, and interval coverage.
  • Variance validation: The measured RSD-to-Theorem-2.2 ratio stays in [0.9981, 1.0018] across all 160 configurations, with no visible k = 3 versus k = 4 separation.The ratio is measured RSD divided by the theoretical prediction, with 1 indicating exact agreement.
  • Chi-square validation: Chi-square quantile errors shrink with increasing M, from about 0.0040/0.0023/0.0039 at M = 64 to about 0.0001 at M = 4096.The three values correspond to the reported lower-tail, median, and upper-tail quantile errors.
  • Coverage: The smallest configuration, (M, d) = (64, 26), has about 0.5 percentage points of coverage error, while all tiers at M ≥256 stay below 0.3 percentage points.At M = 4096, the coverage error drops to 0.02 percentage points.
  • Protocol implication: The protocol uses the empirical failure-conditioned qF_0.01 for capacity planning because distribution-free lower-tail bounds can become nonpositive at δ = 0.01.Those analytic bounds remain safety floors rather than practical configuration inputs.

H Irregular Adapter Proofs and the Degenerate Boundary

The Irregular adapter derives unbiasedness from a centering projection and a degree-aware normalization, then isolates how degree heterogeneity affects the estimator’s center and dispersion.

  • Unbiasedness: The Irregular estimator is unbiased because the centered quadratic statistic has expected energy dγirr under independent random degrees.The normalization γirr accounts for the Irregular mapping’s degree distribution.
  • Variance structure: The relevant expectation depends only on the first four moments of the degree distribution, and the result reduces to Theorem 2.2 for the Plain IBLT.This identifies the moment requirements of the Irregular variance analysis.
  • Degenerate boundary: At M = 18, degree-18 elements hit every cell and contribute no centered energy because the projection removes the constant direction.The degree-aware normalization captures this degenerate contribution through E[D^2].
  • Degenerate boundary: Using the mean-degree plug-in gives γmean = 3.4847 instead of γirr = 2.0792 and introduces a downward bias factor of 0.5967.The plug-in overestimates average energy production in this extreme configuration.
  • Error decomposition: The same configuration has relative RMSE ≈0.34 because smaller M increases overlap fluctuations between distinct difference elements.Normalization controls the estimate’s center, whereas dispersion depends on M and degree-dependent self-energy.

I Rateless Prefix Adapter Proofs

The Rateless adapter uses independent prefix-hit indicators to construct an exactly unbiased average-of-ratios estimator and a chi-square approximation, while experiments validate the sampler and identify finite-sample calibration effects.

  • Kernel and paths: The Rateless transition kernel is obtained by differencing its cumulative degree distribution, and the path-hitting probabilities satisfy a renewal recurrence.The recurrence is verified by induction from the candidate closed form.
  • Pairwise independence: Fresh independent jumps make hit indicators independent, with Pr[Bi = 1, Bj = 1] = qiqj.The result follows because a path’s history before one hit is independent of subsequent jumps.
  • Estimator: Each standardized cell energy is an unbiased estimator of d, so averaging the ratios yields the Rateless estimator.For cell i, the normalization is qi(1 −qi).
  • Estimator: For non-diagonal covariance, the generalized estimator uses the Moore–Penrose pseudoinverse; Rateless pairwise independence reduces it to the diagonal average-of-ratios form.The covariance rank is r = m−1 under the stated non-degeneracy condition.
  • Estimator caveat: The ratio-of-sums alternative has the same mean but a different weighted-chi-square distribution and reduces nominal 90% coverage to approximately 50%.The Proposition 3.7 interval is valid only for the average-of-ratios form.
  • Validation: Across 63 cells, coverage stays within 0.324 percentage points of nominal, with the residual largest at the smallest d/r tier.A separate 18-cell sampler diagnostic stays within 0.22 percentage points, and the fresh-uniform test attributes the residual to finite-(d,m) calibration rather than PRNG recursion.
  • Validation: The two samplers agree with analytic hit probabilities and pairwise moments across 109 paths and 522,753 tested cell pairs.The observed joint-frequency deviations are consistent with sampling noise.

J Rateless IBLT: Production-Scale Comparison

The study compares self-sizing Plain IBLTs with fixed-prefix and incremental Rateless IBLTs under database reconciliation’s scan-dominated cost model. Self-sizing avoids Rateless’s large mapping-state costs while retaining measurement and successful two-round decoding.

  • Experimental setup: All methods share the same row-fingerprint snapshot, isolating reconciliation algorithm costs from the common scan.The comparison uses production-shaped P2 and P1-extra snapshots.
  • Experimental setup: Self-sizing uses a 512-cell first round and α = 1.824, while Rateless methods use either a fixed 249,555-symbol prefix or incremental symbols starting at 1,024.The fixed prefix is substantially above P2’s approximately 5,932-symbol minimum.
  • Results: ∼120 s: self-sizing completes P1-extra far faster than fixed-prefix Rateless at ∼490 s and incremental Rateless at ∼5,800 s.The incremental method is about 48× slower than self-sizing on this snapshot.
  • Results: ∼93 GiB: incremental Rateless endpoint memory peaks three orders of magnitude above self-sizing’s few-tens-of-MiB endpoint peak.Incremental Rateless has the lowest wire bytes on this snapshot, but its endpoint resource costs dominate.
  • Interpretation: Rateless’s O(N) mapping and scheduling state converts its bandwidth advantage into a wall-time and memory disadvantage for large, scan-dominated request/response workloads.Plain IBLT encoding is stateless and scales with table dimension M rather than row count N.
  • Measurement limits: Partial Rateless prefixes require finite-prefix correction and an identifiability check before estimating total F2.The matrix adapter may be identifiable yet highly ill-conditioned, whereas the known-pj scalar path is more stable and is used by default.

N.1 First-round capacity tiers and capacity multipliers

The protocol trades first-round fixed cost against estimation precision and the multiplier used to size the second round. Across the evaluated phase diagram, self-sizing generally matches or improves on Strata-first byte cost, with a narrow high-d exception.

  • Protocol semantics: δ = 0.01: the protocol targets a 99% failure-conditioned lower-tail probability, using q0.01 to control severe underestimation risk.Table N.1 selects multipliers from q0.01, while Table N.2 evaluates resulting decoding success.
  • Protocol semantics: RSD(bd) ≈ 2/(M1 −1): increasing M1 improves estimation precision and raises qδ, which lowers the recommended second-round multiplier.The parameter chain is M1 → precision → qδ → α.
  • Capacity tiers: M1 = 64, 256, 512, and 1024 cells yield recommended multipliers 2.09, 1.63, 1.52, and 1.45, respectively.First-round fixed bytes rise from the minimal-cost 64-cell tier to 32 KB at 1024 cells.
  • Capacity tiers: 99.336%, 99.901%, and 99.955%: at α = 1.6, M1 = 256, 512, and 1024 achieve these reported protocol success rates.The lower multiplier is below M1 = 256’s recommendation but above the recommendations for the two larger tiers.
  • Comparison with Strata-first: 71 of 72 phase-diagram cells have self-sizing+joint byte ratio at most 1 relative to Strata-first.The sole exception is M1 = 64, d = 105, with ratio 1.02; for M1 ≥256, the whole line stays at most 0.87.
  • Comparison with Strata-first: Strata-first’s round advantage is confined to a narrow small-d band where its bottom layer directly enumerates differences.For M1 ≥256, self-sizing’s first-round decodable range covers that window and the round advantage disappears.
  • Comparison with Strata-first: 2.32×: with d = 0 in 95% of requests, Strata-first’s expected bytes exceed self-sizing+joint under M1 = 64.The configuration uses a 2 KB self-sizing first-round cost versus Strata’s 40 KB summary.
  • Comparison with Strata-first: At d = 1000, a 1024-cell Plain estimator uses 20% fewer cells than Strata’s 1280-cell configuration while providing exact mean, variance, and chi-square analysis.The same-budget comparison uses a 1280-cell first-round budget.

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

The production log contains 41,603 row-level reconciliation runs over 90 days after explicit filtering. Timing is dominated by large tables and concentrated workloads, while most small differences are first-round decodable but contribute little total difference mass.

  • Sample and semantics: 41,603 runs: the filtered sample covers 2026-04-29 through 2026-07-28 and retains table-level executions with row-level comparison.Entries lacking executable tables, comparable data, primary keys, or valid nonempty inputs were removed.
  • Difference profiles: 89.1% of runs finish within one first-round interaction when zero differences are included.Among nonzero differences, 75.1% have dms ≤393 and are directly decodable by a 512-cell, 16 KB IBLT.
  • Difference profiles: 0.175% of total difference mass lies in those first-round-decodable records, because mass concentrates in records above p99.Thus run frequency and difference mass have sharply different distributions.
  • Difference profiles: 146 consecutive-difference episodes appear over 90 days; 96.4% of positive-difference time belongs to persisting episodes.Half of the episodes appear once, one third persist through the window, and the intermediate dozens-of-runs category does not occur.
  • Cost concentration: 99.2% of table-level time comes from the largest two table-size deciles, whereas the cheapest 80% of runs account for 0.7%.Small tables are dominated by fixed operational costs; large tables are dominated by scanning.
  • Cost concentration: 56.4% of records have d = 0, but one account contributes 90.6% of cumulative table-level time and 96.0% of records with N ≥10^8.Removing that account changes the zero-difference fraction to 54.5%, making account concentration a boundary of cost-weighted interpretation.

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

Cross-engine replay shows that both methods share a scan and fingerprinting floor, while their divergence comes from post-scan localization or IBLT phases. IBLT remains stable across network tiers, whereas Merkle-style cost grows with dirty-range volume and can fail to complete when differences are widely scattered.

  • Network sensitivity: IBLT varies little across the three network tiers, while Merkle-style P1 time rises mainly through dirty-range drill-down.Batched detail requests prevent request count from translating into linear RTT amplification.
  • Phase composition: All runs share whole-table row normalization and fingerprint computation, which dominates end-to-end time for both IBLT and Merkle-style methods.The comparison therefore separates common scan cost from the smaller but divergent remaining phases.
  • Profile comparison: 137.5 s versus 149.5 s: Merkle-style is faster than IBLT for P3 at 10 Mbps because P3 has only 18 differences and negligible drill cost.Both methods remain close to the checksum-dominated lower bound.
  • Profile comparison: 1020.3 s versus 657.4 s: Merkle-style trails IBLT for P1 at 10 Mbps when many differences create a wide dirty region.The reported gap comes entirely from dirty-range lookup volume.
  • Scattered-difference stress test: Scattered differences sharply increase Merkle-style drill-down because localization cost depends on the number of dirty blocks rather than difference cardinality.Under the stress case, three tested 10 Mbps configurations did not complete the drill phase.
  • Protocol consequence: When estimated capacity exceeds budget, measurement permits immediate FALLBACK before transmitting an oversized second-round sketch.The alternative localization path learns dirty-range volume only after further processing.
  • P2 matrix: W16 is the best-performing IBLT setting for P2, while W64 gives the lowest Merkle-style median and W32 is close.Across the 72-run matrix, all min–max ranges stay within 15%.
  • Self-sizing validation: P3’s 18 differences decode in round one, while P1 and P2 set M2 once from the first-round estimate and decode successfully with residual = 0.The reported rule is M2 = ⌈1.52 × 1.20 bd⌉ for the latter profiles.

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

The six-run deployment verifies accurate pre-decoding estimation and one-shot second-round sizing, while reporting end-to-end scan, transfer, and throughput behavior across scenarios.

  • All six scenario groups recover every difference against injected ground truth or observed run differences.G3 and G6 use observed differences because they lack fixed ground truth.
  • The Redis→Redis scan floor is about 28.1 s, while the Redis→Pika disk SCAN floor is about 73–80 s.These floors provide the scan-cost baseline for interpreting the end-to-end results.
  • +8.1% is the largest estimate deviation across six runs, consistent with the theoretical 6.3% relative standard deviation at M1 = 512.The deployment measurements and theory agree within the reported limited-sample fluctuation.
  • M2 = ⌈1.824 b_d⌉ sizes the second round, and all second-round-triggering runs decode successfully without fallback or rejection.Recorded estimates map exactly to capacities 975, 1,701, and 2,066, while no run needs another capacity request.
  • 126.5 KB per dirty bucket and a 268 KB checksum vector explain the reported payload model at B = 4096.The model uses a 106.0 B per-row payload and an average bucket size of about 1,194 rows.
  • 1.211 MB/s is the measured effective throughput, while Merkle-style end-to-end time rises from 28.3 s to 121.0 s as d increases from 1 to 937.The Merkle-style increase is approximately 93 s over that difference-cardinality range.
Loading 2608.26537v1…