2026-09-13T04:32:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24879 2026-09-05T19:00:17Z ddc:004 open_access

Brief Announcement: Optimal Dispersion Under Asynchrony Pattanayak, Debasish Kshemkalyani, Ajay D. Kumar, Manish Molla, Anisur Rahaman Sharma, Gokarna Distributed algorithms mobile agents local communication dispersion asynchrony port-one tree time and memory complexity We study the dispersion problem in anonymous port-labeled graphs: k ≤ n mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an n-node graph with maximum degree Δ, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in the distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires Ω(k) time in the worst case, and Ω(log k) bits of memory per agent. A recent result [Kshemkalyani et al., 2025] gives an optimal O(k)-time algorithm in the synchronous setting and an O(k log k)-time algorithm in the asynchronous setting, both using O(log(k+Δ)) bits. We close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal O(k) time using O(log(k+Δ)) bits of memory per agent. Our solution relies on a novel technique for constructing a port-one tree in anonymous graphs, which may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Debasish Pattanayak and Ajay D. Kshemkalyani and Manish Kumar and Anisur Rahaman Molla and Gokarna Sharma 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.63 urn:nbn:de:0030-drops-248795 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.63 eng https://creativecommons.org/licenses/by/4.0/legalcode