سیستم های عامل توزیع شده (قراردادهای توافق ـ Agreement Protocols):
- در مواردی سایت‌ها باید با هم به توافقی برسند. مثلاً تصمیم به Abort یا Commit در DBSs.
- هر سایت باید از مقادیر سایت‌های دیگر مطلع باشد.
- تصمیم در غیاب خطا ::
- تصمیم در حضور خطا؟ چرا که سایت‌های خطادار مقادیر غلطی می‌فرستند.
قرارداد توافق:
- پردازه رسیدن به تصمیم در حضور خطا به وسیله رله کردن چندباره‌ی اطلاعات پردازه‌ها به یکدیگر به منظور محو اثر پردازه‌های خطادار.
- فرض: وجود یک مدل عمومی از خطا: ارسال پیغام مشکوک به دیگران، پایین بودن سایت، پاسخ درست ندادن به پیغام‌ها.
- نکته: پردازه‌های سالم خبری از پردازه‌های خراب ندارند.
مدل:
- n تا پردازنده در سیستم وجود دارد که m تای آنها خطادار هستند.
- سیستم منطقاً کاملاً مرتبط است.
- تنها خطای پردازنده مطرح است و خطای رسانه ارتباطی نداریم.
- برای سادگی فرض بر توافق روی مقدار صفر و یک است.
- محاسبات همگام: پردازنده‌های سیستم در یک حالت قفلی/مرحله‌ای عمل می‌کنند. هر پردازه پیغامی که در مرحله قبل ارسال شده بود را دریافت می‌کند، محاسبه‌ای انجام می‌دهد و پیغام‌هایی را ارسال می‌کند.
- هر مرحله را یک round می‌نامیم. تأخیر پیغامی یا سرعت کند یک پردازنده کل محاسبات را کند می‌کند.
- پیغام‌ها non-Authenticated هستند: پردازنده‌ای می‌تواند پیغامی را جعل کند و یا محتویات ان را عوض کند و سپس آن را رله کند.
ازریابی کارایی:
- زمان: تعداد دور
- ترافیک پیغامی
- سربار حافظه‌ای
دسته‌بندی مسائل توافقی:
۱ ـ توافق Byzantine :
مقدار اولیه‌ای که قرار است روی آن توافق شود توسط پردازنده‌ای بی‌خطا اعلام و همه پردازنده‌های بی‌خطا مجبور به توافق روی آن مقدار هستند.
راه‌حل این مسئله باید:
- توافق: توافق همه پردازنده‌های بی‌خطا روی آن مقدار مشترک.
- اعتبار: اگر پردازنده مبدأ بی‌خطاست، مقدار توافق شده همان مقدار اولیه باشد.
- نکته: اگر مبدأ خطادار باشد، پردازنده‌های بی‌خطا روی هر مقدار مشترکی می‌توانند توافق کنند.
- مهم نیست که پردازنده‌های خطادار روی چه مقدار مشترکی توافق کرده‌اند و یا اصلاًً توافق کرده‌اند.
۲ ـ اجماع:
هر پردازنده مقدار اولیه خود را منتشر می‌کند. همه پردازنده‌های بی‌خطا باید روی مقدار مشترکی توافق کنند.
۳ ـ سازگاری محاوره‌ای (Interactive Consistency):
- هر پردازنده مقدار اولیه خاص خود را دارد. همه پردازنده‌ها روی مجموعه یکسانی توافق می کنند.
- اگر پردازنده‌ای خطا دارد (مثل j )، سپس همه پردازنده های بی‌خطا می‌توانند روی هر مقدار مشترک برای j توافق داشته باشند (Vj).