خوارزمية بيركلي

خوارزمية بيركلي هي طريقة لمزامنة الساعة في الحوسبة الموزعة ، تفترض عدم وجود مصدر زمني دقيق لأي جهاز. طُوّرت هذه الخوارزمية بواسطة جوسيلا وزاتي في جامعة كاليفورنيا، بيركلي عام ١٩٨٩. ^{[ ١ ]} ومثل خوارزمية كريستيان ، فهي مُصممة للاستخدام داخل الشبكات الداخلية (الإنترانت) .

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

1. يتم اختيار القائد من خلال عملية انتخابية مثل خوارزمية تشانغ وروبرتس .
2. يقوم القائد باستطلاع آراء الأتباع الذين يردون بوقتهم بطريقة مشابهة لخوارزمية كريستيان .
3. يراقب القائد وقت الرحلة ذهابًا وإيابًا ( RTT) للرسائل ويقدر وقت كل تابع ووقته الخاص.
4. ثم يقوم القائد بحساب متوسط ​​أوقات الساعة، متجاهلاً أي قيم يتلقاها خارج نطاق قيم الآخرين.
5. بدلاً من إرسال الوقت الحالي المُحدَّث إلى العملية الأخرى، يُرسل القائد مقدار التعديل (موجبًا أو سالبًا) الذي يجب على كل تابع تعديله في ساعته. وهذا يتجنب المزيد من عدم اليقين الناتج عن زمن الاستجابة (RTT) في عمليات التابعين .

بهذه الطريقة، يُلغي المتوسط ​​ميل الساعات الفردية للانحراف. وقد نشر جوسيلا وزاتي نتائج شملت 15 جهاز كمبيوتر تمت مزامنة ساعاتها في حدود 20-25 مللي ثانية باستخدام بروتوكولهما.

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

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