AAL260 - ćw - temat C2
Algorytmy rozproszone c.d.
Zadanie
54 "max ID"
Wymyśl algorytm rozproszony znajdujący maksymalny ID w dowolnym grafie;
równocześnie powinien to być algorytm znajdujący lidera w grafie ...
(+ implementacja w symulatorze).
Zadanie 55 "drzewo BSF"
Wymyśl algorytm rozproszony znajdujący drzewo BSF w dowolnym grafie.
(+ implementacja w symulatorze).
............................................................
Od tego miejsca zajmujemy się algorytmami w modelu obliczeń:
* z przesyłaniem komunikatów
* asynchronicznym (nie
ma rund!!!; każdy węzeł sieci czeka na komunikaty od sasiadów
i reaguje na nie
obliczeniami lokalnymi i/lub wysyłając komunikaty)
W pliku aal260_asynch.txt pokazano jak
używać naszego symulatora do
symulowania algorytmów asynchronicznych
...
Wszystkie komunikaty mają "typ" jest to pierwszy elem komunikatu
traktowanego jako lista.
Istnieje procedura "OdbierzKomTypu typ od_kogo"
gdzie od_kogo to numer sąsiada; procedura ta wyciąga z listy komunikatow
(które przyszły od od_kogo) komunikaty podanego typu;
gdy nie ma już takich komunikatów następuje powrót do konsoli.
Algorytm asynch. powinien odczytywać komunikaty wyłącznie tą procedurą!
Procedura "krokAsynch" wykonuje pojedynczy krok, czyli
wybiera losowo wierzchołek i następnie wykonuje jego kod, aą nie nastąpi
powrót od konsoli w OdbierzKomTypu.
Zadanie 56 "synchronizator Alfa"
Spróbuj symulować model synchroniczny na maszynie asynchronicznej
w następujący sposób:
w i-tej (symulowanej)
rundzie, każdy wierzchołek wysyła komunikaty,
które powinny byc
wysłane w i-tej rudzie,
następnie wysyła
komunikat SAFE do wszystkich sąsiadów,
następnie czeka na
komunikat SAFE od wszystkich
sąsiadów,
następnie przechodzi do
rundy i+1 ...
(jest to tzw symulator alfa)
Wypróbuj jak działa Twoj synchronizator na przykładzie trywialnego
algorytmu synch. w którym każdy wierzchołek ma licznik_rund
i w każdej rundzie zwieksza go o 1;
jako wizualizajce działania pokazuj wartości zmiennej licznik_rund
na wszystkich wierzchołkach.
Odpowiedz na pytanie:
mamy 2 wierzchołki: a i b;
jak bardzo może się różnić nr rundy w wierzchołku a i b ???