کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874214 1441029 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On deterministic rendezvous at a node of agents with arbitrary velocities
ترجمه فارسی عنوان
در رویکرد مخرب در گره ای از عوامل با سرعت دلخواه
کلمات کلیدی
قرار ملاقات قطعی، الگوریتم ها، عامل موبایل، سرعت
ترجمه چکیده
ما وظیفه قرار ملاقات در شبکه ها را به عنوان نمودار های غیر مستقیم هدایت می کنیم. دو عامل تلفن همراه با برچسب های مختلف، با شروع از گره های مختلف یک نمودار ناشناس، باید ملاقات کنند. این کار در ادبیات تحت دو سناریوی جایگزین قرار گرفته است: ضعیف و قوی. در سناریو ضعیف، عوامل ممکن است در یک گره یا در داخل لبه دیدار کنند. تحت سناریوی قوی، آنها باید در یک گره ملاقات کنند و حتی جلسات را در لبه متوجه نمی شوند. الگوریتم های ملاقات در زیر سناریو قوی برای عوامل همزمان شناخته شده است. برای عوامل ناهمزمان، قرار گرفتن در زیر سناریوی قوی حتی در گراف دو گره غیر ممکن است، و از این رو تنها الگوریتم های تحت سنسور ضعیف ساخته شده است. در این مقاله ما نشان می دهیم که قرار گرفتن در معرض دید در سناریوی قوی برای عوامل با آسینچری محدود به روش زیر می باشد: عامل ها یک اندازه گیری زمان دارند، اما دشمن می تواند برای هر عامل و هر لبه، سرعت حرکت این لبه را این عامل سرعت ها ممکن است برای لبه های مختلف و عوامل مختلف متفاوت باشند، اما تمام گذرگاه های یک لبه داده شده توسط یک عامل خاص باید با همان سرعت تحمیل شده باشد. ما یک الگوریتم مرسوم را برای چنین عوامل ایجاد می کنیم، که در چند جمله ای زمان در اندازه گراف، در طول برچسب کوچکتر و در بزرگترین زمان عبور لبه، کار می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
در رویکرد مخرب در گره ای از عوامل با سرعت دلخواه
چکیده انگلیسی
We consider the task of rendezvous in networks modeled as undirected graphs. Two mobile agents with different labels, starting at different nodes of an anonymous graph, have to meet. This task has been considered in the literature under two alternative scenarios: weak and strong. Under the weak scenario, agents may meet either at a node or inside an edge. Under the strong scenario, they have to meet at a node, and they do not even notice meetings inside an edge. Rendezvous algorithms under the strong scenario are known for synchronous agents. For asynchronous agents, rendezvous under the strong scenario is impossible even in the two-node graph, and hence only algorithms under the weak scenario were constructed. In this paper we show that rendezvous under the strong scenario is possible for agents with asynchrony restricted in the following way: agents have the same measure of time but the adversary can impose, for each agent and each edge, the speed of traversing this edge by this agent. The speeds may be different for different edges and different agents but all traversals of a given edge by a given agent have to be at the same imposed speed. We construct a deterministic rendezvous algorithm for such agents, working in time polynomial in the size of the graph, in the length of the smaller label, and in the largest edge traversal time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 133, May 2018, Pages 39-43
نویسندگان
, , , ,