SUM na Politechnice Poznańskiej, SKiSR

Smigacz

wstawiam zadania jakie pojawily sie na dzisiejszym egzam. dla grupy II, moze ktoś ma zadania dla grupy I

Gość

Czy ktoś zna odpowiedź na pytanie 5 ?

Na wykładach nie było takiego przykładu, była tylko mowa o tym że reguluje to Twierdzenie 1 Impossibility Results i że ktoś to już kiedyś udowanił.

Gosc · Gość

Mylbym wdzieczny gdyby ktos podal tu rozwiazania zadań 2 i 3

Gość

Jeśli ktoś zna rozwiązanie na pyt 1 i 4 to też może podać Smile

Gość

jaka brdzie prawidlowa linia odtwarzania dla przykladu z zadania pierwszego?

Gość

ODP 2 wg mojej wiedzy, proszę o poprawienie jeśli coś jest nie tak

Kod znajduje się na slajdach
Algorytm działa rekurencyjnie wykonując w każdej rekurencji OM(t), gdzie t - liczba zdrawjców; Ostatnim wykonaniem jest OM(0); W zadaniu mamy 1 zdrajce (jest nim generał głównodowodzący Gc) wiec t=1;

Krok 1:
Wykonanie OM(1);
Tu chyba można by przerysować ten rysunek stanu początkowego;
Gc jest generałem głównodowodzącym - on decyduje co mają zrobić pozostali, Gc jest jednak zdrajcą więc rozsyła do 2 generałów ATAK(1) a do 2 pozostałych ODWRÓT(0);

Krok 2:
Każdy proces uruchamia własną instancję algorytmu OM(t-1) a więc każdy wykonuje OM(0) - rozsyła swoją wartość do pozostałych generałów (np. G1 wysyła wartość ATAK(1) do G2,G3,G4);
W wyniku tego każdy z generałów G1-G4 buduje swój wektor (v1,v2,v3,v4) gdzie np, v3 jest wartością pochodzącą od G3 - w tym przypadku każdy zbuduje identyczny wektor (1,1,0,0)
(Tu można narysować rysunek jak przesyłają sobie wartości)

Krok 3:
Generałowie podejmują decyzję wykonując funkcję majority(1,1,0,0), jaka będzie ostateczna decyzja to nie ma znaczenia, a więc może to być 1(ATAK) lub 0(ODWRÓT) , istotne jest to że każdy poprawny generał podejmie taką samą decyzję bo funkcja majority wszędzie będzie działała tak samo (np. wybierze większość jeśli nie znajdzie jej to wybierze 0 (ODWRÓT))

Załóżmy że w każdym procesie funkcja majority zwróciła ODWRÓT, ostatecznie problem bizantyjski został rozwiązany:
BA1: Każdy poprawny proces podjął tą samą decyzję
BA2: Jeśli Gc byłby poprawny to pozostali poprawni generałowie musieliby wykonać jego rozkaz ... ale nie był

Gość

wg. mnie pytanie 2 jest dobrze rozwiazane, moze ktos przedstawic odp na pytanie 1

Smigacz

wydaje mi się ze w zadaniu 1 linia odtwarznia powinna przebiegac tak:

P1 drugi cp
P2 drugi cp
P3 drugi cp
P4 trzeci cp
P5 drugi cp

ale wydaje mi się też, że pan M.Sz. gdzieś jakich haczyk umieścił bo nikt za to zadanie nie zgarnął max punktów

EDIT ze strony p.Michała
SUM SKiSR sem.3.: Systemy Wiarygodne - egzamin poprawkowy - 10 lutego godz. 9:00, sala C-8 CW.

Gość

M... · Gość

A ktoś na podstawie tego diagramu przestrzenno czasowego narysował extended checkpoint graph a następnie stosując algorytm Wanga Fuchsa wyznaczył linie ottwarzania. Mi sie wydaje ze tak trzeba do tego podejsc.

Najpierw wyznaczamy rollback edges i cofamy sie do wierzchołka poprzedzajacego wierzcholek na ktory wskazywala ta krawedz (rollback edges) potem rysujemy root set i usuwamy wszystkie wierzchołki tak aby w root set nie było krawedzi łaczacych wierzcholki nalezacych do root set

i tak wyznaczony zbior root set wyznacza linie odtwarzania

Popzdrawiam

Gość

Ja narysowalem graf, wg tego grafu nalezy wycofac prawie wszystkie procesy ( chyba ze go zle zrozumialem), wtedy linia odtwarzania by wygladala tak:
P1 1
P2 2
P3 1
P4 3
P5 1

prosze o korekte jesli moje rozumowanie jest bledne:)