الخلاصة

  • أثبت فيشر ولينش وباترسون أن كل بروتوكول توافق حتمي وصحيح جزئياً في نموذجهم غير المتزامن، مع احتمال تعطل عملية واحدة، له تنفيذ مقبول لا يصل إلى قرار أبداً.
  • يبقي التكوين ثنائي التكافؤ القيمتين ممكنتين. ويسمح تبديل ترتيب الأحداث المستقلة بتأجيل الحدث الحرج مع الاستمرار في خدمة العمليات وتسليم الرسائل بعدل.
  • تغيّر المزامنة الجزئية وكواشف الأعطال والعشوائية الفرضيات. قد يطلق انتهاء المهلة إجراءً، لكنه لا يثبت أن العملية البعيدة تعطلت.

عندما يصمت قائد في نظام موزع، يبدو عداد الوقت كأنه يحول الغموض إلى حقيقة. لكنه لا يرى سوى غياب الرد قبل حد اختاره المصمم. وفي عالم لا يضع سقفاً لزمن الرسالة، لا يمكن لهذا الصمت أن يميز بين عملية متوقفة وأخرى بطيئة.

حوّل مايكل ج. فيشر ونانسي أ. لينش ومايكل س. باترسون هذا الالتباس إلى برهان في بحثهم المنشور عام 1985، استحالة التوافق الموزع مع عملية معطلة واحدة. ليست النتيجة حكماً بأن التوافق العملي مستحيل. إنها تقول إن خوارزمية حتمية آمنة لا تستطيع، ضمن النموذج المحدد، ضمان القرار في كل تنفيذ مقبول إذا سُمح بعطل واحد.

رسائل موثوقة من دون موعد

تعمل العمليات بحتمية وتتبادل الرسائل. لا يوجد حد لسرعتها النسبية، ولا سقف لتأخير التسليم، ولا ساعة متزامنة. وقد تصل الرسالة متأخرة جداً أو بترتيب مختلف. لكنها لا تُفقد اعتباطاً: إذا كانت العملية المستقبلة غير معطلة وتواصل محاولات الاستقبال، فلا بد أن تصلها الرسالة في النهاية صحيحة ولمرة واحدة.

يسمح التنفيذ المقبول بعملية معطلة واحدة على الأكثر، ويلزم بتسليم الرسائل إلى العمليات غير المعطلة. وهذه العمليات تنفذ عدداً غير منته من الخطوات. لذلك لا يصنع البرهان الجمود بإخفاء رسالة إلى الأبد. يمكن للجدول أن يمنح كل عملية ورسالة دورها، فيما يؤجل القرار وحده مرة بعد مرة.

حتى شرط الإنهاء الذي يفشل ضعيف عمداً: يكفي أن تقرر عملية واحدة في كل تنفيذ مقبول. وإذا تعذر ضمان ذلك، استحال ضمان شروط أقوى.

التكافؤ الثنائي وصف للمستقبل

يجمع التكوين حالات العمليات الداخلية والرسائل المنتظرة. يكون صفرِي التكافؤ إذا انتهت كل امتداداته الحاسمة إلى الصفر، وأحادي التكافؤ للقيمة واحد بالطريقة نفسها، وثنائي التكافؤ إذا بقيت النتيجتان قابلتين للوصول.

يثبت المؤلفون أولاً وجود تكوين ابتدائي ثنائي التكافؤ. لو كانت كل التكوينات الابتدائية أحادية، لأمكن تغيير المدخلات عملية بعد أخرى حتى يظهر تكوينان متجاوران بنتيجتين متعارضتين. ولا يختلفان إلا في عملية واحدة. فإذا تعطلت قبل أن تتحرك، فلن تستطيع بقية العمليات التمييز بين العالمين، مع أنها مطالبة بقرارين مختلفين.

ثم ينظر البرهان إلى حدث قابل للتطبيق، مثل استلام رسالة معينة. لنفترض أن تنفيذه بعد أي تأجيل يحول الحالة حتماً إلى أحادية التكافؤ. عندئذ يجب أن توجد عتبة حرجة يثبت عندها حدث واحد النتيجة. لكن خطوات عمليتين مختلفتين قابلة للتبديل: تنفيذ أ ثم ب يصل إلى التكوين نفسه الذي يصل إليه ب ثم أ. يجمع هذا المربع مسارين يفترض أن لهما تكافؤين مختلفين في حالة واحدة، وهو تناقض.

إذن يمكن دائماً اختيار مقطع محدود، ثم تنفيذ الحدث المؤجل مع بقاء التكوين ثنائي التكافؤ. وبتكرار ذلك بالتناوب العادل بين العمليات والرسائل، يظهر تنفيذ غير منته، مقبول، ولا يقرر.

وجود مسار سيئ لا يعني أن كل المسارات سيئة

كمّية البرهان مهمة: يوجد تنفيذ غير حاسم، وليس كل تنفيذ غير حاسم. تصل الأنظمة الفعلية إلى القرار لأن مساراتها الواقعية ألطف من أسوأ ترتيب ممكن، أو لأنها تضيف فرضيات ليست في نموذج FLP. ما يسقط هو الضمان غير المشروط، لا القدرة العملية.

كذلك لا تصبح كل انتخابات متوقفة «حادثة FLP». قد يكون السبب فقدان حزم فعلياً، أو ضغط التخزين، أو خطأ عضوية، أو أعطالاً مترابطة، أو عيباً برمجياً. لا تفسر الإشارة إلى النظرية شيئاً ما لم يحدد التحليل النموذج وقيد السلامة وكيف منع تعذر التمييز بين التأخير والعطل ضمان التقدم.

ثلاثة تغييرات في العقد

صاغ دورك ولينش وستوكماير المزامنة الجزئية: قد توجد حدود زمنية لكنها مجهولة، أو تبدأ حدود معلومة في العمل بعد لحظة استقرار عالمية مجهولة. يستطيع البروتوكول التقدم عندما تسري تلك المرحلة الأقوى.

تضيف كواشف الأعطال لدى تشاندرا وتويغ خدمة معلومات ذات خصائص معلنة للاكتمال والدقة. لا تستخرج اليقين من الصمت. أما البروتوكولات العشوائية، ومنها عمل بن أور المبكر، فتغير فرضية الحتمية وتقدم وعداً احتمالياً بالإنهاء.

هذه ليست ثغرات في FLP، بل عقود جديدة تصرح بالمورد الإضافي الذي يحمل التقدم.

إنجاز مشترك ومنهج دائم

تروي لينش لاحقاً أنها وفيشر بدآ مطاردة المسألة عام 1982، ثم انضم باترسون إلى العمل الذي أنتج البرهان النهائي. الحفاظ على أسماء المؤلفين الثلاثة جزء من الدقة، لا مجرد مجاملة تاريخية.

يجب على النظام الناضج أن يعلن الأعطال التي يتحملها، وخصائص ساعاته وكاشف الأعطال، ومتى يقدم السلامة على التوافر، وتحت أي ظروف يتوقع الحيوية. لا تمنع FLP بناء التوافق؛ بل تمنع إخفاء شروطه خلف وعد مطلق.

المصادر