مدلهای زمانبندی و شکست
مدلهای زمانبندی و شکست مشخص میکنند که یک الگوریتم توزیعشده چه فرضیاتی را میتواند در مورد تأخیر پیامها و سرعت پردازشگرها داشته باشد و چگونه اجزا مجاز به شکست هستند.
Definition
یک مدل زمانبندی فرضیات مربوط به کرانهای بالایی زمان تحویل پیام و سرعت نسبی فرآیند را تعیین میکند، در حالی که یک مدل شکست مجموعهای از روشهایی را که فرآیندها و کانالها ممکن است از رفتار مشخصشده خود منحرف شوند، تعیین میکند.
Scope
این موضوع مدلهای زمانبندی همگام، ناهمگام و نیمههمگام؛ طبقهبندی شکستها از خرابی (توقف-خرابی) از طریق حذف و زمانبندی تا خطاهای دلخواه (بیزانسی)؛ و انتزاع آشکارسازهای شکست را پوشش میدهد که سیستمهای ناهمگام و استدلال مبتنی بر زمانبندی را به هم متصل میکند. این مدلها اصول موضوعهای هستند که هم نتایج امکانپذیری و هم نتایج عدم امکانپذیری از آنها استخراج میشوند.
Core questions
- یک الگوریتم چه کرانهایی را برای تأخیر و سرعت میتواند فرض کند و زمانبندیها چگونه به آنها بستگی دارند؟
- یک پروتکل باید کدام کلاسهای شکست — خرابی، حذف، زمانبندی، بیزانسی — را پنهان کند؟
- چگونه میتوان سیستمهای ناهمگام را با آشکارسازهای شکست تقویت کرد تا نتایج عدم امکانپذیری را دور زد؟
Key theories
- همگامی جزئی
- سیستمهای واقعی نه کاملاً همگام و نه کاملاً ناهمگام هستند؛ مدل نیمههمگام کرانهایی را برای تأخیر و سرعت فرض میکند که در نهایت برقرار میشوند یا ناشناخته هستند، که برای حل اجماع در عین واقعبینانه ماندن کافی است.
- سلسله مراتب مدل شکست
- شکستها از خرابیهای خوشخیم توقف-خرابی، از طریق حذفهای ارسال/دریافت و نقضهای زمانبندی، تا رفتار دلخواه بیزانسی متغیر هستند؛ شدت شکستهایی که یک پروتکل باید تحمل کند، عامل تکثیر و پیچیدگی پیام مورد نیاز را دیکته میکند.
- آشکارسازهای شکست غیرقابل اعتماد
- یک آشکارساز شکست انتزاعی ممکن است نکات نادرستی در مورد اینکه کدام فرآیندها از کار افتادهاند ارائه دهد؛ توصیف ضعیفترین آشکارساز کافی برای حل اجماع، دقت ناهمگام را با پیادهسازیهای عملی مبتنی بر زمانبندی آشتی میدهد.
Clinical relevance
سیستمهای تولیدی به طور ضمنی یک مدل زمانبندی و شکست را هر زمان که زمانبندیها را تنظیم میکنند، یک عامل تکثیر را انتخاب میکنند، یا تصمیم میگیرند که در برابر شرکتکنندگان مخرب دفاع کنند، انتخاب میکنند؛ اشتباه گرفتن این فرضیات یک علت ریشهای رایج برای حوادث تقسیم مغز و از دست دادن دادهها است.
History
پس از اینکه مدل ناهمگام برای اجماع تحملپذیر در برابر خطا بسیار ضعیف نشان داده شد، دورک، لینچ و استاکمایر در سال 1988 همگامی جزئی را معرفی کردند و چاندرا و توگ در سال 1996 آشکارسازهای شکست غیرقابل اعتماد را رسمی کردند که در مجموع ابزارهای مدلسازی را فراهم کردند که توافق تحملپذیر در برابر خطا را ممکن میسازد.
Debates
- آیا زمانبندیها یک فرض زمانبندی هستند یا یک آشکارساز شکست؟
- یک دیدگاه زمانبندیها را به عنوان رمزگذاری یک کران همگامی (نهایی) در نظر میگیرد؛ دیدگاه دیگر آنها را به عنوان پیادهسازی یک آشکارساز شکست انتزاعی در نظر میگیرد. این دو چارچوب تا حد زیادی معادل هستند اما بر مرزهای طراحی متفاوتی بین مدل شبکه و الگوریتم تأکید میکنند.
Key figures
- Cynthia Dwork
- Nancy Lynch
- Larry Stockmeyer
- Tushar Chandra
- Sam Toueg
Related topics
Seminal works
- dwork1988
- chandra1996
- lynch1996
Frequently asked questions
- چرا تشخیص شکست قابل اعتماد را نمیتوان در یک سیستم کاملاً ناهمگام پیادهسازی کرد؟
- بدون کرانهایی برای تأخیر پیام، یک فرآیند به طور دلخواه کند اما زنده از یک فرآیند از کار افتاده قابل تشخیص نیست، بنابراین هر آشکارسازی باید گاهی اوقات اشتباه کند. به همین دلیل سیستمهای ناهمگام با فرضیات زمانبندی یا آشکارسازهای غیرقابل اعتماد تقویت میشوند.