ساعة المتجه

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

نرمز إلى VC_i بساعة المتجهة التي تحتفظ بها العملية i ، و تتم تحديثات الساعة على النحو التالي: 
تصغير| مثال على نظام الساعات المتجهة. الأحداث في المنطقة الزرقاء هي الأسباب المؤدية إلى الحدث B4، في حين أن الأحداث في المنطقة الحمراء هي تأثيرات الحدث B4.

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

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

## خاصية الترتيب الجزئي
تسمح ساعات المتجه بالترتيب السببي الجزئي للأحداث. تعريف ما يلي:

* VC(x) يشير إلى ساعة متجهة للحدث x ، و VC(x)_z يشير إلى مكون تلك الساعة للعملية z .
* VC(x) 
** باللغة الإنجليزية: VC(x) أقل من VC(y) ، إذا وفقط إذا VC(x)_z أقل من أو يساوي VC(y)_z لجميع مؤشرات العملية z ، وعلى الأقل واحدة من تلك العلاقات أصغر تمامًا (أي، VC(x)_{z'}  ).
* x \to y\; يدل على هذا الحدث x حدث قبل الحدث y . يتم تعريفه على النحو التالي: إذا x \to y\; ، ثم VC(x) 

* عدم التماثل : إذا VC(a)  ، ثم ¬ (VC(b) 
* الانتقالية : إذا VC(a)  و VC(b)  ، ثم VC(a)  ؛ أو إذا a \to b\; و b \to c\; ، ثم a \to c\;

العلاقة مع الطلبات الأخرى:

* يترك RT(x) كن الوقت الحقيقي عندما حدث x يحدث. لو VC(a)  ، ثم RT(a) 
* يترك C(x) كن طابعًا زمنيًا لحدث لامبورت x . لو VC(a)  ، ثم C(a) 

## آليات أخرى

* في عام 1999، قام توريس روخاس وأحمد بتطوير **الساعات المعقولة** ،  وهي آلية تشغل مساحة أقل من الساعات المتجهة ولكنها في بعض الحالات سوف تنظم الأحداث المتزامنة سببيًا بشكل كامل.

* في عام 2005، أنشأ أجراوال وجارج **Chain Clocks** ،  وهو نظام يتتبع التبعيات باستخدام متجهات ذات حجم أصغر من عدد العمليات ويتكيف تلقائيًا مع الأنظمة ذات العدد الديناميكي من العمليات.
* في عام 2008، قدم ألميدا *وآخرون* **ساعات الشجرة الفاصلة** .    تعمل هذه الآلية على تعميم ساعات المتجهات وتسمح بالعمل في بيئات ديناميكية عندما لا تكون الهويات وعدد العمليات في الحساب معروفة مسبقًا.

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

## انظر أيضًا

* طوابع زمنية لامبورت
* ساعات المصفوفة
* ناقل الإصدار

## المراجع


## الروابط الخارجية

* لماذا الساعات المنطقية سهلة (مقارنة بين التواريخ السببية والساعات المتجهة ومتجهات الإصدار)
* شرح الساعات المتجهة
* تنفيذ ساعة متجهية تعتمد على الطابع الزمني في إرلانج
* تنفيذ ساعة المتجهات في Objective-C
* تنفيذ ساعة المتجهات في إرلانج
* لماذا تعتبر ساعات المتجهات صعبة؟
* لماذا لا تحتاج كاساندرا إلى ساعات متجهة

تصنيف:خوارزميات
تصنيف:هياكل بيانات رسوميات الحاسوب
تصنيف:اتصالات