论文标题
记忆最佳分散匿名移动机器人
Memory Optimal Dispersion by Anonymous Mobile Robots
论文作者
论文摘要
考虑一个由$ k \ leq n $自动移动机器人组成的团队，最初放置在带有$ n $节点的任意图$ g $的节点上。分散问题要求提供分布式算法，该算法允许机器人达到每个机器人在图形上不同节点的配置。如果机器人是匿名的，即它们没有任何唯一的标识符，那么任何确定性算法都无法解决问题。但是，如果每个机器人都可以访问可以用来生成随机位的公平硬币，则可以通过匿名机器人解决问题。在这种情况下，众所周知，机器人需要$ω（\logδ）$位的内存才能实现分散，其中$δ$是$ g $的最大度。另一方面，最著名的内存上限为$ min \ {δ，max \ {\logδ，\ log {d} \} \} $（$ d $ = $ g $的直径），这可以是$ω（\logδ）$，取决于$ $δ$和$ d $的值。在本文中，我们通过提出了需要$ o（\logδ）$内存的最佳算法来缩小这一差距。
Consider a team of $k \leq n$ autonomous mobile robots initially placed at a node of an arbitrary graph $G$ with $n$ nodes. The dispersion problem asks for a distributed algorithm that allows the robots to reach a configuration in which each robot is at a distinct node of the graph. If the robots are anonymous, i.e., they do not have any unique identifiers, then the problem is not solvable by any deterministic algorithm. However, the problem can be solved even by anonymous robots if each robot is given access to a fair coin which they can use to generate random bits. In this setting, it is known that the robots require $Ω(\logΔ)$ bits of memory to achieve dispersion, where $Δ$ is the maximum degree of $G$. On the other hand, the best known memory upper bound is $min \{Δ, max\{\logΔ, \log{D}\}\}$ ($D$ = diameter of $G$), which can be $ω(\logΔ)$, depending on the values of $Δ$ and $D$. In this paper, we close this gap by presenting an optimal algorithm requiring $O(\logΔ)$ bits of memory.
