کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434157 689692 2015 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the self-stabilization of mobile oblivious robots in uniform rings
ترجمه فارسی عنوان
در تثبیت خود را از روبات های تلفن همراه فراموش شده در حلقه های یکنواخت
کلمات کلیدی
روبات های موبایل حلقه، جمع آوری گرایش، تنظیم تشکیل
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• We investigate self-stabilizing (SS) algorithms for oblivious robots in rings.
• We propose probabilistic SS algorithms for the gathering and orientation problems.
• Our algorithms assume the SSYNC model and the global-strong multiplicity detection.
• We show these assumptions are weakest to realize probabilistic SS algorithms.

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 no probabilistic self-stabilizing gathering algorithm exists in the asynchronous (ASYNC) 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 a 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 semi-synchronous (SSYNC) 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 568, 23 February 2015, Pages 84–96
نویسندگان
, ,