Dağıtık Uzlaşma
Dağıtık uzlaşma, mesaj gecikmelerine ve süreç hatalarına rağmen bir dizi sürecin tek bir değer üzerinde anlaşmasını sağlama sorunudur ve hata toleranslı bilişimin temel soyutlamasını oluşturmaktadır.
Tanım
Uzlaşma, her hatasız sürecin, önerilen bir girdiden başlayarak, sonunda bir çıktı değerine karar vermesini gerektirir; öyle ki tüm hatasız süreçler aynı değere karar verir (anlaşma), değer bir süreç tarafından önerilmiştir (geçerlilik) ve her hatasız süreç sonunda bir karara varır (sonlandırma).
Kapsam
Bu konu, uzlaşmanın resmi spesifikasyonunu (anlaşma, geçerlilik, bütünlük ve sonlandırma), FLP imkansızlık teoremini ve bunun etrafından dolaşma yollarını—kısmi senkronizasyon, güvenilmez hata dedektörleri ve rastgeleleştirme—ve uzlaşmanın atomik yayın ile çoğaltılmış durum makineleri ile eşdeğerliğini kapsamaktadır. Çökme-hatası (crash-failure) ortamını ele almaktadır; Bizans (Byzantine) ortamı ise ilgili başka bir konuda incelenmektedir.
Temel sorular
- Bir protokolün doğru bir uzlaşma algoritması olabilmesi için tam olarak neyi garanti etmesi gerekmektedir?
- Tek bir çökme durumunda bile deterministik asenkron uzlaşma neden imkansızdır?
- Hangi ek varsayımlar—senkronizasyon, hata dedektörleri, rastgelelik—çözülebilirliği geri kazandırmaktadır?
Temel kuramlar
- FLP imkansızlığı
- Asenkron mesajlaşma sistemlerinde, tek bir süreç bile çökebilirse, hiçbir deterministik protokol uzlaşmayı çözemez; çünkü her protokolün, bir karara varmadan sonsuza kadar çalışmaya yönlendirilebilecek bir yürütmesi bulunmaktadır.
- Hata dedektörü yaklaşımı
- Asenkron bir sistemi, sonunda doğru hale gelen güvenilmez bir hata dedektörü ile güçlendirmek, uzlaşmanın çözülebilirliğini geri kazandırmaktadır ve yeterli olan en zayıf dedektör hassas bir şekilde karakterize edilmiştir.
- Rastgeleleştirilmiş uzlaşma
- Süreçlerin yazı tura atmasına izin vermek, tamamen asenkron bir sistemde bile uzlaşmanın olasılıkla bir (probability one) ile sonlanmasını sağlamaktadır; bu durum, FLP engelinden kaçmak için deterministik sonlandırmayı olasılıksal sonlandırma ile değiştirmek anlamına gelmektedir.
Klinik önem
Her güçlü tutarlı dağıtık sistem—çoğaltılmış günlükler, koordinasyon hizmetleri, yapılandırma depoları—uzlaşmayı dahili olarak çözmektedir; bu nedenle burada belirlenen garantiler ve sınırlar, bu tür sistemlerin tutarlılık ve erişilebilirlik konusunda ne vaat edebileceğini doğrudan sınırlamaktadır.
Tarihçe
1985 FLP teoremi, temel imkansızlığı ortaya koymuştur; Ben-Or'un 1983 tarihli rastgeleleştirilmiş protokolü ve Chandra ile Toueg'in 1996 tarihli hata dedektörü çerçevesi ise uzlaşmayı çözülebilir kılmak için iki tamamlayıcı yol göstermiş ve sonraki on yılların araştırma gündemini belirlemiştir.
Öne çıkan isimler
- Michael Fischer
- Nancy Lynch
- Michael Paterson
- Tushar Chandra
- Sam Toueg
- Michael Ben-Or
İlgili konular
Temel eserler
- fischer1985
- chandra1996
- ben-or1983
Sıkça sorulan sorular
- Uzlaşma imkansızsa, gerçek sistemler bunu nasıl başarmaktadır?
- İmkansızlık, yalnızca tamamen asenkron bir modelde her zaman sonlanması gereken deterministik bir protokol için geçerlidir. Gerçek sistemler güvenliği koşulsuz tutar ve sonlandırma için nihai senkronizasyona veya rastgeleliğe dayanır; bu sayede anlaşmayı asla ihlal etmezler ve ağ düzgün çalıştığında ilerleme kaydederler.