On the Self-stabilization of Mobile Oblivious Robots in Uniform Rings - Sorbonne Université
Communication Dans Un Congrès Année : 2012

On the Self-stabilization of Mobile Oblivious Robots in Uniform Rings

Résumé

We investigate self-stabilizing algorithms for anonymous and oblivious robots in uniform ring networks, that is, we focus on algorithms that can start from any initial configuration (including those with multiplicity points). First, we show that there exists no probabilistic self-stabilizing gathering algorithm in the non-atomic CORDA model or if only global-weak and local-strong multiplicity detection is available. This impossibility result implies that a common assumption about initial configurations (no two robots share an node initially) is a very strong one. On the positive side, we give a probabilistic self-stabilizing algorithm for the gathering and orientation problems in the atomic ATOM model with global-strong multiplicity detection. With respect to impossibility results, those are the weakest system hypotheses. In addition, as an application of the previous algorithm, we provide a self-stabilizing algorithm for the set formation problem. Our results imply that any static set formation can be realized in a self-stabilizing manner in this model.
Fichier non déposé

Dates et versions

hal-00934149 , version 1 (21-01-2014)

Identifiants

Citer

Fukuhito Ooshita, Sébastien Tixeuil. On the Self-stabilization of Mobile Oblivious Robots in Uniform Rings. International Symposium on Stabilization, Safety, and Security of Distributed Systems, Oct 2012, Toronto, Canada. pp.49-63, ⟨10.1007/978-3-642-33536-5_6⟩. ⟨hal-00934149⟩
319 Consultations
0 Téléchargements

Altmetric

Partager

More