解决异步下带移动故障的不透明机器人聚集难题，首次实现时间复杂度分析与抗遮挡能力。
Asynchronous Gathering of Opaque Robots with Mobility Faults
- 引入移动故障模型，故障仅影响移动能力，不影响灯光通信
- 用3色灯解决(2,1)系统聚集问题，证明2色灯不可能，且3色最优
- 提出两种算法，可在不同条件下实现快速聚集，适合分布式协同系统研究者
本文研究在异步环境下，具有移动故障的不透明机器人系统中的聚集问题。在$(N,f)$-移动故障系统中，最多有$f$个机器人因故障丧失移动能力但仍可操作灯光。我们证明：使用2色灯无法解决$(2,1)$-移动故障系统的聚集问题；而使用3色灯可构造最优解。对于未知$N,f$的$(N,f)$-移动故障系统（$f<N$），我们提出两个确定性算法：一个在$O(N)$时间内完成，使用7色灯；另一个在$O(\ ext{max}\{\ell,f\})$时间内完成，使用26色灯，其中$\ell < N$是初始配置中机器人位置的凸层数量。当$\ell, f = O(1)$时，该结果为最优。所提算法是首个分析时间复杂度、能处理遮挡（不透明机器人）和异步调度的解决方案。
原文摘要 · Abstract (English)
We consider the fundamental benchmarking problem of gathering in an $(N,f)$-fault system consisting of $N$ robots, of which at most $f$ might fail at any execution, under asynchrony. Two seminal results established impossibility of a solution in the oblivious robot (OBLOT) model in a $(2,0)$-fault system under semi-synchrony and in a $(3,1)$-Byzantine fault system under asynchrony. Recently, a breakthrough result circumvented the first impossibility result by giving a deterministic algorithm in a $(2,0)$-fault system under asynchrony in the luminous robot (LUMI) model using 2-colored lights. However, a breakthrough result established impossibility of gathering in a $(2,1)$-crash system in the LUMI model under semi-synchrony. In this paper, we consider a {\em mobility fault} model in which a robot crash only impacts it mobility but not the operation of the light. We establish four results under asynchrony in LUMI with the mobility fault model. We show that it is impossible to solve gathering in a $(2,1)$-mobility fault system using 2-colored lights, and then give a solution using 3-colored lights, which is optimal w.r.t. the number of colors. We then consider an $(N,f)$-mobility fault system, $f<N$, both $N,f$ not known, and give two deterministic algorithms that exhibit a nice time-color trade-off: The first with time $O(N)$ using 7-colored lights and the second with time $O(\max\{\ell,f\})$ using 26-colored lights, where $\ell< N$ is the number of distinct convex layers of robot positions in the initial configuration. Interestingly, for $l, f = O(1)$, our result is optimal. Our algorithms for an $(N,f)$-mobility fault system are the first to be analysed time complexity, can withstand obstructed visibility (opaque robot model) and asynchronous scheduling.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。