انحصار متقابل توزیعشده و انتخاب رهبر
انحصار متقابل و انتخاب رهبر از مسائل کلاسیک هماهنگی هستند: اطمینان از اینکه حداکثر یک فرآیند به یک منبع حیاتی دسترسی پیدا میکند، و انتخاب یک هماهنگکننده متمایز از میان همتایان.
Definition
انحصار متقابل توزیعشده تضمین میکند که حداکثر یک فرآیند در هر زمان یک منبع مشترک را در اختیار دارد، در حالی که دسترسی نهایی برای همه درخواستکنندگان را نیز تضمین میکند؛ انتخاب رهبر به طور قطعی دقیقاً یک فرآیند را به عنوان هماهنگکننده انتخاب میکند، به طوری که همه فرآیندها بر نتیجه توافق دارند.
Scope
این موضوع الگوریتمهای انحصار متقابل مبتنی بر مجوز (الگوریتم برچسب زمانی لمپورت، ریکارت-آگراوالا، رویکرد سهمیه ماکاوا) و الگوریتمهای مبتنی بر توکن را، به همراه پیچیدگی پیام و ویژگیهای انصاف آنها، پوشش میدهد؛ و همچنین الگوریتمهای انتخاب رهبر برای حلقهها (چانگ-رابرتز) و شبکههای عمومی (الگوریتم قلدری)، شامل مفروضات آنها در مورد شناسهها و همگامسازی. این اصول اولیه در سراسر خدمات هماهنگی و سیستمهای تکثیرشده تکرار میشوند.
Core questions
- چگونه فرآیندها میتوانند دسترسی به یک منبع مشترک را تنها با استفاده از پیامها سریالسازی کنند؟
- موازنه بین پیچیدگی پیام و انصاف در طرحهای مبتنی بر مجوز و مبتنی بر توکن چیست؟
- چگونه یک رهبر منحصر به فرد انتخاب میشود و چگونه پس از شکست رهبر، انتخابات دوباره آغاز میشود؟
Key theories
- انحصار متقابل مبتنی بر مجوز
- الگوریتمهایی مانند ریکارت-آگراوالا درخواستها را بر اساس برچسبهای زمانی منطقی مرتب میکنند و پس از دریافت مجوز از همه (یا سهمیهای از) همتایان، ورود را اعطا میکنند و به این ترتیب با هزینه پیام محدود برای هر ورود به بخش حیاتی، انصاف را محقق میسازند.
- انحصار متقابل مبتنی بر توکن
- یک توکن منحصر به فرد در گردش است یا در صورت تقاضا درخواست میشود، و فقط دارنده آن میتواند وارد بخش حیاتی شود، که ترافیک پیام را کاهش میدهد اما به مکانیزمهایی برای بازتولید توکن گمشده پس از خرابیها نیاز دارد.
- انتخاب رهبر
- الگوریتمهای انتخاب مانند چانگ-رابرتز برای حلقهها و الگوریتم قلدری برای شبکههای عمومی از شناسههای فرآیند برای همگرایی بر روی یک هماهنگکننده واحد با بالاترین اولویت استفاده میکنند که همه فرآیندهای صحیح آن را تشخیص میدهند.
Clinical relevance
انتخاب رهبر هر زمان که یک سیستم تکثیرشده باید یک اولیه (primary) یا هماهنگکننده را انتخاب کند، فراخوانی میشود، و قفلگذاری توزیعشده انحصار متقابل را تعمیم میدهد؛ هر دو به عنوان خدمات اصلی توسط سیستمهای هماهنگی مورد استفاده در سراسر زیرساخت ابری ارائه میشوند.
History
مقاله ساعت منطقی لمپورت در سال ۱۹۷۸ یک الگوریتم انحصار متقابل مبتنی بر برچسب زمانی را معرفی کرد؛ ریکارت و آگراوالا آن را در سال ۱۹۸۱ بهینهسازی کردند، ماکاوا اندکی پس از آن سهمیهها را معرفی کرد، و الگوریتم قلدری گارسیا-مولینا در سال ۱۹۸۲ انتخاب رهبر را رسمی کرد و الگوریتمهای هماهنگی متعارف را به این حوزه بخشید.
Key figures
- Leslie Lamport
- Glenn Ricart
- Ashok Agrawala
- Hector Garcia-Molina
Related topics
Seminal works
- ricart1981
- garcia-molina1982
- lynch1996
Frequently asked questions
- انحصار متقابل توزیعشده چه تفاوتی با قفل در یک ماشین واحد دارد؟
- حافظه مشترک یا مدیر قفل مرکزی برای تکیه بر آن وجود ندارد، بنابراین فرآیندها باید صرفاً با تبادل پیامها هماهنگ شوند و باید به صراحت تأخیر پیام و خرابیها را مدیریت کنند، که یک قفل تک ماشینی میتواند آن را بدیهی فرض کند.