Tree algorithms for set reconciliation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908515617996800 |
|---|---|
| author | Lázaro, Francisco Stefanović, Čedomir |
| author_facet | Lázaro, Francisco Stefanović, Čedomir |
| contents | In this work, a set reconciliation setting is considered in which two parties have similar sets that they would like to reconcile. In particular, we focus on a divide-and-conquer strategy known as partitioned set reconciliation (PSR), in which the sets to be reconciled are successively partitioned until they contain a number of differences below some predetermined value. Borrowing techniques from tree-algorithms for random-access protocols, we present and analyze a novel set reconciliation scheme that we term enhanced partitioned set reconciliation (EPSR). This approach improves the efficiency in terms of overhead, i.e., it yields a lower communication cost, while keeping the same time and communication round complexity as PSR. Additionally, we simulate the performance of the proposed algorithm in an event-driven simulator. Our findings indicate that this novel protocol nearly halves the communication cost of PSR while maintaining the same time complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02373 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tree algorithms for set reconciliation Lázaro, Francisco Stefanović, Čedomir Networking and Internet Architecture Data Structures and Algorithms Information Theory In this work, a set reconciliation setting is considered in which two parties have similar sets that they would like to reconcile. In particular, we focus on a divide-and-conquer strategy known as partitioned set reconciliation (PSR), in which the sets to be reconciled are successively partitioned until they contain a number of differences below some predetermined value. Borrowing techniques from tree-algorithms for random-access protocols, we present and analyze a novel set reconciliation scheme that we term enhanced partitioned set reconciliation (EPSR). This approach improves the efficiency in terms of overhead, i.e., it yields a lower communication cost, while keeping the same time and communication round complexity as PSR. Additionally, we simulate the performance of the proposed algorithm in an event-driven simulator. Our findings indicate that this novel protocol nearly halves the communication cost of PSR while maintaining the same time complexity. |
| title | Tree algorithms for set reconciliation |
| topic | Networking and Internet Architecture Data Structures and Algorithms Information Theory |
| url | https://arxiv.org/abs/2509.02373 |