{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T15:20:06Z","timestamp":1758122406080,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538593","type":"proceedings-article","created":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T22:13:02Z","timestamp":1659391982000},"page":"389-399","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Balanced Allocations in Batches"],"prefix":"10.1145","author":[{"given":"Dimitrios","family":"Los","sequence":"first","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}]},{"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2022,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/299633.299636"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210411"},{"key":"e_1_3_2_1_3_1","volume-title":"Brief Announcement: Fast Graphical Population Protocols. In 35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"4","author":"Alistarh Dan","year":"2021","unstructured":"Dan Alistarh , Rati Gelashvili , and Joel Rybicki . 2021 . Brief Announcement: Fast Graphical Population Protocols. In 35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 43:1-43: 4 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.43 Full version at https:\/\/arxiv.org\/abs\/2102.08808. 10.4230\/LIPIcs.DISC.2021.43 Dan Alistarh, Rati Gelashvili, and Joel Rybicki. 2021. Brief Announcement: Fast Graphical Population Protocols. In 35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 43:1-43:4. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.43 Full version at https:\/\/arxiv.org\/abs\/2102.08808."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_3_2_1_5_1","volume-title":"The Power of Two Choices in Graphical Allocation. https:\/\/doi.org\/10.48550\/ARXIV.2106.06051 (to appear in STOC","author":"Bansal Nikhil","year":"2022","unstructured":"Nikhil Bansal and Ohad Feldheim . 2021. The Power of Two Choices in Graphical Allocation. https:\/\/doi.org\/10.48550\/ARXIV.2106.06051 (to appear in STOC 2022 ). 10.48550\/ARXIV.2106.06051 Nikhil Bansal and Ohad Feldheim. 2021. The Power of Two Choices in Graphical Allocation. https:\/\/doi.org\/10.48550\/ARXIV.2106.06051 (to appear in STOC 2022)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.10.008"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_35"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444435X"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.023"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3288645.3288678"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1011"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.888643"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1986.6312961"},{"key":"#cr-split#-e_1_3_2_1_14_1.1","unstructured":"Ohad Noy Feldheim Ori Gurel-Gurevich and Jiange Li. 2021. Long-term balanced allocation via thinning. https:\/\/doi.org\/10.48550\/ARXIV.2110.05009 10.48550\/ARXIV.2110.05009"},{"key":"#cr-split#-e_1_3_2_1_14_1.2","unstructured":"Ohad Noy Feldheim Ori Gurel-Gurevich and Jiange Li. 2021. Long-term balanced allocation via thinning. https:\/\/doi.org\/10.48550\/ARXIV.2110.05009"},{"key":"e_1_3_2_1_15_1","volume-title":"Load balancing under d-thinning. Electronic Communications in Probability 25","author":"Feldheim Ohad Noy","year":"2020","unstructured":"Ohad Noy Feldheim and Jiange Li. 2020. Load balancing under d-thinning. Electronic Communications in Probability 25 ( 2020 ), Paper No . 1, 13. https:\/\/doi.org\/10.1214\/19-ecp282 10.1214\/19-ecp282 Ohad Noy Feldheim and Jiange Li. 2020. Load balancing under d-thinning. Electronic Communications in Probability 25 (2020), Paper No. 1, 13. https:\/\/doi.org\/10.1214\/19-ecp282"},{"key":"e_1_3_2_1_16_1","first-page":"511","volume-title":"Proceedings of 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08)","author":"Godfrey Philip Brighten","year":"2008","unstructured":"Philip Brighten Godfrey . 2008 . Balls and bins with structure: balanced allocations on hypergraphs . In Proceedings of 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08) . Society for Industrial and Applied Mathematics, USA , 511 - 517 . Philip Brighten Godfrey. 2008. Balls and bins with structure: balanced allocations on hypergraphs. In Proceedings of 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08). Society for Industrial and Applied Mathematics, USA, 511-517."},{"key":"e_1_3_2_1_17_1","volume-title":"Algorithms and Techniques (APPROX\/RANDOM 2020) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"22","author":"Greenhill Catherine","year":"2020","unstructured":"Catherine Greenhill , Bernard Mans , and Ali Pourmiri . 2020 . Balanced Allocation on Dynamic Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization . Algorithms and Techniques (APPROX\/RANDOM 2020) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 176), Jaros?aw Byrka and Raghu Meka (Eds.). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 11:1-11: 22 . https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.11 10.4230\/LIPIcs.APPROX Catherine Greenhill, Bernard Mans, and Ali Pourmiri. 2020. Balanced Allocation on Dynamic Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 176), Jaros?aw Byrka and Raghu Meka (Eds.). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 11:1-11:22. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.11"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_48"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940878"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109606"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323203"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993639"},{"key":"e_1_3_2_1_24_1","volume-title":"13th Innovations in Theoretical Computer Science Conference (ITCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs)","author":"Los Dimitrios","year":"2022","unstructured":"Dimitrios Los and Thomas Sauerwald . 2022. Balanced Allocations with Incomplete Information: The Power of Two Queries . In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 215), Mark Braverman (Ed.). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 103:1-103: 23 . https: \/\/doi.org\/10.4230\/LIPIcs.ITCS. 2022 .103 10.4230\/LIPIcs.ITCS.2022.103 Dimitrios Los and Thomas Sauerwald. 2022. Balanced Allocations with Incomplete Information: The Power of Two Queries. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 215), Mark Braverman (Ed.). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 103:1-103:23. https: \/\/doi.org\/10.4230\/LIPIcs.ITCS.2022.103"},{"key":"e_1_3_2_1_25_1","volume-title":"Balanced Allocations with the Choice of Noise. (to appear in PODC","author":"Los Dimitrios","year":"2022","unstructured":"Dimitrios Los and Thomas Sauerwald . 2022. Balanced Allocations with the Choice of Noise. (to appear in PODC 2022 ). Dimitrios Los and Thomas Sauerwald. 2022. Balanced Allocations with the Choice of Noise. (to appear in PODC 2022)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.74"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.824633"},{"key":"e_1_3_2_1_28_1","first-page":"255","volume-title":"II. Comb. Optim.","volume":"9","author":"Mitzenmacher Michael","year":"2001","unstructured":"Michael Mitzenmacher , Andr\u00e9a W. Richa , and Ramesh Sitaraman . 2001 . The power of two random choices: a survey of techniques and results. In Handbook of randomized computing, Vol. I , II. Comb. Optim. , Vol. 9 . Kluwer Acad. Publ., Dordrecht, Netherlands , 255 - 312 . https:\/\/doi.org\/10.1007\/978-1-4615-0013-1_9 10.1007\/978-1-4615-0013-1_9 Michael Mitzenmacher, Andr\u00e9a W. Richa, and Ramesh Sitaraman. 2001. The power of two random choices: a survey of techniques and results. In Handbook of randomized computing, Vol. I, II. Comb. Optim., Vol. 9. Kluwer Acad. Publ., Dordrecht, Netherlands, 255-312. https:\/\/doi.org\/10.1007\/978-1-4615-0013-1_9"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20558"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250829"},{"key":"e_1_3_2_1_32_1","series-title":"Lecture Notes in Comput. Sci.","volume-title":"Automata, languages, and programming. Part I","author":"Talwar Kunal","unstructured":"Kunal Talwar and Udi Wieder . 2014. Balanced allocations: a simple proof for the heavily loaded case . In Automata, languages, and programming. Part I . Lecture Notes in Comput. Sci. , Vol. 8572 . Springer, Heidelberg , Berlin, Heidelberg , 979-990. https:\/\/doi.org\/10.1007\/978-3-662-43948-7_81 10.1007\/978-3-662-43948-7_81 Kunal Talwar and Udi Wieder. 2014. Balanced allocations: a simple proof for the heavily loaded case. In Automata, languages, and programming. Part I. Lecture Notes in Comput. Sci., Vol. 8572. Springer, Heidelberg, Berlin, Heidelberg, 979-990. https:\/\/doi.org\/10.1007\/978-3-662-43948-7_81"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248407"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000070"}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Philadelphia PA USA","acronym":"SPAA '22"},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538593","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538593"}},"subtitle":["Simplified and Generalized"],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":34,"alternative-id":["10.1145\/3490148.3538593","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538593","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}