DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

A rate-compatible solution to the set reconciliation problem

Lazaro, Francisco and Matuz, Balazs (2023) A rate-compatible solution to the set reconciliation problem. IEEE Transactions on Communications. IEEE - Institute of Electrical and Electronics Engineers. doi: 10.1109/TCOMM.2023.3296630. ISSN 0090-6778.

[img] PDF - Preprint version (submitted draft)


We consider a set reconciliation setting in which two parties hold similar sets that they would like to reconcile. In particular, we focus on set reconciliation based on invertible Bloom lookup tables (IBLTs), a probabilistic data structure inspired by Bloom filters. IBLT-based set reconciliation schemes have the advantage of exhibiting low computational complexity, however, the schemes available in the literature are known to be far from optimal in terms of communication complexity (overhead). The inefficiency of IBLT-based set reconciliation can be attributed to two facts. First, it requires an estimate of the cardinality of the difference between the sets, which implies an increase in overhead. Second, to cope with uncertainties in the estimation of the cardinality of the set difference, IBLT schemes in the literature oversize the data structures, thus further increasing the overhead. In this work, we present a novel IBLTbased set reconciliation protocol that does not require estimating the cardinality of the set difference. The proposed scheme relies on what we termed multi-edge-type (MET) IBLTs. The simulation results illustrate that the novel scheme outperforms state-ofthe-art IBLT-based approaches to set reconciliation in terms of communication cost, i.e., in terms of the number of bits to be exchanged.

Item URL in elib:https://elib.dlr.de/198952/
Document Type:Article
Title:A rate-compatible solution to the set reconciliation problem
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Lazaro, FranciscoUNSPECIFIEDhttps://orcid.org/0000-0003-0761-7700UNSPECIFIED
Matuz, BalazsUNSPECIFIEDhttps://orcid.org/0000-0002-0133-6564UNSPECIFIED
Date:October 2023
Journal or Publication Title:IEEE Transactions on Communications
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:Yes
Publisher:IEEE - Institute of Electrical and Electronics Engineers
Keywords:set reconciliation
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Communication, Navigation, Quantum Technology
DLR - Research area:Raumfahrt
DLR - Program:R KNQ - Communication, Navigation, Quantum Technology
DLR - Research theme (Project):R - Global Connectivity for People and Machines
Location: Oberpfaffenhofen
Institutes and Institutions:Institute of Communication and Navigation > Satellite Networks
Deposited By: Lazaro, Francisco
Deposited On:08 Nov 2023 16:50
Last Modified:08 Nov 2023 16:50

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.