Range-Based Set Reconciliation via Range-Summarizable Order-Statistics Stores

Read full text Summarise with VIRAT
Authors: Elvio Gilberto Amparore
Cited by: 0
References: 12

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Range-Based Set Reconciliation (RBSR) synchronizes ordered sets by recursively comparing summaries of contiguous ranges and refining only the mismatching parts. While its communication complexity is well understood, its local computational cost fundamentally depends on the storage backend that must answer repeated range-summary, rank, and enumeration queries during refinement. We argue that a natural storage abstraction for RBSR implementations based on composable range aggregates is a \emph{range-summarizable order-statistics store} (RSOS): a dynamic ordered-set structure supporting composable summaries of contiguous ranges together with rank/select navigation. This identifies and formalizes the backend contract needed for efficient recursive refinement, combining range-summary support with order-statistics navigation for balanced partitioning. We then show that a specific augmentation of B\textsuperscript{+}-trees with subtree counts and composable summaries realizes a RSOS, and we derive corresponding bounds on local reconciliation work in this abstract storage model. Finally, we introduce AELMDB, an extension of LMDB that realizes this design inside a persistent memory-mapped engine, and evaluate it through an integration with Negentropy. The results show that placing the reconciliation oracle inside the storage tree substantially reduces local reconciliation cost on the evaluated reconciliation-heavy workloads compared with an open-source persistent baseline based on auxiliary tree caches, while the window-subrange ablation further confirms the usefulness of the systems optimizations built on top of the core aggregate representation.

Fields of Study & Subjects

Advanced Database Systems and Queries Distributed systems and fault tolerance Algorithms and Data Compression

Publication details

Journal / source
arXiv (Cornell University)
Publication date
20 March 2026
Language
EN
Document type
Preprint