الطابع الزمني لامبورت
المحتويات
في البداية، خوارزمية الطابع الزمني Lamport هي خوارزمية بسيطة للساعة منطقية تُستعمل لتحديد ترتيب الأحداث في نظام حاسوبي موزع . نظرًا لأن العقد أو العمليات المختلفة عادةً لا تكون متزامنة بشكل تام، تُستعمل هذه الخوارزمية لتوفير ترتيب جزئي للأحداث بأقل تكلفة ممكنة، وتمثل الناحية المفاهيمية نقطة انطلاق لطريقة الساعة الاتجاهية الأكثر تقدمًا. الخوارزمية على اسم مبتكرها، ليزلي لامبورت . وتعرض الأقسام التالية جوانب أخرى من الموضوع.
كذلك، ابتكر لامبورت آلية بسيطة يمكن من خلالها تمثيل ترتيب "حدث قبل" باستخدام القيم الرقمية. ساعة لامبورت المنطقية هي قيمة عداد برمجية رقمية يتم الاحتفاظ بها في كل عملية.
وعلى صعيد آخر، تعتمد الخوارزميات الموزعة مثل تزامن الموارد غالبًا على طريقة ما لترتيب الأحداث حتى تعمل بشكل صحيح. مثلًا، لنفترض وجود نظام يتكون من عمليتين وقرص تخزين. تتبادل العمليات رسائل فيما بينها، كما ترسل كذلك رسائل إلى القرص لطلب الوصول. يمنح القرص الوصول حسب ترتيب استلام الرسائل. فمثلًا، ترسل العملية رسالة إلى القرص تطلب فيها إذن الكتابة، ثم ترسل تعليمات قراءة إلى العملية . تستلم العملية الرسالة، ونتيجة لذلك ترسل بدورها طلب قراءة إلى القرص. إذا حصل تأخير زمني أدى إلى استلام القرص للرسالتين في نفس اللحظة، فيمكنه تحديد أي من الرسالتين، فيمكنه تحديد الرسالة التي حدثت قبل الأخرى: يحدث قبل إذا كان بإمكان المرء الحصول عليه من ل بسلسلة من التحركات من نوعين: الانتقال إلى الأمام ضمن نفس العملية، واتباع الرسالة من إرسالها إلى استقبالها. توفر خوارزمية الساعة المنطقية آلية لتحديد الحقائق حول ترتيب مثل هذه الأحداث. لاحظ أنه إذا حدث حدثان في عمليتين مختلفتين لا تتبادلان الرسائل بشكل مباشر أو غير مباشر عبر عمليات تابعة لجهة خارجية، فإننا نقول إن العمليتين متزامنتان، أي أنه لا يمكن قول أي شيء عن ترتيب الحدثين.
وفي السياق ذاته، من الناحية المفاهميمية، يمكن اعتبار هذه الساعة المنطقية كساعة لا يكون لها معنى إلا فيما يتعلق بالرسائل المتبادلة بين العمليات. عند استلام عملية ما لرسالة، فإنها تعيد مزامنة الساعة المنطقية الخاصة بها مع هذا المرسل. إن ساعة المتجهات المذكورة أعلاه هي تعميم للفكرة في سياق عدد عشوائي من العمليات المتوازية المستقلة.
الترتيب السببي
في هذا الإطار، بالنسبة لأي حدثين، و ، إذا كان هناك أي احتمال لأن يكون قد أثر في ، فإن الطابع الزمني لامبورت للحدث سيكون أقل من الطابع الزمني لـ Lamport للحدث . ومن الممكن كذلك وجود حدثين لا يمكن تحديد أيهما حدث أولاً؛ وعندما يحدث ذلك، فهذا يعني أنهما لا يمكن أن يؤثرا على بعضهما البعض. وإذا لم يكن بالإمكان أن يؤثر و على بعضهما، فلا يهم أيهما حدث أولًا.
تداعيات
ومن جهة أخرى، هذه العلاقة تسير في اتجاه واحد فقط، وتُعرف بشرط اتساق الساعة : إذا سبق حدث ما حدثا آخر، فإن الساعة المنطقية لذلك الحدث تسبق ساعة الحدث الآخر. ويمكن تحقيق شرط اتساق القوي للساعة ، الذي يكون ثنائي الاتجاه (إذا فإن )، باستخدام تقنيات أخرى مثل الساعات المتجهة.
إضافةً إلى ذلك، ومع ذلك، يمكن استخدام الطوابع الزمنية Lamport لإنشاء ترتيب كلي للأحداث في نظام موزع من خلال آلية عشوائية لكسر التعادلات (مثل معرف العملية). لكن التحذير هو أن هذا الترتيب اصطناعي ولا يمكن الاعتماد عليه للدلالة على وجود علاقة سببية.
علاوةً على ذلك، وعند استخدام ساعة لامبورت البسيطة فقط، لا يمكن استنتاج سوى ترتيب سببي جزئي من الساعة.
كذلك، طريقة أخرى للتعبير عن ذلك هي أن وهي تعني أن قد يكون قد حدث قَبل أو لا يمكن مقارنته بـ في ترتيب "حث قبل"، ولكن لم يحدث بعد .
من جانب آخر، يمكن استخدام ساعة Lamport لإنشاء ترتيب جزئي للأحداث بين العمليات. وبوجود ساعة منطقية تتبع هذه القواعد، فإن العلاقة التالية تكون صحيحة: إذا فإن ، أين يعني "حدث من قبل" .
كذلك، ومع ذلك، من خلال المقابل المنطقي، فإن يُشير إلى أن .فمثلًا، إذا كان ثم فلا يمكن أن يكون حدث من قبل .
# الحدث معروف
الزمن = الزمن + 1؛
(الرسالة، الطابع الزمني) = استلام;
الوقت = الحد الأقصى (الطابع الزمني، الوقت) + 1؛
خوارزمية
تتبع الخوارزمية بعض القواعد البسيطة:
في الكود الزائف ، خوارزمية الإرسال هي:
في هذا الإطار، عندما ترسل عملية رسالة، فإنها تتضمن قيمة العداد الخاصة بها مع الرسالة بعد تنفيذ الخطوة 1؛
في هذا الإطار، عند استلام رسالة، يتم تحديث عداد المستلم، إذا لزم الأمر، إلى الرقم الأكبر من عداده الحالي وعلامة الوقت في الرسالة المستلمة. يتم فيما بعد زيادة العداد بمقدار 1 قبل اعتبار الرسالة مستلمة.
وفي هذا الصدد، تزيد العملية من عدادها قبل كل حدث محلي (مثلًا، حدث إرسال رسالة)؛
بدائل للسببية المحتملة
- انظر كذلك
- ساعة المصفوفة
- ساعة متجهة
- ناقل الإصدار
من جهة ثانية، الفكرة الأكبر هي مفهوم دلالات التطبيق، أي تصميم الأنظمة الموزعة استنادًا إلى محتوى الرسائل، وهي فكرة متضمنة في مبدأ النهاية إلى النهاية . الأساليب الحالية تتجاهل إلى حد كبير الدلالات وتركز على تقديم خدمات اتصال تضمن تسليم الرسائل وترتيبها بشكل غير متعلق بالتطبيق ("النحوي") وهنا تبرز أهمية أفكار مثل السببية المحتملة. ولكن إذا كان لدينا طريقة مناسبة لإجراء دلالات التطبيق، فلن نحتاج إلى مثل هذه الخدمات الاتصالية. إن خدمة الاتصالات غير المنظمة وغير الموثوقة ستكون كافية. القيمة الحقيقية لنهج بروتوكولات المعلومات تكمن في أنها توفر الأساس لنهج دلالات التطبيق.
علاوةً على ذلك، علاقة "حدث قبل" تلتقط السببية المحتملة، وليس السببية الحقيقية. في عام 2011-2012، اقترح مونيندار سينغ منهجًا تصريحيًا متعدد الوكلاء يعتمد على السببية الحقيقية يسمى بروتوكولات المعلومات. يحدد بروتوكول المعلومات القيود المفروضة على الاتصالات بين الوكلاء الذين يشكلون نظامًا موزعًا. ومع ذلك، بدلاً من تحديد ترتيب الرسائل (مثلًا، عبر آلة الحالات، وهي طريقة شائعة لتمثيل البروتوكولات في الحوسبة)، يحدد بروتوكول المعلومات تبعيات المعلومات بين الاتصالات التي قد يرسلها الوكلاء (نقاط نهاية البروتوكول). يمكن للوكيل إرسال اتصال في حالة محلية (تاريخه الاتصالي) فقط إذا كانت الرسالة والحالة معًا تلبيان تبعيات المعلومات ذات الصلة. مثلًا، قد يحدد بروتوكول معلومات لتطبيق تجارة إلكترونية أنه لإرسال عرض سعر يحتوي على معرّف ID (المُوَحِّد) وعنصر وسعر، يجب أن يعرف البائع بالفعل معرف العنصر من حالته ولكن يمكنه إنشاء أي سعر يريده. الأمر المثير للدهشة في بروتوكولات المعلومات هو أنه على الرغم من أن الانبعاثات مقيدة، فإن الاستقبالات ليست كذلك. على وجه التحديد، قد يتلقى الوكلاء الاتصالات بأي ترتيب كان - فالاستقبالات ببساطة تحمل المعلومات وليس هناك معنى لتأخيرها. وهذا يعني أنه يمكن تنفيذ بروتوكولات المعلومات عبر خدمات الاتصال غير المنظمة مثل UDP .
الاعتبارات
ولذلك فمن الضروري أن:
كذلك، في بيئة متعددة العمليات أو متعددة الخيوط، قد يكون من الضروري إرفاق معرف العملية (PID) أو أي معرف فريد آخر بطابع الوقت حتى يكون من الممكن التمييز بين الأحداث و والتي قد تحدث في وقت واحد في عمليات مختلفة.
وفي هذا الصدد، بالنسبة لكل حدثين مختلفين و يحدثان في نفس العملية، وباعتبار هو الطابع الزمني لحدث معين ، من الضروري أن لا يكون مساويًا لـ .
من جهة ثانية، يتم ضبط الساعة المنطقية بحيث يكون هناك حد أدنى من "دقات" الساعة (زيادة العداد) بين الأحداث و ؛
ساعة لامبورت المنطقية في الأنظمة الموزعة
وفي هذا السياق، في نظام موزع، لا يمكن عمليًا مزامنة الوقت بين الكيانات (والتي تُعتبر عادةً عمليات) داخل النظام؛ وبالتالي، يمكن للكيانات استخدام مفهوم الساعة المنطقية استنادًا إلى الأحداث التي تتواصل من خلالها.
وعلى صعيد آخر، لاحظ أنه بِاستخدام ساعات لامبورت، لا يمكن قول أي شيء عَن الوقت الفعلي للحدثين و . إذا قالت الساعة المَنطِقية إن فَهذا لا يَعني فِي الواقع أن حدث فعلياً قبل من حيث الوقت الحقيقي.
وفي السياق ذاته، تُظهر ساعات لامبورت غياب السببية، لكنها لا تلتقط جميع العلاقات السببية. فمعرفة أن و تظهر أن لم يتسبب في أو لكن لا يمكننا تحديد أي منهما بدأ .
ومن جهة أخرى، إذا لم تتبادل كيانان أي رسائل، فغالبًا لا يحتاجان إلى مشاركة ساعة مشتركة؛ وتسمى الأحداث التي تحدث على هذه الكيانات بالأحداث المتزامنة.
كذلك، يُقال إن النظام الموزع يحتوي على ترتيب جزئي بين الأحداث في النظام. وإذا أمكن تحديد "الكل"، أي العلاقة السببية بين جميع الأحداث في النظام، فيقال أن النظام يتمتع بالنظام الكلي.
وفي السياق ذاته، يمكن أن يكون هذا النوع من المعلومات مهمًا عند محاولة إعادة تشغيل الأحداث في نظام موزع (مثل محاولة الاستعادة بعد تعطل). فإذا تعطل أحد العقد، وكنا نعرف العلاقات السببية بين الرسائل، يمكننا إعادة تشغيل تلك الرسائل واحترام العلاقة السببية لإعادة تلك العقدة إلى الحالة التي تحتاجها.
من جهة ثانية، عندما يتواصل كيانان عبر تمرير الرسائل، يُقال إن حدث الإرسال يحدث قبل حدث الاستلام، ويمكن الترتيب المنطقي بين الأحداث.
من جانب آخر، من بين العمليات على نفس الجهاز المحلي، يمكننا ترتيب الأحداث استنادًا إلى الساعة المحلية للنظام.
من جهة ثانية، لا يمكن لكيان واحد أن تحدث فيه حدثان في الوقت نفسه. إذا كان النظام يحتوي على ترتيب كلي، فيمكننا تحديد الترتيب بين جميع الأحداث في النظام. أما إذا كان النظام يحتوي على ترتيب جزئي بين العمليات، وهو نوع الترتيب الذي توفره ساعة لامبورت المنطقية، فإنه يمكننا فقط تحديد الترتيب بين الكيانات التي تتفاعل مع بعضها. وقد تناول لامبورت مسألة ترتيب حدثين لهما نفس الطابع الزمني (أو العداد)، حيث قال: "لكسر التعادلات، نستعمل أي ترتيب إجمالي تعسفي "من العمليات." وبالتالي، قد تكون هناك طوابع زمنية أو عدادات متساوية داخل نظام موزع، ولكن عند تطبيق خوارزمية الساعات المنطقية، فإن الأحداث التي تحدث ستحافظ دائمًا على ترتيب جزئي صارم على الأقل.
وعلى صعيد آخر، تؤدي ساعات لامبورت إلى حالة حيث يتم فيها ترتيب جميع الأحداث في نظام موزع ترتيبًا كليًا. أي أنه إذا ، فيمكننا أن نقول حدث بالفعل من قبل .
# يحدث الحدث
إرسال(الرسالة، الوقت)؛
الخوارزمية لاستقبال الرسالة هي:
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟