Konsensüs ve Koordinasyon
Konsensüs ve koordinasyon, yalnızca mesajlarla iletişim kuran bağımsız süreçlerin, gecikmelere ve arızalara rağmen ortak bir değer veya eylem üzerinde nasıl anlaşabileceği sorununu ele almaktadır.
Tanım
Konsensüs, her biri bir değer öneren bir dizi sürecin, bazı süreçler başarısız olsa bile, kararın geçerli olduğu, tüm doğru süreçlerin anlaştığı ve her doğru sürecin sonunda bir karara vardığı tek bir ortak değer üzerinde uzlaşması problemidir.
Kapsam
Bu alan, konsensüs problemini ve varyantlarını (anlaşma, atomik yayın, geçerlilik, sonlandırma), deterministik asenkron konsensüs için temel FLP imkansızlık sonucunu, Paxos ve Raft gibi pratik konsensüs protokollerini, Bizans hata toleranslı anlaşmayı ve karşılıklı dışlama ile lider seçimi gibi klasik koordinasyon problemlerini kapsamaktadır. Hata toleranslı dağıtık bilişimin teorik ve pratik çekirdeğini oluşturmaktadır.
Alt konular
Temel sorular
- Konsensüs hangi zamanlama ve hata modelleri altında çözülebilirdir ve ne zaman kanıtlanabilir şekilde imkansızdır?
- Pratik protokoller güvenliği korurken FLP imkansızlığını nasıl aşmaktadır?
- Çökme hatalarına kıyasla Bizans hatalarına tolerans göstermek için ne kadar çoğaltma gerekmektedir?
- Süreçler paylaşılan kaynaklara erişimi nasıl koordine edebilir veya güvenilir bir şekilde bir lider seçebilir?
Temel kuramlar
- FLP imkansızlığı
- Tamamen asenkron bir sistemde, tek bir süreç bile çökebilirse hiçbir deterministik protokol konsensüsü garanti edemez, çünkü yavaş bir süreç başarısız olandan ayırt edilemez; bu sonuç, kısmi senkronizasyonu, rastgeleleştirmeyi ve hata dedektörlerini motive etmektedir.
- Korum tabanlı konsensüs
- Paxos gibi protokoller, önerileri kabul etmek için örtüşen çoğunluklar (korumlar) gerektirerek anlaşmayı sağlamaktadır; bu da herhangi iki kararın doğru bir süreçte kesişmesini ve böylece turlar ve lider değişiklikleri boyunca tutarlı kalmasını güvence altına almaktadır.
- Bizans anlaşma sınırları
- f adede kadar sürecin keyfi davranabileceği durumlarda anlaşmaya varmak için, klasik senkron ayarda en az 3f+1 süreç gerekmektedir; bu, tüm Bizans hata toleranslı sistemlerin tasarımını şekillendiren sıkı bir sınırdır.
Klinik önem
Konsensüs, güvenilir altyapının omurgasını oluşturmaktadır: koordinasyon hizmetleri, çoğaltılmış veritabanları, dağıtık kilitler ve blok zincirleri, kopyaları tutarlı tutmak için bir konsensüs protokolü çalıştırmaktadır; bu da bu alanı modern bulut sistemlerinin dayanıklılık ve erişilebilirlik garantilerinden doğrudan sorumlu kılmaktadır.
Tarihçe
1982 tarihli Bizans generalleri makalesi ve 1985 tarihli FLP imkansızlık sonucu, anlaşmanın sınırlarını belirlemiştir; Lamport'un Paxos'u (1989'da dolaşıma girdi, 1998'de yayımland) pratik, asenkron-güvenli bir protokol sunmuş, Bizans hata toleransı ve Raft üzerine yapılan sonraki çalışmalar ise konsensüsü hem kötü niyetli hatalara karşı sağlam hem de uygulayıcılar için erişilebilir hale getirmiştir.
Tartışmalar
- FLP imkansızlığı konsensüsü pratikte ulaşılamaz mı kılmaktadır?
- FLP, tamamen asenkron bir modelde her zaman hem güvenli hem de canlı olan deterministik bir protokolü dışlamaktadır; ancak pratik sistemler, nihai senkronizasyon varsayarak veya rastgeleleştirmeyi kullanarak bunu aşmakta, güvenliği koşulsuz tutmakta ve ağ düzgün çalıştığında canlılığı sağlamaktadır.
Öne çıkan isimler
- Leslie Lamport
- Nancy Lynch
- Michael Fischer
- Michael Paterson
- Barbara Liskov
İlgili konular
Temel eserler
- fischer1985
- lamport1998
- lamport1982byz
Sıkça sorulan sorular
- Konsensüs neden dağıtık sistemlerdeki en zor problem olarak kabul edilmektedir?
- Çünkü atomik yayın, çoğaltılmış durum makineleri, dağıtık kilitleme gibi birçok diğer koordinasyon görevi konsensüse indirgenmektedir ve konsensüsün kendisi asenkron çökme-hata modelinde deterministik olarak çözülmesi kanıtlanabilir şekilde imkansızdır; bu nedenle herhangi bir çözüm dikkatli zamanlama veya rastgelelik varsayımları yapmalıdır.
- Konsensüs çoğaltılmış veritabanlarıyla nasıl ilişkilidir?
- Çoğaltılmış bir veritabanı, işlemlerin sırası üzerinde anlaşarak kopyalarını tutarlı tutmaktadır; bu da tam olarak bir konsensüs kararları dizisidir. Bu nedenle dağıtık anahtar-değer depoları gibi sistemler çekirdeklerinde bir konsensüs protokolü barındırmaktadır.