TY - JOUR ID - 200179 TI - رنگ‌آمیزی گروندی خود‌ تثبیت‌کننده با استفاده از نظریه بازی‌ها و یافتار مرتب‌سازی JO - پدافند الکترونیکی و سایبری JA - ECD LA - fa SN - 2322-4347 AU - طاهری, سید محمود AU - حیدری, حسن AD - دانشگاه تهران Y1 - 2018 PY - 2018 VL - 6 IS - 2 SP - 39 EP - 48 KW - خرابی گذرا KW - امنیت شبکه KW - شبح مرکزی KW - تعادل نش KW - سیستم توزیع‌شده ناشناس DO - N2 - خرابی گذرا در سیستم‌های توزیع‌شده در شرایط مختلفی مانند خرابی پردازه‌ها و حمله‌های امنیتی رخ می‌دهد. یک الگوریتم خود تثبیت‌کننده با شروع از هر حالت دلخواه، در زمان متناهی به حالت قانونی می‌رسد و در مقابل خرابی گذرا مقاوم است. در این مقاله، نخست، برای مسئلۀ رنگ‌آمیزی گروندی، اولین الگوریتم قطعی خود تثبیت‌کننده مبتنی بر نظریه بازی‌ها را ارائه می‌کنیم. در این الگوریتم، که از قابلیت اجرا روی شبکه‌های ناشناس برخوردار است، برای کاهش تعداد رنگ‌های مصرفی، از یافتارهای مرتب‌سازی استفاده می‌کنیم. با به‌کارگیری تعادل نش، ثابت می‌کنیم که الگوریتم روی شبح مرکزی با پیچیدگی زمانی O(m) به رنگ‌آمیزی گروندی همگرا می‌شود که در آن m تعداد یال‌های شبکه است. نتایج شبیه‌سازی روی شبکه‌های مستقل از مقیاس، شبکه‌های تصادفی و شبکه‌های دنیای کوچک حاکی از آن است که به‌کارگیری یافتارهای مرتب‌سازی نسبت به عدم استفاده از آن‌ها موجب کاهش تعداد رنگ‌ها تا 18% و بهبود سرعت همگرایی به جواب تا 5% می‌گردد. UR - https://ecdj.ihu.ac.ir/article_200179.html L1 - https://ecdj.ihu.ac.ir/article_200179_e6600c2c5e3368b62936fd7b8030bff1.pdf ER -