Metraipolis › archive › dc_bf46c8f7779f

Random-Sign IBLTs: Calibration-Free Self-Sizing After Decoding Failure — arXiv:2610.41211

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41211
License (as archived)
CC0-1.0
Archived
2026-11-02T08:06:43.740Z
SHA-256 of the archived text
0814eae88d47f4ce5f38dc1f18e8f0ce8a24dee65f23990c0f8909f3ce084247
Stable URL of this page
https://metraipolis.com/documento/dc_bf46c8f7779f

How to cite

Random-Sign IBLTs: Calibration-Free Self-Sizing After Decoding Failure — arXiv:2610.41211 — arXiv (en), https://arxiv.org/abs/2610.41211 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bf46c8f7779f (Metraipolis archive dc_bf46c8f7779f, sha256 0814eae88d47f4ce5f38dc1f18e8f0ce8a24dee65f23990c0f8909f3ce084247)
BibTeX
@misc{dcbf46c8f7779f,
  title = {Random-Sign IBLTs: Calibration-Free Self-Sizing After Decoding Failure — arXiv:2610.41211},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41211},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bf46c8f7779f; sha256 0814eae88d47f4ce5f38dc1f18e8f0ce8a24dee65f23990c0f8909f3ce084247},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41211. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We propose the random-sign Invertible Bloom Lookup Table (IBLT) for calibration-free self-sizing after decoding failure. In a two-round set reconciliation protocol, the receiver uses the failed first-round table to estimate an upper bound on the unknown difference size $d$ and size the second-round table. In standard IBLTs, failure selection couples the overlap bias with the sign composition of the set difference, making practical sizing depend on offline simulation calibration. A shared pseudorandom sign independent of the position mapping removes this dependence while preserving cell fields, field widths, and ideal peeling recovery. We prove exact unbiasedness on every fixed mapping, a Gaussian limit after failure for $d\gg\sqrt M$, and a discrete limit dominated by duplicate edge pairs at smaller scales, where $M$ is the number of cells. These results yield a Skellam upper-bound rule whose conditional miss rate is asymptotically at most the target risk, uniformly over all $d\ge2$, without offline calibration. More than 500 million paired decoding trials and end-to-end protocol experiments support the design. For small differences, the Gaussian rule's conditional miss rate exceeds the target by more than a factor of 8. The Skellam rule meets the target within sampling error across all 189 tested load configurations. Total two-round communication approaches that of an oracle using the true $d$ in the same protocol. With fixed deployment parameters, precomputed table lookup reduces sizing to less than one microsecond, with total protocol time within 0.5 percent of the Gaussian rule.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41211 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T07:45:15.771Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).