提出首个异步环境下最优时间的分散算法,仅用极小内存。
Optimal Dispersion Under Asynchrony
- 通过构建端口一棵树实现匿名图上的分布式协调
- 在异步场景下实现O(k)时间复杂度,达到理论下界
- 适合研究移动代理协同与低内存算法的读者
我们研究匿名端口标记图中的分散问题:k ≤ n个具有唯一ID的移动代理,初始时任意分布在n个节点的图中,最大度为Δ,需自主迁移使得每个节点至多容纳一个代理。分散是移动代理分布式计算的基础任务,其复杂性源于匿名性和有限内存下的局部协调挑战。目标是同时最小化达成分散所需的时间和每代理的内存开销。已知任何算法在最坏情况下均需Ω(k)时间,且每代理至少需要Ω(log k)位内存。近期工作(SPAA'25)给出了同步环境下O(k)时间的最优算法,以及异步环境下O(k log k)时间的算法,均使用O(log(k+Δ))位内存。本文首次在异步设置下构造出运行时间为最优O(k),且每代理仅使用O(log(k+Δ))位内存的分散算法。该方案基于本文提出的全新技术——在匿名图中构建端口一棵树,该技术本身可能具有独立研究价值。
原文摘要 · Abstract (English)
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 $Δ$, 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 $Ω(k)$ time in the worst case, and $Ω(\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+Δ))$ 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+Δ))$ 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。