الطابع الزمني لامبورت

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

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

ابتكر لامبورت آلية بسيطة يمكن من خلالها تمثيل ترتيب "حدث قبل" باستخدام القيم الرقمية. ساعة لامبورت المنطقية هي قيمة عداد برمجية رقمية يتم الاحتفاظ بها في كل عملية.

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

 خوارزمية 
تتبع الخوارزمية بعض القواعد البسيطة:

 تزيد العملية من عدادها قبل كل حدث محلي (على سبيل المثال، حدث إرسال رسالة)؛
 عندما ترسل عملية رسالة، فإنها تتضمن قيمة العداد الخاصة بها مع الرسالة بعد تنفيذ الخطوة 1؛
 عند استلام رسالة، يتم تحديث عداد المستلم، إذا لزم الأمر، إلى الرقم الأكبر من عداده الحالي وعلامة الوقت في الرسالة المستلمة. يتم بعد ذلك زيادة العداد بمقدار 1 قبل اعتبار الرسالة مستلمة. 

في الكود الزائف ، خوارزمية الإرسال هي:
 # الحدث معروف
 الزمن = الزمن + 1؛
 # يحدث الحدث
 إرسال(الرسالة، الوقت)؛
الخوارزمية لاستقبال الرسالة هي:
 (الرسالة، الطابع الزمني) = استلام();
 الوقت = الحد الأقصى (الطابع الزمني، الوقت) + 1؛

 الاعتبارات 
بالنسبة لكل حدثين مختلفين  و  يحدثان في نفس العملية، وباعتبار  هو الطابع الزمني لحدث معين  ، من الضروري أن  لا يكون مساويًا لـ  .

ولذلك فمن الضروري أن:

 يتم ضبط الساعة المنطقية بحيث يكون هناك حد أدنى من "دقات" الساعة (زيادة العداد) بين الأحداث  و  ؛
 في بيئة متعددة العمليات أو متعددة الخيوط، قد يكون من الضروري إرفاق معرف العملية (PID) أو أي معرف فريد آخر بطابع الوقت حتى يكون من الممكن التمييز بين الأحداث  و  والتي قد تحدث في وقت واحد في عمليات مختلفة.

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

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

هذه العلاقة تسير في اتجاه واحد فقط، وتُعرف بشرط اتساق الساعة : إذا سبق حدث ما حدثا آخر، فإن الساعة المنطقية لذلك الحدث تسبق ساعة الحدث الآخر. ويمكن تحقيق شرط اتساق القوي للساعة ، الذي يكون ثنائي الاتجاه (إذا  فإن  )، باستخدام تقنيات أخرى مثل الساعات المتجهة.

وعند استخدام ساعة لامبورت البسيطة فقط، لا يمكن استنتاج سوى ترتيب سببي جزئي من الساعة.

ومع ذلك، من خلال المقابل المنطقي، فإن  يُشير إلى أن .فعلى سبيل المثال، إذا كان  ثم  فلا يمكن أن يكون حدث من قبل  .

طريقة أخرى للتعبير عن ذلك هي أن  وهي تعني أن  قد يكون قد حدث قَبل  أو لا يمكن مقارنته بـ  في ترتيب "حث قبل"، ولكن  لم يحدث بعد  .

ومع ذلك، يمكن استخدام الطوابع الزمنية Lamport لإنشاء ترتيب كلي للأحداث في نظام موزع من خلال آلية عشوائية لكسر التعادلات (مثل معرف العملية). لكن التحذير هو أن هذا الترتيب اصطناعي ولا يمكن الاعتماد عليه للدلالة على وجود علاقة سببية.

 ساعة لامبورت المنطقية في الأنظمة الموزعة 
في نظام موزع، لا يمكن عمليًا مزامنة الوقت بين الكيانات (والتي تُعتبر عادةً عمليات) داخل النظام؛ وبالتالي، يمكن للكيانات استخدام مفهوم الساعة المنطقية استنادًا إلى الأحداث التي تتواصل من خلالها.

إذا لم تتبادل كيانان أي رسائل، فغالبًا لا يحتاجان إلى مشاركة ساعة مشتركة؛ وتسمى الأحداث التي تحدث على هذه الكيانات بالأحداث المتزامنة.

من بين العمليات على نفس الجهاز المحلي، يمكننا ترتيب الأحداث استنادًا إلى الساعة المحلية للنظام.

عندما يتواصل كيانان عبر تمرير الرسائل، يُقال إن حدث الإرسال يحدث قبل حدث الاستلام، ويمكن الترتيب المنطقي بين الأحداث.

يُقال إن النظام الموزع يحتوي على ترتيب جزئي بين الأحداث في النظام. وإذا أمكن تحديد "الكل"، أي العلاقة السببية بين جميع الأحداث في النظام، فيقال أن النظام يتمتع بالنظام الكلي.

لا يمكن لكيان واحد أن تحدث فيه حدثان في الوقت نفسه. إذا كان النظام يحتوي على ترتيب كلي، فيمكننا تحديد الترتيب بين جميع الأحداث في النظام. أما إذا كان النظام يحتوي على ترتيب جزئي بين العمليات، وهو نوع الترتيب الذي توفره ساعة لامبورت المنطقية، فإنه يمكننا فقط تحديد الترتيب بين الكيانات التي تتفاعل مع بعضها. وقد تناول لامبورت مسألة ترتيب حدثين لهما نفس الطابع الزمني (أو العداد)، حيث قال: "لكسر التعادلات، نستخدم أي ترتيب إجمالي تعسفي  "من العمليات." Lamport, L. (1978). "Time, clocks, and the ordering of events in a distributed system" (PDF). Communications of the ACM . 21 (7): 558–565. doi:10.1145/359545.359563. S2CID 215822405. وبالتالي، قد تكون هناك طوابع زمنية أو عدادات متساوية داخل نظام موزع، ولكن عند تطبيق خوارزمية الساعات المنطقية، فإن الأحداث التي تحدث ستحافظ دائمًا على ترتيب جزئي صارم على الأقل.

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

لاحظ أنه بِاستخدام ساعات لامبورت، لا يمكن قول أي شيء عَن الوقت الفعلي للحدثين  و  . إذا قالت الساعة المَنطِقية إن  فَهذا لا يَعني فِي الواقع أن  حدث فعلياً قبل  من حيث الوقت الحقيقي.

تُظهر ساعات لامبورت غياب السببية، لكنها لا تلتقط جميع العلاقات السببية. فمعرفة أن  و  تظهر أن  لم يتسبب في  أو  لكن لا يمكننا تحديد أي منهما بدأ  .

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

 بدائل للسببية المحتملة 
علاقة "حدث قبل" تلتقط السببية المحتملة، وليس السببية الحقيقية. في عام 2011-2012، اقترح مونيندار سينغ منهجًا تصريحيًا متعدد الوكلاء يعتمد على السببية الحقيقية يسمى بروتوكولات المعلومات. يحدد بروتوكول المعلومات القيود المفروضة على الاتصالات بين الوكلاء الذين يشكلون نظامًا موزعًا.  ومع ذلك، بدلاً من تحديد ترتيب الرسائل (على سبيل المثال، عبر آلة الحالات، وهي طريقة شائعة لتمثيل البروتوكولات في الحوسبة)، يحدد بروتوكول المعلومات تبعيات المعلومات بين الاتصالات التي قد يرسلها الوكلاء (نقاط نهاية البروتوكول). يمكن للوكيل إرسال اتصال في حالة محلية (تاريخه الاتصالي) فقط إذا كانت الرسالة والحالة معًا تلبيان تبعيات المعلومات ذات الصلة. على سبيل المثال، قد يحدد بروتوكول معلومات لتطبيق تجارة إلكترونية أنه لإرسال عرض سعر يحتوي على معرّف ID (المُوَحِّد) وعنصر وسعر، يجب أن يعرف البائع بالفعل معرف العنصر من حالته ولكن يمكنه إنشاء أي سعر يريده. الأمر المثير للدهشة في بروتوكولات المعلومات هو أنه على الرغم من أن الانبعاثات مقيدة، فإن الاستقبالات ليست كذلك. على وجه التحديد، قد يتلقى الوكلاء الاتصالات بأي ترتيب كان - فالاستقبالات ببساطة تحمل المعلومات وليس هناك معنى لتأخيرها. وهذا يعني أنه يمكن تنفيذ بروتوكولات المعلومات عبر خدمات الاتصال غير المنظمة مثل UDP .

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

 انظر أيضًا 

 ساعة المصفوفة
 ساعة متجهة
 ناقل الإصدار

 المراجع 

تصنيف:خوارزميات