نماذج التوقيت والفشل
تحدد نماذج التوقيت والفشل ما يمكن أن تفترضه الخوارزمية الموزعة بشأن تأخيرات الرسائل وسرعات المعالج، وكيف يُسمح للمكونات بالفشل.
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
- لماذا لا يمكن تنفيذ الكشف الموثوق عن الفشل في نظام غير متزامن بحت؟
- بدون حدود لتأخير الرسائل، لا يمكن تمييز عملية بطيئة بشكل تعسفي ولكنها حية عن عملية معطلة، لذا يجب أن يكون أي كاشف خاطئًا في بعض الأحيان. هذا هو السبب في تعزيز الأنظمة غير المتزامنة بافتراضات التوقيت أو الكاشفات غير الموثوقة.