خلاصة:
خرابی گذرا در سیستم های توزیع شده در شرایط مختلفی مانند خرابی پردازه ها و حمله های امنیتی رخ می دهد. یک الگوریتم خود تثبیت کننده با شروع از هر حالت دلخواه، در زمان متناهی به حالت قانونی می رسد و در مقابل خرابی گذرا مقاوم است. در این مقاله، نخست، برای مسئله رنگ آمیزی گروندی، اولین الگوریتم قطعی خود تثبیت کننده مبتنی بر نظریه بازی ها را ارائه می کنیم. در این الگوریتم، که از قابلیت اجرا روی شبکه های ناشناس برخوردار است، برای کاهش تعداد رنگ های مصرفی، از یافتارهای مرتب سازی استفاده می کنیم. با به کارگیری تعادل نش، ثابت می کنیم که الگوریتم روی شبح مرکزی با پیچیدگی زمانی O (m) به رنگ آمیزی گروندی همگرا می شود که در آن m تعداد یال های شبکه است. نتایج شبیه سازی روی شبکه های مستقل از مقیاس، شبکه های تصادفی و شبکه های دنیای کوچک حاکی از آن است که به کارگیری یافتارهای مرتب سازی نسبت به عدم استفاده از آن ها موجب کاهش تعداد رنگ ها تا 18% و بهبود سرعت همگرایی به جواب تا 5% می گردد.
ملخص الجهاز:
در این مقاله، نخست، برای مسئلۀ رنگآمیزی گروندی، اولین الگوریتم قطعی خود تثبیتکننده مبتنی بر نظریه بازیها را ارائه میکنیم.
در این الگوریتم، که از قابلیت اجرا روی شبکههای ناشناس برخوردار است، برای کاهش تعداد رنگهای مصرفی، از یافتارهای مرتبسازی استفاده میکنیم.
با بهکارگیری تعادل نش، ثابت میکنیم که الگوریتم روی شبح مرکزی با پیچیدگی زمانی () به رنگآمیزی گروندی همگرا میشود که در آن تعداد یالهای شبکه است.
برای مسئلۀ رنگآمیزی رأسی، الگوریتم خود تثبیتکننده نیز ارائه شده است.
در این مقاله برای مسئلۀ رنگآمیزی گروندی، یک الگوریتم قطعی خودتثبیتکننده و مبتنی بر نظریه بازیها، ارائه میکنیم.
با استفاده از تعادل نش، ثابت میکنیم که پیچیدگی الگوریتم پیشنهادی روی شبح مرکزی از مرتبه () است.
در بخش 3، با به کارگیری تعادل نش، یک الگوریتم مبتنی بر نظریه بازیها برای مسئلۀ رنگآمیزی گروندی خود تثبیتکننده روی شبح مرکزی ارائه میکنیم.
بر اساس قضیه 3، پس از رسیدن به تعادل نش، ترکیب راهبرد ، یک رنگآمیزی گروندی خودتثبیتکننده است و اثبات کامل میشود.
در این مقاله، یک الگوریتم مبتنی بر نظریه بازیها برای مسئلۀ رنگآمیزی گروندی خودتثبیتکننده روی شبح مرکزی و سیستمهای توزیعشده ناشناس ارائه کردیم که در برابر خرابی گذرا مقاوم است.
برای آینده تحقیق، ارائه یک الگوریتم رنگآمیزی گروندی خودتثبیتکننده و مبتنی بر نظریه بازیها را روی شبح همگام و شبح توزیعشده پیشنهاد میکنیم.
Kheddouci, A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs, Journal of Parallel and Distributed Computing, vol.
Johnen, Silent self-stabilizing BFS tree algorithms revisited, Journal of Parallel and Distributed Computing, vol.