Sr-11-wyk-1.0-Slajd13

From Studia Informatyczne

Problem dwu armii

Problem dwu armii


Kanały komunikacyjne w problemie dwu armii są zawodne. Każdy komunikat może być więc utracony. Załóżmy, że generał pierwszej armii niebieskiej wysyła posłańca z wiadomością „atakujemy” do generała drugiej armii. Ten odebrawszy propozycję, odsyła posłańca z wiadomością „ok, atakujemy”. Generał 1 dostaje potwierdzenie, ale zauważa, że generał 2 nie wie, że on dostał potwierdzenie, a więc że może nie wiedzieć czy przeprowadzić atak czy nie. W związku z tym wysyła drugiego posłańca potwierdzającego decyzję o ataku. Generał 2 po odebraniu wiadomości stwierdza, że generał 1 nie wie, że jego posłaniec dotarł z potwierdzeniem, a skoro nie dotarł to generał 2 może zwątpić w plany ataku. Na wszelki wypadek wysyła więc kolejnego posłańca do generała 1, potwierdzającego odbiór wiadomości o potwierdzeniu ataku... Łatwo zauważyć, że bez względu na liczbę przesyłanych komunikatów (posłańców), generałowie nigdy nie uzyskają całkowitej pewności co do podejmowanej decyzji. Wynika to z tego, że zawsze ostatni przesyłany komunikat nie będzie potwierdzany, a jeżeli nie ma pewności, że komunikat ten dotarł, to nie ma również pewności, że cały protokół podejmowania decyzji został zakończony. Pomimo więc bardzo prostej sytuacji modelowej – mamy tu do czynienia z dwoma poprawnymi procesami (generałowie) – nie można podjąć decyzji, ponieważ komunikacja jest zawodna.


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