2025/09/02 by Francisco Lázaro, Lázaro, Francisco, Čedomir Stefanović +1
Computer Science · #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.2509.02373
openalex publication_date 2025/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.