{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T22:10:09Z","timestamp":1755900609993,"version":"3.44.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,5,27]]},"abstract":"<jats:p>Set reconciliation is a fundamental task in distributed systems, particularly in blockchain networks, where it enables the synchronization of transaction pools among peers and facilitates block dissemination. Existing traditional set reconciliation schemes are either statistical, providing success probability as a function of the communication overhead and the size of the symmetric difference, or require parametrization and estimation of the size of the symmetric difference, which can be prone to error. In this paper, we present CertainSync, a novel reconciliation framework that, to the best of our knowledge, is the first to guarantee successful set reconciliation without any parametrization or estimators in use. The framework is rateless and adapts to the unknown symmetric difference size. The set reconciliation is guaranteed to be completed successfully whenever the communication overhead reaches a lower bound derived from the symmetric difference size and the universe size. Our framework is based on recent constructions of Invertible Bloom Lookup Tables (IBLTs) ensuring successful element listing as long as the number of elements is bounded. We provide a theoretical analysis to prove the certainty in the set reconciliation for multiple constructions. The approach is also validated by simulations, showing the ability to synchronize sets with efficient communication costs while maintaining reconciliation guarantees compared to other baseline schemes for set reconciliation. To further improve communication overhead for large universes as blockchain networks, CertainSync is extended with a universe reduction technique to minimize communication overhead. We compare and validate the extended framework UniverseReduceSync against the basic CertainSync framework through simulations using real blockchain transaction hash data from the Ethereum blockchain network. The results illustrate a trade-off between improved communication costs and maintaining reconciliation guarantees without relying on parametrization or estimators, offering a comprehensive solution for set reconciliation in diverse scenarios.<\/jats:p>","DOI":"10.1145\/3727110","type":"journal-article","created":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T09:43:35Z","timestamp":1749030215000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["CertainSync: Rateless Set Reconciliation with Certainty"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-2711-104X","authenticated-orcid":false,"given":"Tomer","family":"Keniagin","sequence":"first","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9851-5234","authenticated-orcid":false,"given":"Eitan","family":"Yaakobi","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4064-1238","authenticated-orcid":false,"given":"Ori","family":"Rottenstreich","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2025,6,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Djamal Belazzougui Gregory Kucherov and Stefan Walzer. 2024. Better Space-Time-Robustness Trade-Offs for Set Reconciliation. In International Colloquium on Automata Languages and Programming (ICALP)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_3_1","volume-title":"SREP: Out-Of-Band Sync of Transaction Pools for Large-Scale Blockchains. In IEEE International Conference on Blockchain and Cryptocurrency (ICBC).","author":"Boskov Novak","year":"2023","unstructured":"Novak Boskov, Sevval Simsek, Ari Trachtenberg, and David Starobinski. 2023. SREP: Out-Of-Band Sync of Transaction Pools for Large-Scale Blockchains. In IEEE International Conference on Blockchain and Cryptocurrency (ICBC)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2022.3164369"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"John W. Byers Jeffrey Considine Michael Mitzenmacher and Stanislav Rost. 2002. Informed content delivery across adaptive overlay networks. In ACM SIGCOMM.","DOI":"10.1145\/633030.633031"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2024.3377222"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Graham Cormode and S. Muthukrishnan. 2004. An Improved Data Stream Summary: The Count-Min Sketch and Its Applications. In Latin American Theoretical Informatics (LATIN).","DOI":"10.1007\/978-3-540-24698-5_7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1003839"},{"key":"e_1_2_1_9_1","volume-title":"Smith","author":"Dodis Yevgeniy","year":"2006","unstructured":"Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam D. Smith. 2006. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. CoRR, Vol. abs\/cs\/0602007 (2006)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/050631847"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"David Eppstein Michael T. Goodrich Frank C. Uyeda and George Varghese. 2011. What's the Difference? Efficient Set Reconciliation without Prior Context. In ACM SIGCOMM.","DOI":"10.1145\/2018436.2018462"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.883542"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436906"},{"volume-title":"Allerton Conference on Communication, Control, and Computing.","author":"Michael","key":"e_1_2_1_14_1","unstructured":"Michael T. Goodrich and Michael Mitzenmacher. 2011. Invertible Bloom lookup tables. In Allerton Conference on Communication, Control, and Computing."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.144.0390"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2021.3050428"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"A. Donald Keedwell and J\u00f3zsef D\u00e9nes. 2015. Chapter 5 - The concept of orthogonality. In Latin Squares and their Applications (Second Edition).","DOI":"10.1016\/B978-0-444-63555-6.50005-2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2021.3059075"},{"key":"e_1_2_1_19_1","volume-title":"Failure Probability Analysis for Partial Extraction from Invertible Bloom Filters. CoRR","author":"Kubjas Ivo","year":"2020","unstructured":"Ivo Kubjas and Vitaly Skachek. 2020. Failure Probability Analysis for Partial Extraction from Invertible Bloom Filters. CoRR, Vol. abs\/2008.00879 (2020)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2023.3296630"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2024.3432334"},{"key":"e_1_2_1_22_1","volume-title":"Towards Network-level Efficiency for Cloud Storage Services. In Internet Measurement Conference (IMC).","author":"Li Zhenhua","year":"2014","unstructured":"Zhenhua Li, Cheng Jin, Tianyin Xu, Christo Wilson, Yao Liu, Linsong Cheng, Yunhao Liu, Yafei Dai, and Zhi-Li Zhang. 2014. Towards Network-level Efficiency for Cloud Storage Services. In Internet Measurement Conference (IMC)."},{"key":"e_1_2_1_23_1","volume-title":"Set Reconciliation with Cuckoo Filters. In ACM International Conference on Information and Knowledge Management (CIKM).","author":"Luo Lailong","year":"2019","unstructured":"Lailong Luo, Deke Guo, Ori Rottenstreich, Richard T.B Ma, and Xueshan Luo. 2019. Set Reconciliation with Cuckoo Filters. In ACM International Conference on Information and Knowledge Management (CIKM)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3074440"},{"key":"e_1_2_1_25_1","volume-title":"Range-Based Set Reconciliation. In International Symposium on Reliable Distributed Systems (SRDS).","author":"Meyer Aljoscha","year":"2023","unstructured":"Aljoscha Meyer. 2023. Range-Based Set Reconciliation. In International Symposium on Reliable Distributed Systems (SRDS)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.815784"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0316-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Avi Mizrahi Daniella Bar-Lev Eitan Yaakobi and Ori Rottenstreich. 2024. Invertible Bloom Lookup Tables with Listing Guarantees. In ACM Sigmetrics.","DOI":"10.1145\/3652963.3655060"},{"key":"e_1_2_1_29_1","volume-title":"Peer-to-Peer Based Version Control. In IEEE International Conference on Parallel and Distributed Systems (ICPADS).","author":"Mukherjee Patrick","year":"2008","unstructured":"Patrick Mukherjee, Christof Leng, Wesley W. Terpstra, and Andy Sch\u00fcrr. 2008. Peer-to-Peer Based Version Control. In IEEE International Conference on Parallel and Distributed Systems (ICPADS)."},{"key":"e_1_2_1_30_1","volume-title":"Graphene: Efficient interactive set reconciliation applied to blockchain propagation. In ACM SIGCOMM.","author":"Ozisik A. Pinar","year":"2019","unstructured":"A. Pinar Ozisik, Gavin Andresen, Brian N. Levine, Darren Tapp, George Bissias, and Sunny Katkuri. 2019. Graphene: Efficient interactive set reconciliation applied to blockchain propagation. In ACM SIGCOMM."},{"volume-title":"Version Reconciliation for Collaborative Databases. In ACM Symposium on Cloud Computing (SoCC).","author":"Ranjan Nalin","key":"e_1_2_1_31_1","unstructured":"Nalin Ranjan, Zechao Shang, Sanjay Krishnan, and Aaron J. Elmore. 2021. Version Reconciliation for Collaborative Databases. In ACM Symposium on Cloud Computing (SoCC)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2013.2275036"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2021.3068604"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2013.03.007"},{"key":"e_1_2_1_35_1","volume-title":"On the Stopping Distance and the Stopping Redundancy of Codes. CoRR","author":"Schwartz Moshe","year":"2005","unstructured":"Moshe Schwartz and Alexander Vardy. 2005. On the Stopping Distance and the Stopping Redundancy of Codes. CoRR, Vol. abs\/cs\/0503058 (2005)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/DBKDA.2010.21"},{"volume-title":"Fast PDA Synchronization Using Characteristic Polynomial Interpolation","author":"Trachtenberg Ari","key":"e_1_2_1_37_1","unstructured":"Ari Trachtenberg, David Starobinski, and Sachin Agarwal. 2002. Fast PDA Synchronization Using Characteristic Polynomial Interpolation. In IEEE INFOCOM."},{"key":"e_1_2_1_38_1","volume-title":"Financial Big Data Reconciliation Method. In International Symposium on Advances in Informatics, Electronics and Education (ISAIEE).","author":"Xing Xiaobo","year":"2021","unstructured":"Xiaobo Xing. 2021. Financial Big Data Reconciliation Method. In International Symposium on Advances in Informatics, Electronics and Education (ISAIEE)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Lei Yang Yossi Gilad and Mohammad Alizadeh. 2024. Practical Rateless Set Reconciliation. In ACM SIGCOMM.","DOI":"10.1145\/3651890.3672219"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727110","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:32:29Z","timestamp":1755898349000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,27]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,27]]}},"alternative-id":["10.1145\/3727110"],"URL":"https:\/\/doi.org\/10.1145\/3727110","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2025,5,27]]},"assertion":[{"value":"2025-06-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}