Consensus algorithms form the foundation for many distributed algorithms by enabling multiple robots to converge to consistent estimates of global variables using only local communication. However, standard consensus protocols can be easily led astray by non-cooperative team members. As such, the study of resilient forms of consensus is necessary for designing resilient distributed algorithms. W-MSR consensus is one such resilient consensus algorithm that allows for resilient consensus with only local knowledge of the communication graph and no a priori model for the data being shared. However, the verification that a given communication graph meets the strict graph connectivity requirement makes W-MSR difficult to use in practice. In this paper, we show that a commonly used communication graph structure in robotics literature, the communication graph built based on the Voronoi tessellation, automatically results in a sufficiently connected graph to reject a single non-cooperative team member. Further, we show how this graph can be enhanced to reject two non-cooperative team members and provide a roadmap for modifications for further resilience. This contribution will allow for the easy application of resilient consensus to algorithms that already rely on Voronoi-based communication such as distributed coverage and exploration algorithms.
翻译:共识运算法是许多分布式算法的基础,它使多个机器人能够仅仅使用当地通信,汇集到全球变量的一致估计中。然而,标准共识协议很容易被不合作的小组成员误导。因此,研究具有弹性的共识形式对于设计具有弹性分布式算法是必要的。W-MSR共识是一种具有弹性的共识算法,它只允许当地对通信图表的了解,而没有共享数据的先验模型,从而能够产生具有弹性的共识。然而,如果核实某一通信图符合严格的图形连通性要求,则难以在实践中使用W-MSR。在本文中,我们表明在机器人文献中常用的通信图表结构,即基于Voronoioi Tessellation的通信图,会自动产生一个足够连接的图表,从而拒绝一个不合作的单一小组成员。此外,我们展示如何加强这一图表,拒绝两个不合作的小组成员,并为进一步调整复原力提供一个路线图。这一贡献将便于对已经依赖Voronoi通信的算法应用具有弹性的具有弹性的共识,例如分布式的覆盖范围和探索算法。