Problem bizantyjskich generałów - na czym polega i jak go rozwiązać?
Jest to zagadnienie, które obejmuje bardzo szeroki zakres dziedzin niezbędnych do opisania go. Pierwszą z nich jest teoria gier, która jest działem matematyki opisującym najbardziej optymalne rozwiązanie w przypadku pojawienia się konfliktu interesów. Kolejną dziedziną jest teoria rozproszonych systemów, która wykorzystuje mechanizm wieloagentowy. Jest on złożony z komunikujących się ze sobą podmiotów, które realizują wspólne cele. Ostatnią dziedziną jaka jest potrzebna by dogłębnie wyjaśnić to zagadnienie jest szyfrowanie kryptograficzne, czyli sposób przekazania informacji w sposób zabezpieczony przed dostępem osób trzecich.
Wprowadzenie do problemu
Wyobraźmy sobie wielką zrobotyzowaną fabrykę, której prace nadzorowane są 24 godziny na dobę przez złożone systemy informatyczne i nie może ona pozwolić sobie na przestoje. Projektantom takiego systemu będzie zależało więc, aby był on jak najmniej awaryjny. Żeby to osiągnąć zwielokrotniają oni urządzenia działające w punktach krytycznych systemów. Jeśli jeden z elementów zawiedzie, jego pracę przejmie inny co pozwoli na nieprzerwaną pracę fabryki. W takim przypadku zepsuty element będzie bardzo łatwo namierzyć i podjąć próbę naprawienia go. Jednak co w wypadku, gdy dany element nie przestanie pracować, a zacznie wysyłać błędne sygnały wskazujące na awarię? Jego funkcja zostanie przejęta przez inne urządzenie. Może ono wykorzystywać również potencjalną ochronę przed błędami w oprogramowaniu i posiadać inny program zastępczy, niż oryginał. Jak wtedy ocenić, który z dwóch poprawnie działających procesorów podejmuje dobrą decyzję?
Sformułowanie problemu
Zagadnienie to zostało bardzo obrazowo sformułowane w roku 1980, przez trzech naukowców.
Byli nimi Marshall Pease, Leslie Lamport oraz Robert Shostak, a sam problem opisali następująco:
Grupa armii bizantyjskich otacza miasto wroga z czterech stron. Aby je zdobyć wszystkie oddziały muszą zaatakować jednocześnie, w przeciwnym wypadku poniosą klęskę. Każdy przywódca oddziału ma swojego zaufanego posłańca, który dostarczy komunikat do innego przywódcy. Jednak nie mamy pewności, czy któryś z przywódców nie jest zdrajcą, któremu zależy na doprowadzeniu wojsk bizantyjskich do porażki. Należy więc opracować taki algorytm, który pozwoli wszystkim wiernym generałom na uzgodnienie planu działania. Jeśli któryś okaże się zdrajcą, wtedy będzie jeszcze możliwość odwrotu i ocalenia wojsk - jeśli natomiast zdrajca ujawniłby się dopiero podczas ataku byłoby już za późno na odwrót co oznaczałoby koniec dla całej armii.
Przywódcy oddziałów są więc podmiotami decyzyjnymi w systemie rozproszonym, a posłańcy to kanały komunikacyjne. Aby algorytm zadziałał musi on spełniać następujące warunki.
- Wszyscy wierni przywódcy podejmują taką samą decyzję.
- Niewielka liczba zdrajców nie spowoduje podjęcia złej ostatecznej decyzji, która będzie niezgodna z zamiarami większości przywódców.
Możemy również założyć, kiedy ewentualnie należałoby się wycofać poprzez ustalenie limitów czasowych, po przekroczeniu których, jeśli nie uzyskamy odpowiedzi od reszty oddziałów to uznajemy, że nie zdecydowały się one na atak.
Czy da się go rozwiązać?
Tak, jednak wymaga to bardzo wielu rund, w których będą wysyłane komunikaty. W pierwszej kolejności przywódca przekazuje pozostałym oddziałom swoją decyzję. Otrzymane od innych informacje oraz swój głos zapisuje na unikalnej tablicy. Następnie, każdy z przywódców przekazuje innym zawartość swojej tablicy. Nie musi on otrzymać tablicy, którą sam wypełniał oraz przekazywać tej którą posiada z powrotem do nadawcy. Jeżeli liczbę zdrajców oznaczymy literką “Z” to do ustalenia prawidłowej decyzji potrzebne będzie Z+1 rund. Sumaryczna liczba wszystkich przywódców powinna wynosić wtedy 3Z+1. Ze względu na znaczną liczbę komunikatów jakich wymaga to rozwiązanie w praktyce byłoby ono nieprzydatne, jeśli liczba zdrajców okazałaby się duża.
Jakie rozwiązanie oferuje technologia blockchain?
W przypadku technologii blockchain odnosi się ono do tego, że przynajmniej dwa węzły będą mogły się ze sobą komunikować mając gwarancję wyświetlania takich samych danych. Jest to trudne zadanie, jednak możliwe do osiągnięcia. Sieć blockchain wykorzystuje technologię P2P (ang. peer-to-peer) w której konsensus jest osiągany, jeśli “lojalne” lub nieuszkodzone węzły podejmą większościową zgodę co do decyzji. Sieć większości kryptowalut wykorzystuje odpowiedni algorytm konsensusu, czyli mechanizm zapewniający rozwiązanie problemu bizantyjskich generałów. Najczęściej spotykanymi implementacjami są protokoły proof-of-work lub proof-of-stake.
Jeśli jeszcze nie wiesz jak działają protokoły wykorzystywane w sieciach blockchain zachęcamy do przeczytania naszego wcześniejszego artykułu!
Więcej na temat proof-of-work i proof-of-stake możesz przeczytać również w tym artykule.