{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:05:48Z","timestamp":1766066748331,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,10,23]],"date-time":"2017-10-23T00:00:00Z","timestamp":1508716800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,10,23]],"date-time":"2017-10-23T00:00:00Z","timestamp":1508716800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-1320231","CNS-1228598"],"award-info":[{"award-number":["CCF-1320231","CNS-1228598"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["IIS-0964473","CCF-0915922"],"award-info":[{"award-number":["IIS-0964473","CCF-0915922"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001732","name":"Danmarks Grundforskningsfond","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00446-017-0316-0","type":"journal-article","created":{"date-parts":[[2017,10,24]],"date-time":"2017-10-24T00:51:54Z","timestamp":1508806314000},"page":"441-453","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Simple multi-party set reconciliation"],"prefix":"10.1007","volume":"31","author":[{"given":"Michael","family":"Mitzenmacher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,23]]},"reference":[{"key":"316_CR1","unstructured":"Andresen, G.: $$O(1)$$ Block Propagation. https:\/\/gist.github.com\/gavinandresen\/e20c3b5a1d4b97f79ac2"},{"key":"316_CR2","unstructured":"Appleby, A.: MurmurHash2 Implementation. https:\/\/github.com\/aappleby\/smhasher\/wiki\/MurmurHash2"},{"issue":"7","key":"316_CR3","doi-asserted-by":"crossref","first-page":"20:20","DOI":"10.1145\/2639988.2655736","volume":"12","author":"P Bailis","year":"2014","unstructured":"Bailis, P., Kingsbury, K.: The network is reliable: an informal survey of real-world communications failures. Queue 12(7), 20:20\u201320:32 (2014)","journal-title":"Queue"},{"key":"316_CR4","doi-asserted-by":"crossref","unstructured":"Boral, A., Mitzenmacher, M.: Multi-party set reconciliation using characteristic polynomials. In: Proceedings of the 52nd Allerton Conference, pp. 1182\u20131187 (2014)","DOI":"10.1109\/ALLERTON.2014.7028589"},{"issue":"8","key":"316_CR5","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.ipl.2011.10.017","volume":"112","author":"F Botelho","year":"2012","unstructured":"Botelho, F., Wormald, N., Ziviani, N.: Cores of random $$r$$-partite hypergraphs. Inf. Process. Lett. 112(8), 314\u2013319 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"316_CR6","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1006\/jcss.1999.1690","volume":"60","author":"A Broder","year":"2000","unstructured":"Broder, A., Charikar, M., Frieze, A., Mitzenmacher, M.: Min-wise independent permutations. J. Comput. Syst. Sci. 60(3), 630\u2013659 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"316_CR7","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1109\/TNET.2004.836103","volume":"12","author":"J Byers","year":"2004","unstructured":"Byers, J., Considine, J., Mitzenmacher, M., Rost, S.: Informed content delivery across adaptive overlay networks. IEEE\/ACM Trans. Netw. 12(5), 767\u2013780 (2004)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"316_CR8","doi-asserted-by":"crossref","unstructured":"Calder, B., Wang, J., Ogus, A., Nilakantan, N., Skjolsvold, A., McKelvie, S., Xu, Y., Srivastav, S., Wu, J., Simitci, H., et al.: Windows Azure Storage: a highly available cloud storage service with strong consistency. In: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pp. 143\u2013157 (2011)","DOI":"10.1145\/2043556.2043571"},{"key":"316_CR9","doi-asserted-by":"crossref","unstructured":"Chen, D., Konrad, C., Yi, Ke, Yu, W., Zhang, Q.: Robust set reconciliation. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 135\u2013146 (2014)","DOI":"10.1145\/2588555.2610528"},{"key":"316_CR10","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Almost tight bounds for rumour spreading with conductance. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 399\u2013408 (2010)","DOI":"10.1137\/1.9781611973075.135"},{"issue":"3","key":"316_CR11","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E Cohen","year":"1997","unstructured":"Cohen, E.: Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci. 55(3), 441\u2013453 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"316_CR12","doi-asserted-by":"publisher","first-page":"2486","DOI":"10.1109\/TIT.2006.874532","volume":"52","author":"S Deb","year":"2006","unstructured":"Deb, S., M\u00e9dard, M., Choute, C.: Algebraic gossip: a network coding approach to optimal multiple rumor mongering. IEEE Trans. Inf. Theory 52(6), 2486\u20132507 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"316_CR13","doi-asserted-by":"crossref","unstructured":"DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W.: Dynamo: Amazon\u2019s highly available key-value store. In: Proceedings of Twenty-First ACM SIGOPS Symposium on Operating Systems Principles, pp. 205\u2013220 (2007)","DOI":"10.1145\/1323293.1294281"},{"key":"316_CR14","doi-asserted-by":"crossref","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pp. 1\u201312 (1987)","DOI":"10.1145\/41840.41841"},{"issue":"1","key":"316_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/060651380","volume":"38","author":"Y Dodis","year":"2008","unstructured":"Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97\u2013139 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"316_CR16","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1109\/TKDE.2010.132","volume":"23","author":"D Eppstein","year":"2011","unstructured":"Eppstein, D., Goodrich, M.: Straggler identification in round-trip data streams via Newton\u2019s identities and invertible bloom filters. IEEE Trans. Knowl. Data Eng. 23(2), 297\u2013306 (2011)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"316_CR17","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Goodrich, M., Uyeda, F., Varghese, G.: What\u2019s the difference? Efficient set reconciliation without prior context. In: Proceedings of the ACM SIGCOMM Conference, pp. 218\u2013229 (2011)","DOI":"10.1145\/2043164.2018462"},{"key":"316_CR18","unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, pp. 57\u201368 (2011)"},{"key":"316_CR19","doi-asserted-by":"crossref","unstructured":"Gabrys, R., Farnoud, F.: Reconciling similar sets of data. In: Proceedings of the International Symposium on Information Theory, pp. 2837\u20132341 (2014)","DOI":"10.1109\/ISIT.2015.7282974"},{"key":"316_CR20","doi-asserted-by":"crossref","unstructured":"Goodrich, M., Mitzenmacher, M.: Invertible bloom lookup tables. In: Proceedings of the 49th Annual Allerton Conference, pp. 792\u2013799 (2011)","DOI":"10.1109\/Allerton.2011.6120248"},{"key":"316_CR21","unstructured":"Gorale, A.: Bitcoin in Bloom: How IBLTs Allow Bitcoin to Scale. Cryptocoin News, October 2, 2014. https:\/\/www.cryptocoinsnews.com\/bitcoin-in-bloom-how-iblts-allow-bitcoin-scale"},{"key":"316_CR22","unstructured":"Goyal, N., Varghese, G.: Personal communication (2013)"},{"key":"316_CR23","doi-asserted-by":"crossref","unstructured":"Haeupler, B.: Analyzing network coding gossip made easy. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 293\u2013302 (2011)","DOI":"10.1145\/1993636.1993676"},{"issue":"4","key":"316_CR24","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"S Hedetniemi","year":"1988","unstructured":"Hedetniemi, S., Hedetniemi, S., Liestman, A.: A survey of gossiping and broadcasting in communication networks. Networks 18(4), 319\u2013349 (1988)","journal-title":"Networks"},{"key":"316_CR25","doi-asserted-by":"crossref","unstructured":"Huang, Z., Yi, Ke, Zhang, Q.: Randomized algorithms for tracking distributed count, frequencies, and ranks. In: Proceedings of the 31st Symposium on Principles of Database Systems, pp. 295\u2013306 (2012)","DOI":"10.1145\/2213556.2213596"},{"issue":"2","key":"316_CR26","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10623-005-6343-z","volume":"38","author":"A Juels","year":"2006","unstructured":"Juels, A., Sudan, M.: A fuzzy vault scheme. Des. Codes Crypt. 38(2), 237\u2013257 (2006)","journal-title":"Des. Codes Crypt."},{"issue":"4","key":"316_CR27","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/1151659.1159942","volume":"36","author":"S Katti","year":"2006","unstructured":"Katti, S., Rahul, H., Hu, W., Katabi, D., M\u00e9dard, M., Crowcroft, J.: XORs in the air: practical wireless network coding. ACM SIGCOMM Comput. Commun. Rev. 36(4), 243\u2013254 (2006)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"issue":"1","key":"316_CR28","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0012-365X(75)90090-4","volume":"13","author":"W Kn\u00f6del","year":"1975","unstructured":"Kn\u00f6del, W.: New gossips and telephones. Discrete Math. 13(1), 95 (1975)","journal-title":"Discrete Math."},{"key":"316_CR29","doi-asserted-by":"crossref","unstructured":"Kosti\u0107, D., Snoeren, A., Vadhat, A., Braud, R., Killian, C., Anderson, J., Albrecht, J., Rodriguesz, A., Vandkieft, E.: High-bandwidth data dissemination for large-scale distributed systems. ACM Trans. Comput. Syst. 26(1), Article 3 (2008)","DOI":"10.1145\/1328671.1328674"},{"issue":"2","key":"316_CR30","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1109\/18.910575","volume":"47","author":"M Luby","year":"2001","unstructured":"Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D.: Efficient erasure correcting codes. IEEE Trans. Inf. Theory 47(2), 569\u2013584 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"9","key":"316_CR31","doi-asserted-by":"publisher","first-page":"2213","DOI":"10.1109\/TIT.2003.815784","volume":"49","author":"Y Minsky","year":"2003","unstructured":"Minsky, Y., Trachtenberg, A., Zippel, R.: Set reconciliation with nearly optimal communication complexity. IEEE Trans. Inf. Theory 49(9), 2213\u20132218 (2003)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"316_CR32","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Varghese, G.: The complexity of object reconciliation, and open problems related to set difference and coding. In: Proceedings of the 50th Annual Allerton Conference, pp. 1126\u20131132 (2012)","DOI":"10.1109\/Allerton.2012.6483345"},{"key":"316_CR33","unstructured":"Molloy, M.: The pure literal rule threshold and cores in random hypergraphs. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 672\u2013681 (2004)"},{"key":"316_CR34","doi-asserted-by":"crossref","unstructured":"Rink, M.: Mixed hypergraphs for linear-time construction of denser hashing-based data structures. In: SOFSEM 2013: Theory and Practice of Computer Science, pp. 356\u2013368 (2013)","DOI":"10.1007\/978-3-642-35843-2_31"},{"issue":"4","key":"316_CR35","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"316_CR36","doi-asserted-by":"crossref","unstructured":"Skachek, V., Rabbat, M.: Subspace synchronization: a network-coding approach to object reconciliation. In: Proceedings of the International Symposium on Information Theory, pp. 2301\u20132305 (2014)","DOI":"10.1109\/ISIT.2014.6875244"},{"key":"316_CR37","doi-asserted-by":"crossref","unstructured":"Skjegstad, M., Maseng, T.: Low complexity set reconciliation using Bloom filters. In: Proceedings of the 7th ACM ACM SIGACT\/SIGMOBILE International Workshop on Foundations of Mobile Computing, pp. 33\u201341 (2011)","DOI":"10.1145\/1998476.1998483"},{"issue":"1","key":"316_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/1300000014","volume":"3","author":"D Shah","year":"2008","unstructured":"Shah, D.: Gossip algorithms. Found. Trends Netw. 3(1), 1\u2013125 (2008)","journal-title":"Found. Trends Netw."},{"key":"316_CR39","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Proceedings on the International Symposium on Symbolic and Algebraic Computation, pp. 216\u2013226 (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0316-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0316-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0316-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,20]],"date-time":"2020-10-20T09:54:18Z","timestamp":1603187658000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0316-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,23]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["316"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0316-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,10,23]]},"assertion":[{"value":"12 August 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}