رنگآمیزی گروندی خود تثبیتکننده با استفاده از نظریه بازیها و یافتار مرتبسازی | ||
| پدافند الکترونیکی و سایبری | ||
| مقاله 5، دوره 6، شماره 2 - شماره پیاپی 22، تابستان 1397، صفحه 39-48 اصل مقاله (1.03 M) | ||
| نوع مقاله: مقاله پژوهشی | ||
| نویسندگان | ||
| سید محمود طاهری* ؛ حسن حیدری | ||
| دانشگاه تهران | ||
| چکیده | ||
| خرابی گذرا در سیستمهای توزیعشده در شرایط مختلفی مانند خرابی پردازهها و حملههای امنیتی رخ میدهد. یک الگوریتم خود تثبیتکننده با شروع از هر حالت دلخواه، در زمان متناهی به حالت قانونی میرسد و در مقابل خرابی گذرا مقاوم است. در این مقاله، نخست، برای مسئلۀ رنگآمیزی گروندی، اولین الگوریتم قطعی خود تثبیتکننده مبتنی بر نظریه بازیها را ارائه میکنیم. در این الگوریتم، که از قابلیت اجرا روی شبکههای ناشناس برخوردار است، برای کاهش تعداد رنگهای مصرفی، از یافتارهای مرتبسازی استفاده میکنیم. با بهکارگیری تعادل نش، ثابت میکنیم که الگوریتم روی شبح مرکزی با پیچیدگی زمانی O(m) به رنگآمیزی گروندی همگرا میشود که در آن m تعداد یالهای شبکه است. نتایج شبیهسازی روی شبکههای مستقل از مقیاس، شبکههای تصادفی و شبکههای دنیای کوچک حاکی از آن است که بهکارگیری یافتارهای مرتبسازی نسبت به عدم استفاده از آنها موجب کاهش تعداد رنگها تا 18% و بهبود سرعت همگرایی به جواب تا 5% میگردد. | ||
| کلیدواژهها | ||
| خرابی گذرا؛ امنیت شبکه؛ شبح مرکزی؛ تعادل نش؛ سیستم توزیعشده ناشناس | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 759 تعداد دریافت فایل اصل مقاله: 439 |
||