Bizans Generalleri Sorunu'nu bir makalede anlayın
Yazar | Yu Liebing tarafından düzenlendi | Yapımcı Carol | Blockchain Camp (ID: blockchain_camp) The Byzantine Generals Problem (The Byzantine Generals Problem), ilk olarak Leslie Lamport ve diğerleri tarafından 1982'de ortaya konan dağıtılmış fikir birliği sorununun bağlamsal bir tanımını sağlar. Yayınlanan. "Bizans Generalleri Problemi" makalesi ayrıca Bizans Generalleri Problemini çözmek için iki algoritma sağlar:
- Sözlü mesajla çözüm;
- İmzalı mesaj ile bir çözüm.
kağıt:
https://www-inst.eecs.berkeley.edu/~cs162/sp16/static/readings/Original_Byzantine.pdf
Bu iki algoritma, bu makalenin ilerleyen bölümlerinde ayrıntılı olarak açıklanacaktır. Aslında Bizans Generalleri sorunu, dağıtılmış sistemler alanındaki en karmaşık hataya dayanıklı modeldir ve kötü niyetli davranışlar (mesaj kurcalama veya sahtecilik gibi) varlığında dağıtılmış sistemlerin nasıl anlaşmaya varacağını açıklar. Dağıtılmış fikir birliği protokollerini ve algoritmalarını anlamamız için önemli bir temel oluşturur.
Bizans Generalleri Sorununun Tanımı
Bizans Generali Sorunu böyle bir senaryoyu şöyle anlatır:
Şekil 1. Bizans generalleri sorunu
Bizans İmparatorluğu ordusunun çeşitli tümenleri düşman şehrin dışında konuşlandırılmıştı ve her birliğe kendi generali tarafından komuta ediliyordu. Generaller birbirleriyle ancak haberciler aracılığıyla iletişim kurabilirler. Düşmanın durumunu gözlemledikten sonra, aşağıdakiler gibi ortak bir eylem planı geliştirmeleri gerekir: Saldırı (Saldırı) veya geri çekilme (Geri çekilme) Ve zafer, ancak generallerin yarısından fazlası ortaklaşa bir saldırı başlattığında elde edilebilir. Bununla birlikte, bu generallerden bazıları, sadık generallerin fikir birliğine varan bir eylem planına ulaşmasını engellemeye çalışan hain olabilir. Daha da kötüsü, mesaj dağıtımından sorumlu haberci de bir hain olabilir, mesajı tahrif edebilir veya taklit edebilir veya mesajın kaybolmasına neden olabilirler.
Bizans genel sorununu daha derinlemesine anlamak için, Üç general sorunu Örnek olarak al. Üç general sadık olduğunda, tutarlı bir hareket tarzını belirlemek için oy kullanabilirler. Şekil 2, General A, B'nin düşmanın askeri durumunu gözlemleyerek ve kendi durumuna göre değerlendirerek ve General C'nin düşmanı gözlemleyerek bir saldırı başlatabileceği bir senaryoyu göstermektedir. Askeri durum ve kendi durumu geri çekilmek için yargılanmalıdır. Sonunda, üç general saldırıya oy verdi: geri çekilme = 2: 1, böylece kazanmak için birlikte saldıracaklar. Üç general için, her general iki karar verebilir (hücum veya geri çekilme), 6 farklı senaryo vardır, Şekil 2 bunlardan biridir, diğer 5 senaryo için basitçe itebilirsiniz. Her üç generalin de bir eylem planı üzerinde anlaşması yönünde oylama.
Şekil 2. Üç generalin de sadık olduğu bir sahne
Üç general arasında bir hain olması normal savaş planını bozabilir. Şekil 3, General C'nin hain olduğu bir senaryoyu göstermektedir, General A ve General B'ye farklı mesajlar göndermektedir. Bu senaryoda, General A, oylama ile saldırıya uğrar: geri çekilme = 1: 2 ve sonunda geri çekilecektir. Plan; General B, saldırıyı oylama ile alır: geri çekilme = 2: 1 ve sonunda saldırgan bir eylem planı yapacaktır. Sonuç olarak, yalnızca General B bir saldırı başlattı ve yenildi.
Şekil 3. İki sadakat ve bir isyan sahnesi
Aslında, üç general arasında bir hainin olduğu bir sahne için, her zaman tutarlı bir hareket tarzı elde etmek imkansızdır. Ayrıntılı kanıt Leslie Lamport'un makalesinde bulunabilir. Ek olarak, makale daha genel bir sonuç veriyor: Eğer çok sayıda hain varsa, sonunda tutarlı bir eylem planına ulaşmak için en az 3 milyon + 1 general gerekiyor.
çözüm
Leslie Lamport, makaledeki Bizans Generalleri sorununa sözlü mesajla çözüm ve imzalı mesajla çözüm olmak üzere iki çözüm sundu.
1. Sözlü mesajlaşma çözümü
Öncelikle Sözlü mesajın tanımı şöyledir:
- A1. Gönderilen tüm mesajlar doğru bir şekilde iletilecektir;
- A2. Mesajın alıcısı mesajı kimin gönderdiğini bilir;
- A3 Mesajın yokluğu tespit edilebilir.
Sözlü mesajların tanımına dayanarak, sözlü mesajların tahrif edilemeyeceğini, ancak taklit edilebileceğini bilebiliriz. Şekil 3'teki sahnenin türetilmesine dayanarak, bir hain olduğunda, nihai tutarlı eylemi gerçekleştirmek için üç sadık generalin daha eklenmesi gerektiğini biliyoruz. Anlayışımızı derinleştirmek için, 3 sadık general ve 1 hain senaryosunu ağızdan mesaj çözümünü türetmek için kullanacağız. Mesaja dayalı bir çözümde, mesajı ilk gönderen general komutan, geri kalan generallere teğmen denir. 3 sadakat ve 1 isyan senaryosu için, iki tur muharebe bilgi müzakeresi gereklidir.Hiç savaş bilgisi alınmazsa, varsayılan olarak geri çekilecektir. Şekil 4, komutanın sadık bir general olduğu bir senaryodur. Muharebe bilgi müzakeresinin ilk turunda, komutan üç teğmene saldırgan bir mesaj gönderdi; ikinci turda, üç teğmen savaş bilgilerini tekrar görüştüler çünkü General A B sadık bir general, bu yüzden komutanın mesajına dayanarak diğer iki yardımcıya saldırgan bir mesaj gönderdiler ve General C bir haindi, savaş planını bozmak için diğer iki yardımcıya geri çekilme mesajı gönderdi. Sonunda, Komutan General, General A ve B, üzerinde anlaşılan bir saldırı planına ulaştı ve kazanabildi.
Şekil 4. Komutan sadık bir generaldir
Şekil 5, komutanın hain olduğu bir senaryodur .. Muharebe bilgi müzakeresinin ilk turunda, komutan General A ve B'ye bir geri çekilme mesajı gönderdi, ancak General C'nin kararını bozmak için bir saldırı mesajı gönderdi. İkinci turda, tüm yardımcılar sadık generaller olduğundan, komutandan gelen mesajlar kalan iki yardımcıya doğru bir şekilde gönderilir. Sonunda, tüm sadık generaller bir geri çekilme planı üzerinde anlaşabilir.
Şekil 5. Komutanın hain olduğu bir sahne
Yukarıda bahsedildiği gibi, Bizans genel sözlü mesaj türü sorunu ile ilgili olarak, asi generallerin sayısı m ve general sayısı 3 milyon + 1'den az değilse, nihayetinde bir uzlaşı eylem planına varılabilir. Bu algoritmada, hainlerin sayısının bilindiğini ve hainlerin sayısının yineleme sayısını belirlediğini, yani hainlerin sayısının, savaş bilgi müzakeresi turlarının sayısını belirlediğini belirtmek gerekir. M varsa Asi generallerin m + 1 tur muharebe bilgi müzakeresi yürütmesi gerekiyor. Bir hain olduğunda iki tur savaş bilgisi müzakeresinin gerekli olmasının nedeni de budur.
2. İmza mesajı çözümü
Benzer şekilde, imzalı bir mesajın tanımı, aşağıdaki iki öğenin eklenmesiyle bir mesajın tanımına dayanır:
- A4. Sadık generalin imzası taklit edilemez ve imza mesajının içeriğindeki herhangi bir değişiklik keşfedilecektir;
- A5. Generalin imzasının gerçekliğini herkes doğrulayabilir.
İmzalı mesajların tanımına bağlı olarak, imzalı mesajların taklit edilemeyeceğini veya değiştirilemeyeceğini bilebiliriz. İmza mesajı çözümünü derinlemesine anlamak için, türetilecek bir örnek olarak 3. genel problemi de alıyoruz. Şekil 6, sadık generallerin muharebe müzakerelerinin başlatılmasına öncülük ettiği sahnedir.General A, General B ve C'ye saldırgan mesajlar göndermek için başı çekti. General C, General A'nın mesajını değiştirdiğinde, General B, savaş bilgilerinin General C tarafından tahrif edildiğini görecekti. , General B, General A tarafından gönderilen mesajı yürütecektir.
Şekil 6. Sadık generaller, savaş müzakerelerinin başlatılmasında başı çekiyor
Şekil 7, asi generallerin muharebe müzakerelerinin başlatılmasında başı çektiği senaryodur. Asi general C ilk önce yanıltıcı muharebe bilgileri gönderdi.Daha sonra General A ve B, General C tarafından gönderilen muharebe bilgilerinin tutarsız olduğunu bulacak ve bu yüzden asi generaller olarak yargılanacaklardı. İşlenebilir ve ardından muharebe bilgileri üzerinde müzakere edilebilir.
Şekil 7. Muharebe müzakerelerini ilk başlatanlar asilerdir
İmza mesajı çözümü, herhangi bir sayıda yeniden gönderme senaryosunu işleyebilir.
sonuç olarak
Dağıtık sistemler alanında Bizans Generali Probleminin rolü ile bilgisayar dünyası arasındaki ilişki şu şekildedir:
- Bilgisayar düğümüne karşılık gelen genel;
- İyi işleyen bilgisayar düğümlerine karşılık gelen sadık generaller;
- Asi generaller, yasadışı olarak kontrol edilen bilgisayar düğümleri;
- Haberci öldürüldü ve iletişim hatası mesajın kaybolmasına neden oldu;
- Haberciler casuslarla değiştirilir, iletişim saldırıya uğrar, saldırganlar bilgileri kurcalar veya taklit eder.
Yukarıda bahsedildiği gibi, Bizans Generalleri Problemi, dağıtılmış fikir birliği sorununun bağlamsal bir tanımını sağlar ve dağıtılmış sistemler alanındaki en karmaşık modeldir. Ayrıca, mevcut birçok dağıtılmış konsensüs protokolünü ve algoritmasını anlamamız ve sınıflandırmamız için bir çerçeve sağlar. Mevcut dağıtılmış konsensüs protokolleri ve algoritmaları temel olarak iki kategoriye ayrılabilir:
Biri, hata toleransı algoritmasıdır Bizans dışı hata toleranslı algoritma olan (Crash Fault Tolerance, CFT), dağıtılmış sistemde hataların olduğu ancak kötü niyetli saldırının olmadığı senaryoda mutabakat problemini çözer. Diğer bir deyişle, bu senaryoda mesaj kaybı ve mesaj tekrarlaması olabilir, ancak mesajların tahrif edildiği veya sahtesinin yapıldığı bir senaryo yoktur. Genellikle dağıtılmış veritabanları gibi yerel alan ağı senaryolarında dağıtılmış sistemlerde kullanılır. Bu kategoriye giren yaygın algoritmalar arasında Paxos algoritması, Raft algoritması ve ZAB protokolü bulunur.
Bir Bizans hataya dayanıklı algoritması, Dağıtık bir sistemde fikir birliği sorununu hem arızalar hem de kötü niyetli saldırı senaryoları ile çözebilir. Genellikle dijital para biriminin blok zinciri teknolojisi gibi İnternet senaryolarında dağıtılmış sistemlerde kullanılır. Bu kategorideki yaygın algoritmalar arasında PBFT algoritması ve PoW algoritması bulunur.
Bu makaleyi okuduktan sonra, bu iki çözüm hakkında ne düşünüyorsunuz? Yorumlar bölümünde bizimle görüşmeye hoş geldiniz!
