Sr-11-wyk-1.0-Slajd14

From Studia Informatyczne

Problem bizantyjskich generałów

Problem bizantyjskich generałów


Rozpatrzmy teraz przypadek, kiedy komunikacja jest niezawodna, ale procesy mogą ulegać dowolnym awariom. Klasycznym przykładem może być tutaj problem bizantyjskich generałów . W tym przykładzie również armia niebieska będzie atakować armię czerwoną, ale tym razem armia niebieska jest dowodzona przez n generałów, którzy muszą podjąć wspólnie decyzję. Do podjęcia decyzji jest potrzebna wiedza dotycząca liczebności podległych im oddziałów. Niestety m spośród wszystkich n generałów jest zdrajcami. Oznacza to, że ich odpowiedzi będą celowo nieprawdziwe i sprzeczne, próbując w ten sposób nie dopuścić do porozumienia się generałów lojalnych. Zakładamy tu dodatkowo, że generałowie zdrajcy nie współpracują.

Ze względu na przewidywane dowolne awarie procesów, należy w tym przypadku inaczej zdefiniować porozumienie. Generałowie dążą do ustalenia liczebności oddziałów i wymieniają te informacje między sobą. Porozumieniem jest ustalenie wektora liczebności oddziałów przez poszczególnych generałów, w taki sposób, że jeżeli i-ty generał jest lojalny, to i-ta pozycja wektora zawiera liczebność jego oddziału. W przeciwnym razie pozycja ta będzie nieokreślona.


<< Poprzedni slajd | Spis treści | Następny slajd >>