{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:46Z","timestamp":1777954606627,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743317","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"367-381","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Dispersion is (Almost) Optimal under (A)synchrony"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2451-7306","authenticated-orcid":false,"given":"Ajay D.","family":"Kshemkalyani","sequence":"first","affiliation":[{"name":"University of Illinois Chicago, Chicago, IL, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0414-7910","authenticated-orcid":false,"given":"Manish","family":"Kumar","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1537-3462","authenticated-orcid":false,"given":"Anisur Rahaman","family":"Molla","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2862-2795","authenticated-orcid":false,"given":"Debasish","family":"Pattanayak","sequence":"additional","affiliation":[{"name":"University of Ottawa, Ottawa, Ontario, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4930-4609","authenticated-orcid":false,"given":"Gokarna","family":"Sharma","sequence":"additional","affiliation":[{"name":"Kent State University, Kent, OH, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1","article-title":"Dispersion of Mobile Robots","volume":"1","author":"Augustine John","year":"2018","unstructured":"John Augustine and William K. Moses Jr. 2018. Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs. In ICDCN. 1:1--1:10.","journal-title":"A Study of Memory-Time Trade-offs. In ICDCN."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Evangelos Bampas Leszek Gasieniec Nicolas Hanusse David Ilcinkas Ralf Klasing and Adrian Kosowski. 2009. Euler Tour Lock-in Problem in the Rotor-router Model: I Choose Pointers and You Choose Port Numbers. In DISC (Elche Spain). 423--435.","DOI":"10.1007\/978-3-642-04355-0_44"},{"key":"e_1_3_2_1_3_1","volume-title":"Optimizing Robot Dispersion on Unoriented Grids: With and Without Fault Tolerance","author":"Banerjee Rik","unstructured":"Rik Banerjee, Manish Kumar, and Anisur Rahaman Molla. 2024. Optimizing Robot Dispersion on Unoriented Grids: With and Without Fault Tolerance. In ALGOWIN, Quentin Bramas, Arnaud Casteigts, and Kitty Meeks (Eds.). Springer, 31--45."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3700838.3700842"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"L. Barriere P. Flocchini E. Mesa-Barrameda and N. Santoro. 2009. Uniform scattering of autonomous mobile robots in a grid. In IPDPS. 1--8.","DOI":"10.1109\/IPDPS.2009.5160871"},{"key":"e_1_3_2_1_6_1","volume-title":"Anisur Rahaman Molla, and Sumathi Sivasubramaniam","author":"Chand Prabhat Kumar","year":"2023","unstructured":"Prabhat Kumar Chand, Manish Kumar, Anisur Rahaman Molla, and Sumathi Sivasubramaniam. 2023. Fault-Tolerant Dispersion of Mobile Robots. In CALDAM, Amitabha Bagchi and Rahul Muthu (Eds.). 28--40."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383373"},{"key":"e_1_3_2_1_8_1","volume-title":"Christoph Raupach, Kamil Swierkot, Daniel Warner, Christoph Weddemann, and Daniel Wonisch.","author":"Cord-Landwehr Andreas","year":"2011","unstructured":"Andreas Cord-Landwehr, Bastian Degener, Matthias Fischer, Martina H\u00fcllmann, Barbara Kempkes, Alexander Klaas, Peter Kling, Sven Kurras, Marcus M\u00e4rtens, Friedhelm Meyer auf der Heide, Christoph Raupach, Kamil Swierkot, Daniel Warner, Christoph Weddemann, and Daniel Wonisch. 2011. A New Approach for Analyzing Convergence Algorithms for Mobile Robots. In ICALP. 650--661."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(89)90021-X"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-67899-9_34"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.018"},{"key":"e_1_3_2_1_12_1","volume-title":"C (Aug.","author":"Dereniowski Dariusz","year":"2015","unstructured":"Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pajak, and Przemyslaw Uzna\u0144ski. 2015. Fast Collaborative Graph Exploration. Inf. Comput. 243, C (Aug. 2015), 37--49."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.023"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.014"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2024.104852"},{"key":"e_1_3_2_1_16_1","first-page":"1","article-title":"Dispersion of Mobile Robots on Directed Anonymous Graphs","volume":"11","author":"Italiano Giuseppe F.","year":"2022","unstructured":"Giuseppe F. Italiano, Debasish Pattanayak, and Gokarna Sharma. 2022. Dispersion of Mobile Robots on Directed Anonymous Graphs. In SIROCCO. 11:1--11:21.","journal-title":"SIROCCO."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Tanvir Kaur and Kaushik Mondal. 2023. Distance-2-Dispersion: Dispersion with Further Constraints. In NETYS David Mohaisen and Thomas Wies (Eds.). 157--173.","DOI":"10.1007\/978-3-031-37765-5_12"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2025.115272"},{"key":"e_1_3_2_1_19_1","volume-title":"Kshemkalyani and Faizan Ali","author":"Ajay","year":"2019","unstructured":"Ajay D. Kshemkalyani and Faizan Ali. 2019. Efficient Dispersion of Mobile Robots on Graphs. In ICDCN. 218--227."},{"key":"e_1_3_2_1_20_1","volume-title":"Anisur Rahaman Molla, and Gokarna Sharma","author":"Kshemkalyani Ajay D.","year":"2024","unstructured":"Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma. 2024. Brief Announcement: Agent-Based Leader Election, MST, and Beyond. In DISC (LIPIcs, Vol. 319), Dan Alistarh (Ed.). 50:1--50:7."},{"key":"e_1_3_2_1_21_1","volume-title":"Anisur Rahaman Molla, and Gokarna Sharma","author":"Kshemkalyani Ajay D","year":"2024","unstructured":"Ajay D Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma. 2024. Faster Leader Election and Its Applications for Mobile Agents with Parameter Advice. In ICDCIT. Springer, 108--123."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2503.16216"},{"key":"e_1_3_2_1_23_1","volume-title":"Anisur Rahaman Molla, and Gokarna Sharma","author":"Kshemkalyani Ajay D.","year":"2025","unstructured":"Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma. 2025. Near-Linear Time Leader Election in Multiagent Networks. In AAMAS (Detroit, MI, USA). 1218--1226."},{"key":"e_1_3_2_1_24_1","volume-title":"Anisur Rahaman Molla, and Gokarna Sharma","author":"Kshemkalyani Ajay D.","year":"2019","unstructured":"Ajay D. Kshemkalyani, Anisur Rahaman Molla, and Gokarna Sharma. 2019. Fast Dispersion of Mobile Robots on Arbitrary Graphs. In ALGOSENSORS. 23--40."},{"key":"e_1_3_2_1_25_1","volume-title":"Anisur Rahaman Molla, and Gokarna Sharma","author":"Kshemkalyani Ajay D.","year":"2020","unstructured":"Ajay D. Kshemkalyani, Anisur Rahaman Molla, and Gokarna Sharma. 2020. Dispersion of Mobile Robots on Grids. In WALCOM. 183--197."},{"key":"e_1_3_2_1_26_1","volume-title":"Anisur Rahaman Molla, and Gokarna Sharma","author":"Kshemkalyani Ajay D.","year":"2020","unstructured":"Ajay D. Kshemkalyani, Anisur Rahaman Molla, and Gokarna Sharma. 2020. Efficient Dispersion of Mobile Robots on Dynamic Graphs. In ICDCS. 732--742."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2021.11.007"},{"key":"e_1_3_2_1_28_1","first-page":"1","article-title":"Near-Optimal Dispersion on Arbitrary Anonymous Graphs","volume":"8","author":"Kshemkalyani Ajay D.","year":"2021","unstructured":"Ajay D. Kshemkalyani and Gokarna Sharma. 2021. Near-Optimal Dispersion on Arbitrary Anonymous Graphs. In OPODIS. 8:1--8:19.","journal-title":"OPODIS."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.06.010"},{"key":"e_1_3_2_1_30_1","volume-title":"Moses Jr","author":"Molla Anisur Rahaman","year":"2019","unstructured":"Anisur Rahaman Molla and William K. Moses Jr. 2019. Dispersion of Mobile Robots: The Power of Randomness. In TAMC. 481--500."},{"key":"e_1_3_2_1_31_1","volume-title":"Moses Jr","author":"Molla Anisur Rahaman","year":"2021","unstructured":"Anisur Rahaman Molla, Kaushik Mondal, and William K. Moses Jr. 2021. Byzantine Dispersion on Graphs. In IPDPS. IEEE, 942--951."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.07.008"},{"key":"e_1_3_2_1_33_1","first-page":"1","article-title":"Dispersion of Mobile Robots Tolerating Faults","volume":"17","author":"Pattanayak Debasish","year":"2021","unstructured":"Debasish Pattanayak, Gokarna Sharma, and Partha Sarathi Mandal. 2021. Dispersion of Mobile Robots Tolerating Faults. In WDALFR. 17:1--17:6.","journal-title":"WDALFR."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Pavan Poudel and Gokarna Sharma. 2019. Time-Optimal Uniform Scattering in a Grid. In ICDCN. 228--237.","DOI":"10.1145\/3288599.3288622"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3700838.3700845"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3700838.3700864"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Masahiro Shibata Toshiya Mega Fukuhito Ooshita Hirotsugu Kakugawa and Toshimitsu Masuzawa. 2016. Uniform Deployment of Mobile Agents in Asynchronous Rings. In PODC (Chicago Illinois USA). 415--424.","DOI":"10.1145\/2933057.2933093"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Takahiro Shintaku Yuichi Sudo Hirotsugu Kakugawa and Toshimitsu Masuzawa. 2020. Efficient Dispersion of Mobile Agents without Global Knowledge. In SSS. 280--294.","DOI":"10.1007\/978-3-030-64348-5_22"},{"key":"e_1_3_2_1_39_1","volume-title":"Scherson","author":"Subramanian Raghu","year":"1994","unstructured":"Raghu Subramanian and Isaac D. Scherson. 1994. An Analysis of Diffusive Load-balancing. In SPAA (Cape May, New Jersey, USA). 220--225."},{"key":"e_1_3_2_1_40_1","first-page":"1","article-title":"Near-linear Time Dispersion of Mobile Agents","volume":"38","author":"Sudo Yuichi","year":"2024","unstructured":"Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. 2024. Near-linear Time Dispersion of Mobile Agents. In DISC. LIPIcs, 38:1--38:22.","journal-title":"DISC. LIPIcs"}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","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"]},"container-title":["Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:19:27Z","timestamp":1777922367000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743317"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":40,"alternative-id":["10.1145\/3694906.3743317","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743317","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}