论文标题
机器人有故障的情况下的圆锥形形成
Conic Formation in Presence of Faulty Robots
论文作者
论文摘要
模式形成是分布式计算中最根本的问题之一，最近引起了很多关注。在本文中，我们在某些机器人可以是\ textit {frescit}的情况下启动了分布式模式形成的研究。特别是，我们考虑了具有完善的\ textit {look-compute-move}模型，该模型具有遗忘的匿名机器人。我们首先提出下限，并表明任何确定性算法至少需要两轮在存在故障机器人的情况下形成简单模式。然后，我们为我们的问题提供了分布式算法，该算法与此绑定\ textit {for conic pection}相匹配：在最多两轮中，机器人形成线条，圆圈和抛物线，分别可容忍$ f = 2,3 $和$ 4 $的故障。对于$ f = 5 $，目标模式是抛物线，双曲线和椭圆形。我们表明，由此产生的模式包括$ n $机器人的$ f $有故障机器人，其中$ n \ geq 2f+1 $，以及$ f <n <2f+1 $ $机器人无法形成此类模式。我们通过讨论几种放松和扩展来结束。
Pattern formation is one of the most fundamental problems in distributed computing, which has recently received much attention. In this paper, we initiate the study of distributed pattern formation in situations when some robots can be \textit{faulty}. In particular, we consider the well-established \textit{look-compute-move} model with oblivious, anonymous robots. We first present lower bounds and show that any deterministic algorithm takes at least two rounds to form simple patterns in the presence of faulty robots. We then present distributed algorithms for our problem which match this bound, \textit{for conic sections}: in at most two rounds, robots form lines, circles and parabola tolerating $f=2,3$ and $4$ faults, respectively. For $f=5$, the target patterns are parabola, hyperbola and ellipse. We show that the resulting pattern includes the $f$ faulty robots in the pattern of $n$ robots, where $n \geq 2f+1$, and that $f < n < 2f+1$ robots cannot form such patterns. We conclude by discussing several relaxations and extensions.
