ساعة متجهة

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

تتم تحديثات الساعة على النحو التالي، ^{[ 1 ]} حيث${\displaystyle VC_{i}}$يشير إلى قيمة ساعة المتجه التي يحتفظ بها المعالج${\displaystyle i}$:

• في البداية، تكون جميع الساعات مضبوطة على الصفر.
• في كل مرة يتعرض فيها برنامج ما لحدث داخلي، فإنه يزيد عداده المنطقي في المتجه بمقدار واحد. على سبيل المثال، عند وقوع حدث في البرنامج${\displaystyle i}$يقوم بتحديثها${\displaystyle VC_{i}[i]\leftarrow VC_{i}[i]+1}$.
• في كل مرة ترسل فيها عملية ما رسالة، فإنها تزيد ساعتها المنطقية في المتجه بمقدار واحد (كما في النقطة أعلاه، ولكن ليس مرتين لنفس الحدث) ثم تقرن الرسالة بنسخة من متجهها الخاص وأخيرًا ترسل الزوج.
• في كل مرة يستقبل فيها برنامج ما زوجًا من ساعة متجه الرسالة، فإنه يزيد ساعته المنطقية في المتجه بمقدار واحد، ويُحدّث كل عنصر في متجهه بأخذ القيمة القصوى بين قيمة ساعة متجهه وقيمة المتجه في الزوج المُستلم (لكل عنصر). على سبيل المثال، إذا كان البرنامج${\displaystyle P_{i}}$يتلقى رسالة${\displaystyle (m,VC_{j})}$من${\displaystyle P_{j}}$، يقوم أولاً بزيادة ساعته المنطقية الخاصة في المتجه بمقدار واحد${\displaystyle VC_{i}[i]\leftarrow VC_{i}[i]+1}$ثم يقوم بتحديث متجهه بالكامل عن طريق تعيين${\displaystyle VC_{i}[k]\leftarrow \max(VC_{i}[k],VC_{j}[k]),\forall k}$.

ابتكر لامبورت فكرة ساعات لامبورت المنطقية عام ١٩٧٨. ^{[ ٢ ]} مع ذلك، كانت الساعات المنطقية في تلك الورقة البحثية كميات قياسية، وليست متجهات. وقد طُوِّر تعميمها إلى الزمن المتجه عدة مرات، على ما يبدو بشكل مستقل، من قِبَل مؤلفين مختلفين في أوائل ثمانينيات القرن العشرين. ^{[ ٣ ]} يحتوي ما لا يقل عن ست أوراق بحثية على هذا المفهوم. ^{[ ٤ ]} وتُعدّ أوراق كولين فيدج وفريدمان ماتيرن لعام ١٩٨٨ من الأوراق المرجعية الأساسية في مجال الساعات المتجهة ، ^{[ ٥ ] [ ٦ ]} حيث رسّخا (بشكل مستقل) مصطلح "الساعة المتجهة" والخصائص الرياضية للساعات المتجهة. ^{[ ٣ ]}

تسمح الساعات المتجهة بالترتيب السببي الجزئي للأحداث. وذلك بتحديد ما يلي:

• ${\displaystyle VC(x)}$يشير إلى ساعة متجه الحدث${\displaystyle x}$، و${\displaystyle VC(x)_{z}}$يشير إلى مكون تلك الساعة للعملية${\displaystyle z}$.
• ${\displaystyle VC(x)<VC(y)\iff \forall z[VC(x)_{z}\leq VC(y)_{z}]\land \exists z'[VC(x)_{z'}<VC(y)_{z'}]}$
  • باللغة الإنجليزية:${\displaystyle VC(x)}$أقل من${\displaystyle VC(y)}$، إذا وفقط إذا${\displaystyle VC(x)_{z}}$أقل من أو يساوي${\displaystyle VC(y)_{z}}$لجميع مؤشرات العمليات${\displaystyle z}$وواحدة على الأقل من تلك العلاقات أصغر حجماً (أي،${\displaystyle VC(x)_{z'}<VC(y)_{z'}}$).
• ${\displaystyle x\to y\;}$يشير إلى ذلك الحدث${\displaystyle x}$حدث قبل الحدث${\displaystyle y}$يُعرَّف على النحو التالي: إذا${\displaystyle x\to y\;}$، ثم${\displaystyle VC(x)<VC(y)}$

ملكيات:

• عدم التناظر : إذا${\displaystyle VC(a)<VC(b)}$ثم ¬${\displaystyle (VC(b)<VC(a))}$
• التعدي : إذا${\displaystyle VC(a)<VC(b)}$و${\displaystyle VC(b)<VC(c)}$، ثم${\displaystyle VC(a)<VC(c)}$أو إذا${\displaystyle a\to b\;}$و${\displaystyle b\to c\;}$، ثم${\displaystyle a\to c\;}$

• يترك${\displaystyle RT(x)}$كن في الوقت الحقيقي عند وقوع الحدث${\displaystyle x}$يحدث. إذا${\displaystyle VC(a)<VC(b)}$، ثم${\displaystyle RT(a)<RT(b)}$
• يترك${\displaystyle C(x)}$يكون الطابع الزمني لحدث لامبورت${\displaystyle x}$. لو${\displaystyle VC(a)<VC(b)}$، ثم${\displaystyle C(a)<C(b)}$

تستطيع الساعات المتجهة اكتشاف السببية بدقة في الأنظمة الموزعة المعرضة لأعطال مفاجئة. مع ذلك، عندما تتصرف العمليات بشكل عشوائي أو خبيث - كما هو الحال في نموذج الأعطال البيزنطية - يصبح اكتشاف السببية مستحيلاً بشكل أساسي ^{[ 7 ]} ، مما يجعل الساعات المتجهة غير فعالة في مثل هذه البيئات. تنطبق هذه النتيجة على جميع أنواع الساعات المتجهة، لأنها تنبع من قيود جوهرية متأصلة في مشكلة اكتشاف السببية في ظل الأعطال البيزنطية.

• في عام 1984، وصف وو وبرنشتاين تقنيةً مُشتقةً من ساعات المتجهات تُعرف باسم ساعات المصفوفة . ^{[ 8 ]} من خلال إنشاء مصفوفة حيث يُمثل كل صف ساعة متجه لنظير، يُمكن للعمليات تقدير الحد الأدنى من المعرفة التي تمتلكها جميع العُقد الأخرى. وهذا يسمح بحساب "حد أدنى" للتقدم العام، مما يُتيح حذف سجلات العمليات (جمع البيانات المهملة) بأمان في قواعد البيانات المُكررة.
• في عام 1999، قام توريس روخاس وأحمد بتطوير الساعات المعقولة ، ^{[ 9 ]} وهي آلية تشغل مساحة أقل من الساعات المتجهة ولكنها، في بعض الحالات، سترتب تمامًا الأحداث المتزامنة سببيًا.
• في عام 2005، ابتكر أغاروال وغارغ نظام Chain Clocks ، ^{[ 10 ]} وهو نظام يتتبع التبعيات باستخدام متجهات ذات حجم أصغر من عدد العمليات ويتكيف تلقائيًا مع الأنظمة ذات العدد الديناميكي من العمليات.
• في عام 2008، قدم ألميدا وآخرون ساعات شجرة الفاصل الزمني . ^{[ 11 ] [ 12 ] [ 13 ]} تعمم هذه الآلية ساعات المتجهات وتسمح بالتشغيل في البيئات الديناميكية عندما لا تكون هويات وعدد العمليات في الحساب معروفة مسبقًا.
• في عام ٢٠١٩، اقترح لوم راماباجا ساعات بلوم ، وهي بنية بيانات احتمالية تعتمد على مرشحات بلوم . ^{[ ١٤ ] [ ١٥ ] [ ١٦ ]} بالمقارنة مع ساعة المتجهات، فإن المساحة المستخدمة لكل عقدة ثابتة ولا تعتمد على عدد العقد في النظام. عند مقارنة ساعتين، إما أن ينتج عن ذلك نتيجة سلبية صحيحة (أي أن الساعتين غير قابلتين للمقارنة)، أو اقتراح بأن إحدى الساعتين تسبق الأخرى، مع احتمال وجود نتيجة إيجابية خاطئة حيث لا توجد علاقة بين الساعتين. ينخفض ​​معدل النتائج الإيجابية الخاطئة مع زيادة سعة التخزين المتاحة.

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

• طابع زمني لامبورت
• ساعة المصفوفة
• نسخة متجهة

• لماذا تعتبر الساعات المنطقية سهلة (مقارنة بين التاريخ السببي، وساعات المتجهات، ومتجهات الإصدارات)
• تنفيذ ساعة متجهة تعتمد على الطابع الزمني في لغة إرلانج
• تنفيذ ساعة المتجهات في لغة Objective-C
• تنفيذ ساعة المتجهات في لغة إرلانج
• لماذا تُعدّ الساعات المتجهة سهلة ؟، برايان فينك، مدونة رياك، 29 يناير 2010
• لماذا تُعدّ الساعات المتجهة صعبة ؟، جاستن شيهي، مدونة رياك، 5 أبريل 2010
• لماذا لا تحتاج كاساندرا إلى ساعات متجهة