Asynchronous Dispersion with Optimal Time Complexity

Abstract

We study the dispersion problem for k mobile agents on an n-node anonymous graph with memory-less nodes and maximum degree Δ. Agents must autonomously relocate so that no two agents occupy the same node. While an optimal O(k)-time, O(log (k + Δ))-memory algorithm is known under synchronous settings, the best known asynchronous algorithm requires O(klog min {k, Δ}) time due to the difficulty of distinguishing unvisited nodes from nodes temporarily vacated by agents in the asynchronous environment. We close this gap by presenting the first fully asynchronous algorithm achieving asymptotically optimal O(k) time and O(log (k + Δ)) memory. Our main technical contribution is the introduction of the Port-1 Tree (P1Tree), a novel structural property of a port-labeled graph. By forcing the DFS traversal to prioritize edges locally labeled with port 1, P1Tree allows agents to verify the status of neighboring nodes in O(1) asynchronous epochs without relying on timing assumptions unavailable in the asynchronous model. We prove the O(k) bound first for rooted initial configurations and then extend it to general initial configurations via asynchronous tree mergers, preserving the same asymptotic time and memory bounds.