Self-stabilizing gathering with strong multiplicity detection

详细信息	查看全文 | 推荐本文 |

• 作者：Yoann Dieudonné ; ^a ; ^{yoann.dieudonne@u-picardie.fr} ; Franck Petit^b
• 关键词：Distributed coordination ; Gathering ; Mobile robot networks ; Self-stabilization
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：13 April, 2012
• 卷：428
• 期：Complete
• 页码：47-57
• 文件大小：274 K

摘要

In this paper, we investigate the possibility to deterministically solve the gathering problem starting from an arbitrary configuration with weak robots, i.e.,聽anonymous, autonomous, disoriented, oblivious, and devoid of means of communication. By starting from an arbitrary configuration, we mean that robots are not required to be located at distinct positions in the initial configuration. We introduce strong multiplicity detection as the ability for the robots to detect the exact number of robots located at a given position. We show that with strong multiplicity detection, there exists a deterministic algorithm solving the gathering problem starting from an arbitrary configuration for robots if, and only if, is odd.