[{"ec_funded":1,"isi":1,"intvolume":"     12810","author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"},{"last_name":"Davies","full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","first_name":"Peter","orcid":"0000-0002-5646-9524"}],"scopus_import":"1","file_date_updated":"2021-07-01T11:21:40Z","publication":"Structural Information and Communication Complexity","oa":1,"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783030795276"],"isbn":["9783030795269"]},"file":[{"date_updated":"2021-07-01T11:21:40Z","checksum":"fe37fb9af3f5016c1084af9d6e7109bd","content_type":"application/pdf","file_size":319728,"creator":"pdavies","file_name":"Population_Coupon_Collector.pdf","date_created":"2021-07-01T11:21:40Z","file_id":"9621","access_level":"open_access","relation":"main_file"}],"acknowledgement":"Peter Davies is supported by the European Union’s Horizon2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411.","publication_status":"published","language":[{"iso":"eng"}],"external_id":{"isi":["001292788400001"]},"department":[{"_id":"DaAl"}],"date_created":"2021-07-01T11:04:43Z","quality_controlled":"1","volume":12810,"abstract":[{"lang":"eng","text":"In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).\r\n\r\nWe provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons."}],"oa_version":"Preprint","year":"2021","date_updated":"2025-09-10T10:04:46Z","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"has_accepted_license":"1","date_published":"2021-06-20T00:00:00Z","page":"3-12","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","status":"public","type":"conference","day":"20","publisher":"Springer Nature","ddc":["000"],"doi":"10.1007/978-3-030-79527-6_1","alternative_title":["LNCS"],"title":"Collecting coupons is faster with friends","month":"06","_id":"9620","citation":{"ieee":"D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,” in <i>Structural Information and Communication Complexity</i>, Wrocław, Poland, 2021, vol. 12810, pp. 3–12.","short":"D.-A. Alistarh, P. Davies, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 3–12.","mla":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” <i>Structural Information and Communication Complexity</i>, vol. 12810, Springer Nature, 2021, pp. 3–12, doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">10.1007/978-3-030-79527-6_1</a>.","chicago":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” In <i>Structural Information and Communication Complexity</i>, 12810:3–12. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">https://doi.org/10.1007/978-3-030-79527-6_1</a>.","ista":"Alistarh D-A, Davies P. 2021. Collecting coupons is faster with friends. Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 12810, 3–12.","ama":"Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: <i>Structural Information and Communication Complexity</i>. Vol 12810. Springer Nature; 2021:3-12. doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">10.1007/978-3-030-79527-6_1</a>","apa":"Alistarh, D.-A., &#38; Davies, P. (2021). Collecting coupons is faster with friends. In <i>Structural Information and Communication Complexity</i> (Vol. 12810, pp. 3–12). Wrocław, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">https://doi.org/10.1007/978-3-030-79527-6_1</a>"},"article_processing_charge":"No","conference":{"name":"SIROCCO: International Colloquium on Structural Information and Communication Complexity","start_date":"2021-06-28","location":"Wrocław, Poland","end_date":"2021-07-01"}},{"arxiv":1,"doi":"10.1007/978-3-030-79527-6_6","alternative_title":["LNCS"],"_id":"9823","title":"Wait-free approximate agreement on graphs","month":"06","article_processing_charge":"No","conference":{"location":"Wrocław, Poland","end_date":"2021-07-01","name":"SIROCCO: Structural Information and Communication Complexity","start_date":"2021-06-28"},"citation":{"ieee":"D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” in <i>Structural Information and Communication Complexity</i>, Wrocław, Poland, 2021, vol. 12810, pp. 87–105.","mla":"Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” <i>Structural Information and Communication Complexity</i>, vol. 12810, Springer Nature, 2021, pp. 87–105, doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_6\">10.1007/978-3-030-79527-6_6</a>.","short":"D.-A. Alistarh, F. Ellen, J. Rybicki, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 87–105.","ista":"Alistarh D-A, Ellen F, Rybicki J. 2021. Wait-free approximate agreement on graphs. Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 12810, 87–105.","chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate Agreement on Graphs.” In <i>Structural Information and Communication Complexity</i>, 12810:87–105. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_6\">https://doi.org/10.1007/978-3-030-79527-6_6</a>.","apa":"Alistarh, D.-A., Ellen, F., &#38; Rybicki, J. (2021). Wait-free approximate agreement on graphs. In <i>Structural Information and Communication Complexity</i> (Vol. 12810, pp. 87–105). Wrocław, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_6\">https://doi.org/10.1007/978-3-030-79527-6_6</a>","ama":"Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs. In: <i>Structural Information and Communication Complexity</i>. Vol 12810. Springer Nature; 2021:87-105. doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_6\">10.1007/978-3-030-79527-6_6</a>"},"date_published":"2021-06-20T00:00:00Z","year":"2021","oa_version":"Preprint","date_updated":"2026-04-16T09:26:11Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","page":"87-105","status":"public","publisher":"Springer Nature","day":"20","type":"conference","publication_status":"published","department":[{"_id":"DaAl"}],"external_id":{"isi":["001292788400006"],"arxiv":["2103.08949"]},"date_created":"2021-08-08T22:01:29Z","language":[{"iso":"eng"}],"volume":12810,"quality_controlled":"1","abstract":[{"text":"Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a vertex of the graph as input and, if non-faulty, must output a vertex such that\r\nall the outputs are within distance 1 of one another, and\r\n\r\neach output value lies on a shortest path between two input values.\r\n\r\nFrom prior work, it is known that there is no wait-free algorithm among   𝑛≥3  processes for this problem on any cycle of length   𝑐≥4 , by reduction from 2-set agreement (Castañeda et al. 2018).\r\n\r\nIn this work, we investigate the solvability and complexity of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length   𝑐≥4 , via a generalisation of Sperner’s Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on these graphs is unsolvable. On the positive side, we present a wait-free algorithm for a class of graphs that properly contains the class of chordal graphs.","lang":"eng"}],"author":[{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"},{"last_name":"Ellen","full_name":"Ellen, Faith","first_name":"Faith"},{"orcid":"0000-0002-6432-6646","last_name":"Rybicki","full_name":"Rybicki, Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel"}],"scopus_import":"1","publication":"Structural Information and Communication Complexity","isi":1,"intvolume":"     12810","publication_identifier":{"isbn":["9783030795269"],"issn":["0302-9743"],"eissn":["1611-3349"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2103.08949"}]}]