{"ID":2875468,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.02373","arxiv_id":"2509.02373","title":"Tree algorithms for set reconciliation","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2509.02373","url_pdf":"https://arxiv.org/pdf/2509.02373v1","authors":"[\"Francisco Lázaro\",\"Čedomir Stefanović\"]","published":"2025-09-02T14:40:25Z","proceeding":"cs.NI","tasks":"[\"cs.NI\",\"cs.DS\",\"cs.IT\"]","methods":"[]","has_code":false}