Berkeley algoritması - Berkeley algorithm

Berkeley algoritması bir yöntemdir saat senkronizasyonu içinde dağıtılmış hesaplama hiçbir makinenin doğru bir zaman kaynağına sahip olmadığını varsayar. Gusella ve Zatti tarafından California Üniversitesi, Berkeley'de 1989 yılında geliştirilmiştir.^[1] Sevmek Cristian'ın algoritması içinde kullanılmak üzere tasarlanmıştır intranetler.

Algoritma

Aksine Cristian'ın algoritması, Berkeley algoritmasındaki sunucu işlemi Önder, periyodik olarak diğer anketler takipçi süreçler. Genel olarak, algoritma şu şekildedir:

1. Bir Önder bir aracılığıyla seçilir seçim süreci gibi Chang ve Roberts algoritması.
2. Önder anketler takipçiler zamanlarıyla benzer şekilde cevap veren Cristian'ın algoritması.
3. Önder gözlemler gidiş-dönüş süresi (RTT) mesajların ve her birinin zamanını tahmin eder takipçi ve kendi.
4. Önder daha sonra diğerlerinin değerlerinin çok dışında aldığı değerleri göz ardı ederek saat zamanlarının ortalamasını alır.
5. Güncellenen şimdiki zamanı diğer sürece geri göndermek yerine, Önder daha sonra her birinin sahip olduğu miktarı (pozitif veya negatif) gönderir takipçi saatini ayarlamalıdır. Bu, RTT'ye bağlı olarak daha fazla belirsizliği önler. takipçi süreçler.

Bu yöntemle ortalama, bireysel saatin kayma eğilimini ortadan kaldırır. Gusella ve Zatti, protokolleri kullanılarak saatleri yaklaşık 20-25 milisaniye içinde senkronize edilen 15 bilgisayarı içeren sonuçlar yayınladı.

Bilgisayar sistemleri normalde, liderden olumsuz bir saat değişikliği aldıklarında saatlerini geri almaktan kaçınırlar. Bunu yapmak, sistemin kendisindeki belirli algoritmalarda veya aşağıdaki gibi programlarda temel bir varsayım olan monoton zaman özelliğini kıracaktır. Yapmak. Bu sorunun basit bir çözümü, lider tarafından belirlenen süre boyunca saati durdurmaktır, ancak bu basit çözüm, daha az ciddi olmasına rağmen sorunlara da neden olabilir. Küçük düzeltmeler için çoğu sistem, düzeltmeyi daha uzun bir süre boyunca uygulayarak saati yavaşlatır ("saat dönüşü" olarak bilinir).

Çoğunlukla, saati belirli bir toleransın dışındaki bir değere göre değişen herhangi bir müşteri, sonuçların ortalamasını alırken göz ardı edilir. Bu, bir hatalı saat nedeniyle genel sistem zamanının büyük ölçüde çarpıtılmasını önler.

Referanslar