Self-stabilizing gathering with strong multiplicity detection

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 th...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2012-04, Vol.428, p.47-57
Main Authors: Dieudonné, Yoann, Petit, Franck
Format: Article
Language:English
Subjects:
Computer Science
Distributed coordination
Gathering
Mobile robot networks
Self-stabilization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 n robots if, and only if, n is odd.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2011.12.010