الخلاصة

  • علاقة happened-before هي أصغر ترتيب جزئي ينشأ من ترتيب الأحداث داخل العملية، ومن إرسال الرسالة قبل استلام الرسالة نفسها، ومن الإغلاق الانتقالي لهذه الروابط.
  • تعمل Clock Condition في اتجاه واحد: إذا كان a → b وجب أن يكون C(a) < C(b). ولا يثبت رقم قياسي أصغر أن a سبّب b أو أبلغه أو سبقه ماديًا.
  • الحدثان المتزامنان منطقيًا لا يربطهما مسار happened-before في أي من الاتجاهين. يعني ذلك أنهما غير مرتبين داخل نموذج الرصد، لا أنهما وقعا في اللحظة نفسها على ساعة مادية.

يسجل نظامان حدثين يبدوان حاسمين: يحمل A الزمن المنطقي 41 ويحمل B الرقم 42. ترتب لوحة التشغيل السطرين وترسم سهمًا يوحي بأن A سبّب B. تجعل الأرقام الرواية سهلة، لكنها لا تكمل الدليل.

لم يبحث بحث Leslie Lamport المنشور عام 1978، Time, Clocks, and the Ordering of Events in a Distributed System، عن ساعة عالمية مخفية. بل حدد بدقة أي ترتيب يستطيع النظام الموزع تبريره من دون تلك الساعة.

أصغر ترتيب ينشأ من الروابط المرصودة

يصوغ Lamport النظام على أنه عمليات لكل منها تسلسل من الأحداث وتتصل عبر الرسائل. وعلاقة happened-before هي أصغر علاقة تحقق ثلاث قواعد: يسبق الحدث المبكر في العملية الحدث اللاحق؛ يسبق إرسال الرسالة استلام الرسالة نفسها؛ وإذا سبق a الحدث b وسبق b الحدث c، سبق a الحدث c.

لكلمة «أصغر» أثر حاسم. فما لا تفرضه القواعد لا يُملأ بالتخمين. إذا لم يوجد a → b ولا b → a عُدّ الحدثان متزامنين منطقيًا، ولا يختار النموذج أحدهما أولًا لمجرد رسم خط زمني أنيق.

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

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

شرط الساعة تضمين لا تكافؤ

تسند الساعة المنطقية رقمًا إلى كل حدث. وتقول Clock Condition إنه إذا كان a → b فإن C(a) < C(b). ينفذ كل مسار ذلك بزيادة العداد بين الأحداث، وإرفاق القيمة بالرسالة، ثم دفع ساعة المستقبل إلى قيمة أكبر من قيمتها الحالية ومن طابع الرسالة.

تحفظ هذه القواعد الأسهم المعروفة. لكنها لا تسمح بالاستدلال العكسي: لا يكفي C(a) < C(b) للقول إن a → b.

هذا حد بنيوي لا تفصيل صغير. لو كانت كل مقارنة رقمية برهانًا على happened-before لوجب أن تحمل الأحداث المتزامنة منطقيًا القيمة نفسها. لكن قد يكون حدث واحد متزامنًا مع حدثين مرتبَين داخل عملية أخرى؛ ومساواة الثلاثة تنقض ذلك الترتيب الداخلي.

إذن يشهد الطابع القياسي بأن رابطًا معروفًا لم ينعكس رقميًا. ولا يشهد بوجود رابط سببي بين كل زوج تصاعدي.

الترتيب الكلي سياسة قرار

تحتاج بعض التطبيقات إلى اختيار واحد حين يسمح الترتيب الجزئي بأكثر من جواب. يبين Lamport إمكان الفرز بالزمن المنطقي، ثم استخدام ترتيب ثابت للعمليات لكسر التعادل. ينتج ترتيب كلي متسق مع happened-before.

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

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

المكالمة الهاتفية التي لم تدخل السجل

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

لا يستطيع خوارزم يراقب الأحداث الداخلية وحدها استعادة رابط لم يرصده قط. يقترح Lamport إدخال معلومة الترتيب الناقصة صراحة أو استخدام ساعات مادية مضبوطة تحت افتراضات أقوى.

قد يكون الرابط المفقود اليوم مكالمة دعم أو موافقة بشرية أو webhook أو طابورًا خارجيًا. وتعني عبارة «لم نجد مسارًا» أنه غير موجود في هذا الالتقاط، لا أنه لم توجد علاقة تأثير في الواقع.

الزمن المنطقي والمتجهي والمادي

تحفظ ساعة Lamport القياسية الاتجاه الذي تفرضه Clock Condition وتسمح بإنشاء ترتيب كلي متسق. وبعد نحو عقد طور Colin Fidge وFriedemann Mattern بنى زمن متجهي تحتفظ بمزيد من الترتيب الجزئي. أوضح Mattern أن إسقاط الأحداث الجزئية على أعداد خطية يفقد معلومات، لأن أحداثًا قد تكون متزامنة منطقيًا تتلقى أرقامًا مختلفة كأن لها ترتيبًا محددًا.

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

أما الساعة المادية فتجيب عن سؤال آخر. يناقش بحث Lamport نفسه Strong Clock Condition وخطأ معدل الساعة والانحراف والحد الأدنى لتأخير الرسائل وحدود الضبط. تقرب هذه الافتراضات العلامات من الزمن المادي مع هامش معلن؛ ولا تحول العداد المنطقي إلى ساعة حائط.

وتتطلب حدود التأليف الدقة نفسها. صاغ Lamport happened-before والساعات القياسية عام 1978، ونسب الفكرة السابقة لاستخدام طوابع الرسائل إلى Paul Johnson وBob Thomas. أما الساعات المتجهية فهي من أعمال Fidge وMattern اللاحقة.

ماذا يجب أن يرافق ادعاء الترتيب

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

عندئذ تكون النتيجة دقيقة: happened-before داخل النموذج الملتقط؛ تزامن منطقي داخله؛ موضع فرضته قاعدة تعادل؛ أسبقية مادية ضمن هامش؛ أو سبب دلالي لم يثبت بعد.

لم تكن مساهمة Lamport إذن ترخيصًا لترتيب كل شيء وتسميته حقيقة. بل كانت طريقة للفصل بين ترتيب يعرفه النظام، وترتيب يختاره، وترتيب لا يزال عاجزًا عن إثباته.

المصادر