标题： 异步下的最优分散 显示英文标题

标题： Optimal Dispersion Under Asynchrony

摘要： 我们研究匿名端口标记图中的分散问题：$k \leq n$个移动代理，每个代理都有一个唯一的 ID，并且最初任意位于一个$n$节点的图上，最大度数为$\Delta$，必须自主重新定位，使得没有节点容纳超过一个代理。 分散是移动代理分布式计算中的基本任务，其复杂性源于在匿名性和有限内存下的局部协调的关键挑战。 目标是同时最小化实现分散所需的时间和每个代理所需的内存。 已知任何算法在最坏情况下需要$\Omega(k)$时间，并且每个代理需要$\Omega(\log k)$位内存。 最近的结果 [SPAA'25] 在同步设置中给出了一个最优的$O(k)$-时间算法，在异步设置中给出了一个$O(k \log k)$-时间算法，两者都使用 $O(\log(k+\Delta))$位。 在本文中，我们通过提出第一个在异步设置中以最优$O(k)$时间运行并使用$O(\log(k+\Delta))$位内存的分散算法来填补复杂性差距。 我们的解决方案基于我们在本文中开发的一种新技术，该技术在匿名图中构建了一个端口一棵树，这可能具有独立的兴趣。 显示英文摘要

摘要： We study the dispersion problem in anonymous port-labeled graphs: $k \leq n$ mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an $n$-node graph with maximum degree $\Delta$, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in 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 $\Omega(k)$ time in the worst case, and $\Omega(\log k)$ bits of memory per agent. A recent result [SPAA'25] 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+\Delta))$ bits. In this paper, 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+\Delta))$ bits of memory per agent. Our solution is based on a novel technique we develop in this paper that constructs a port-one tree in anonymous graphs, which may be of independent interest.