Zamanlama ve Hata Modelleri
Zamanlama ve hata modelleri, dağıtık bir algoritmanın mesaj gecikmeleri ve işlemci hızları hakkında ne gibi varsayımlarda bulunabileceğini ve bileşenlerin nasıl arızalanmasına izin verildiğini belirtmektedir.
Tanım
Bir zamanlama modeli, mesaj teslim süresi ve göreceli süreç hızı üzerindeki üst sınırlarla ilgili varsayımları belirlerken, bir hata modeli ise süreçlerin ve kanalların belirtilen davranışlarından sapabileceği yöntemler kümesini sabitlemektedir.
Kapsam
Bu konu, senkron, asenkron ve kısmen senkron zamanlama modellerini; çökme (fail-stop) hatalarından atlama (omission) ve zamanlama hatalarına, hatta keyfi (Bizans) hatalara kadar uzanan hata taksonomisini; ve asenkron sistemler ile zaman aşımı tabanlı akıl yürütme arasında köprü kuran hata dedektörlerinin soyutlamasını kapsamaktadır. Bu modeller, hem olasılık hem de imkansızlık sonuçlarının türetildiği aksiyomları oluşturmaktadır.
Temel sorular
- Bir algoritma gecikme ve hız konusunda hangi sınırlamalara sahip olabilir ve zaman aşımları bunlara nasıl bağlıdır?
- Bir protokol, çökme, atlama, zamanlama, Bizans gibi hangi hata sınıflarını maskelemelidir?
- Asenkron sistemler, imkansızlık sonuçlarını aşmak için hata dedektörleri ile nasıl güçlendirilebilir?
Temel kuramlar
- Kısmi senkronizasyon
- Gerçek sistemler ne tamamen senkron ne de tamamen asenkrondur; kısmen senkron model, gecikme ve hız üzerinde nihayetinde geçerli olan veya bilinmeyen sınırlamalar varsaymaktadır ki bu, gerçekçi kalırken konsensüsü çözmek için yeterlidir.
- Hata modeli hiyerarşisi
- Hatalar, iyi huylu fail-stop çökmelerinden, gönderme/alma atlamalarına ve zamanlama ihlallerine, hatta keyfi Bizans davranışlarına kadar çeşitlilik göstermektedir. Bir protokolün tolere etmesi gereken hataların ciddiyeti, gerekli replikasyon faktörünü ve mesaj karmaşıklığını belirlemektedir.
- Güvenilmez hata dedektörleri
- Soyut bir hata dedektörü, hangi süreçlerin çöktüğüne dair muhtemelen yanlış ipuçları sağlamaktadır. Konsensüsü çözmek için yeterli olan en zayıf dedektörü karakterize etmek, asenkron titizliği pratik zaman aşımı tabanlı uygulamalarla uzlaştırmaktadır.
Klinik önem
Üretim sistemleri, zaman aşımlarını ayarlarken, bir replikasyon faktörü seçerken veya kötü niyetli katılımcılara karşı savunma yapıp yapmayacaklarına karar verirken zımnen bir zamanlama ve hata modeli seçmektedir. Bu varsayımların yanlış yapılması, split-brain ve veri kaybı olaylarının yaygın bir temel nedeni olarak görülmektedir.
Tarihçe
Asenkron modelin hataya dayanıklı konsensüs için çok zayıf olduğu gösterildikten sonra, Dwork, Lynch ve Stockmeyer 1988'de kısmi senkronizasyonu tanıtmış, Chandra ve Toueg ise 1996'da güvenilmez hata dedektörlerini resmileştirmiştir. Bu çalışmalar, pratik hataya dayanıklı uzlaşmayı mümkün kılan modelleme araçlarını bir araya getirmiştir.
Tartışmalar
- Zaman aşımları bir zamanlama varsayımı mıdır yoksa bir hata dedektörü müdür?
- Bir görüş, zaman aşımlarını (nihai) bir senkronizasyon sınırını kodlayan bir unsur olarak ele alırken; diğer bir görüş ise bunları soyut bir hata dedektörünün bir uygulaması olarak değerlendirmektedir. Bu iki çerçeve büyük ölçüde eşdeğer olmakla birlikte, ağ modeli ile algoritma arasındaki farklı tasarım sınırlarını vurgulamaktadır.
Öne çıkan isimler
- Cynthia Dwork
- Nancy Lynch
- Larry Stockmeyer
- Tushar Chandra
- Sam Toueg
İlgili konular
Temel eserler
- dwork1988
- chandra1996
- lynch1996
Sıkça sorulan sorular
- Tamamen asenkron bir sistemde neden güvenilir hata tespiti uygulanamaz?
- Mesaj gecikmesi üzerinde sınırlamalar olmaksızın, keyfi olarak yavaş ancak çalışan bir süreç, çökmüş bir süreçten ayırt edilemez; bu nedenle herhangi bir dedektör bazen yanlış bilgi vermek durumunda kalmaktadır. Asenkron sistemlerin zamanlama varsayımları veya güvenilmez dedektörlerle güçlendirilmesinin nedeni budur.