ALR - ćw - temat B

symulator algorytmów (wszystko co potrzebne)

Zadania

Zadanie 12 (impl.)(2pkt) "ciężkie gwiazdy w drzewie ukorzenionym"
Dane jest drzewo ukorzenione T, z wagami na krawędziach.
Zaimplementuj algorytm znajdujący rozłączne gwiazdy o ŁĄCZNEJ wadze >=1/2*w(T).
Czas działania algorytmu powinien być rzędu O(wysokość(T)).
Uwaga: nie należy używać długich komunikatów, tj nie zbierać obrazu całego drzewa w korzeniu!
Zakładamy, że wierz znają wysokość(T).

Zadanie 13 (impl.) "wybór lidera w grafie dowolnym"
Zaimplementuj synchroniczny algorytm wyboru lidera w dowolnym grafie;
użyj "flooding"-u do obliczenia max ID;
zbadaj liczbę komunikatów i czas działania tego algorytmu;
zastanów się czy można tu coś zoptymalizować...
zastanów się co jest potrzebne (jakie parametry sieci),
aby algorytm mógł się zakończyć na wszystkich wierzchołkach

Zadanie 14 (impl.)(2pkt) "orientacja kraw. z outdeg<=2 w drzewie"
Zaimplementuj algorytm znajdujący orientację krawędzi z outdeg<=2 w drzewie (nieukorzenionym!)

Zadanie 14a (impl.)(3.5pkt) "szybka orientacja kraw. z outdeg <=2 w drzewie"
Jak 14 ale czas działania ograniczony przez O(logn log^*n) lub lepszy.

Zadanie 14b (impl.)(*)(5pkt) "szybkie ciężkie gwiazdy w drzewie"
Czas działania ograniczony przez O(logn log^*n).

Zadanie 15 (impl.)(*)(5pkt) "szybkie ciężkie gwiazdy w drzewie ukorzenionym"
To samo co w zadaniu 12, ale tym razem w znacznie krotszym czasie, rzędu O(log^*n).
Być może gwiazdy bedą nieco "lżejsze" niż poprzednio...
W tym zadaniu warto pokazać jak te gwiazdy wygladają przy pomocy symul_graf_lib.tcl/ G::rysujGraf.

Zadanie 19 (impl.) "LE, O(n^2)-komunikatów, model asynch"
Zaimplementuj prosty algorytm wyboru lidera w cyklu zorientowanym,
ale tym razem w modelu/symulatorze asynchronicznym!
Zbuduj egzekucję asynchroniczna pokazującą działanie algorytmu...
Aby to nie był dokładnie taki sam algorytm jak w tutorialu, wprowadźmy pewne zmiany:
1. niech liderem będzie wierz z min ID,
2. niech będzie używany mechanizm zapamiętywania min zobaczonego ID na każdym wierzchołku,
3. nie używaj komendy czytajKomTypu.

Zadanie 20 (impl.) "max ID w drzewie ukorzenionym, model asynch"
Zaimplementuj algorytm asynchroniczny znajdujący max ID w drzewie ukorzenionym,
używający minimalnej liczby komunikatów.
Jedynie wierzchołek z max ID musi wiedzieć o tym fakcie; pozostałe wierzchołki nie muszą
wiedzieć (że nie maja max ID).
Zbuduj egzekucję asynchroniczna pokazującą działanie algorytmu...

Zadanie 21 (impl.)(*)(4pkt) "LE w grafie pełnym, asynch."
Opis algorytmu znajduje się w rozdziale 3 wykładu H.A.
patrz także slajdy z wykładu Łukasza Kusznera (kilka ostatnich): wykład7
(jest tam nieco zmodyfikowana wersja tego algorytmu w stosunku do materiałów H.A.)
należy użyć symulatora asynchronicznego.
Mile widziana ciekawa wizualizacja graficzna!

Zadanie 22 (impl.)(3pkt) "leader election O(n logn) - impl. asynch !"
Zaimplementuj asynch. algorytm wyboru lidera, używający O(n logn) komunikatów, w symulatorze asynchronicznym...
(Poprzednio, w temacie A, robiliśmy to w symulatorze synchronicznym!)
Oprócz algorytmu trzeba będzie także wygenerować sensowną egzekucję...

.............................. MST

Zadanie 26 (impl.)(2pkt) "łączenie fragmentów na użytek MST"
Napisz algorytm łączący "fragmenty" (w sensie używanym podczas obliczania MST).
Jak wiemy, każdy fragment zawiera drzewo spinające będące "fragmentem MST";
dwa fragmenty łączymy, jeśli jest między nimi krawędź MOE;
nowy "duży" fragment powinien zawierać drzewo spinające będące sumą drzewek w "małych" fragmentach + krawędź MOE.
Aby uprościc to zadanie robimy następujące założenia:

1. krawędzie MOE, na podstawie których łączymy fragmenty, są dane z góry
2. łączyć się będą jedynie pary fragmentów
3. wagi krawędzi nie są potrzebne
4. fragmenty mają ID; każdy wierz. zna ID swojego fragm.
5. drzewa spinające we fragmentach są ukorzenione

Proszę oszacować czas działania algorytmu (może zależeć np. od max średn. fragmentów).
Wszystko robimy w synchronicznym modelu/symulatorze!

Zadanie 27 (impl.)(2pkt) "obliczanie MOE pojedynczego fragmentu"
Krawędzie mają wagi; w grafie jest dany jeden fragment F;
fragment F zawiera drzewo spinajace ("fragment MST");
oblicz krawędź MOE fragmentu F, oraz niech ona się dowie, że nią jest!
Wszystko robimy w synchronicznym modelu/symulatorze!
Co do impl. wag kraw. w symulatorze, patrz rozszerzenia symulatora.
Uwaga: zakładamy, że fragment MST jest ukorzeniony!

Zadanie 27a (impl.)(*)(4pkt) "obliczanie MOE + łączenie fragmentów"
Połącz zadania 27 i 26; stosuj(?) zasady "kombinacji" i "absorbcji" z alg GHS.
Wszystko w modelu synch!

.............................. BFS

Zadanie 28 (impl.)(2pkt) "drzewo BFS"
Zaimplementuj synchroniczny algorytm budujący drzewo BFS w zadanym wierzchołku "r".
Drzewo BFS to takie drzewo ukorzenione, w którym dla każdego wierzchołka v
ścieżka skierowana po drzewie od v do r jest najkrótsza...
Oszacuj liczbę komunikatów i czas działania algorytmu.

Zadanie 29 "asynchroniczne drzewo BFS"
Zastanów się, czy można uruchomić synchroniczny algorytm BFS w sieci asynchronicznej,
przy pomocy synchronizatorów alfa i beta.
Oszacuj złożoność komunikatową i czasową w modelu asynch., gdy algorytm BFS działa
pod wybranym synchronizatorem.

Zadanie 29a (impl.)(*)(4pkt) "asynchroniczne drzewo BFS"
Ma to być asynch implementacja na zasadzie: "alg. synch BFS" + "synchronizator X".
Przygotować także egzekucję oraz jej ciekawą wizualizację...

.............................. synchronizatory

Zadanie 30 (impl.)(1.5pkt) "synchronizator alfa"
Zaimplementuj synchronizator alfa i zbadaj jaki jest numer rundy na różnych wierzchołkach,
w czasie działania algorytmu:

   set liczRundy 0
   while 1 {
      incr liczRundy
      // wstawka realizująca "koniec rundy"
   }

Wskazówka: dla ułatwienia użyj komendy "dostarcz" zamiast "wyslij", dzięki czemu
trzeba genereować jedynie zdarzenia obliczeniowe (a nie obliczeniowe i dostarczenia),
czyli nie jest konieczne używanie dostarczKom.
Uwaga 1: używanie komendy "czytajKomTypu SAFE * pol" jest niebezpieczne, gdyż
usuwa ona komunikaty z kolejek komX... dlatego lepiej opracowac własną proceurę sprawdzania
czy wierzchołek i jego sąsiedzi są bezpieczni, operującą bezpośrednio na zmiennych kom(X)
(zainstalowac ją przy pomocy fiber_iterate { proc ... }).
Uwaga 2: przypominam, że w synchronizatorze alfa komunikaty alg. synchronicznego są
dostarczane z potwierdzeniem (niezaleznie od komunikatów SAFE),
zatem używanie dostarcz zamiast wyslij jest tym bardziej uzasadnione...
Uwaga 3: w modelu asynch. wszystkie wierzchołki MUSZĄ działać w nieskończoność !!!
gdyż jeśli jakiś fiber kończy pracę to wykonuje "fiber yield" zamiast "fiber switchto main";
jest to "pozostałość" po symulatorze synch, która nie została jeszcze naprawiona (15.11.2016)
Uwaga 4: najłatwiej zrobić eksperyment do tego zadania w cyklu...
(ale procedure "koniec rundy" lepiej napisać ogólnie!)

Zadanie 31 (impl.)(1.5pkt) "synchronizator beta"
Zaimplementuj synchronizator beta...
Założenie upraszczające: drzewo spinające graf jest dane z góry!
Eksperyment może być taki sam jak w zadaniu 30, czyli obserwujemy liczniki rund.

Zadanie 32 "synchronizatory - nr rundy"
Zbadaj jaka może być maksymalna różnica nr rundy (w danej chwili, na różnych wierzchołkach),
gdy model synchroniczny jest symulowany w sieci asynchroncznej,
przy pomocy synchronizatorów: alfa, beta, gamma.
Swoją odpowiedź poprzyj dowodem!

Zadanie 33 (inż.)(1.5pkt) "'przeźroczysty' synchronizator alfa"
Zaprogramuj jeszcze raz synchronizator alfa w taki sposób, aby było możliwe uruchamianie
algorytmów synchronicznych (napisanych dla trybu synchronicznego symulatora)
bez żadnych zmian w kodzie źródłowym...
Należy to osiągnąć przy pomocy dodatkowych interpreterów (komenda "interp" j. Tcl);
każdy fiber ma mieć pomocniczy interpreter, w którym należy:
1. dodać tzw aliasy dla komend (fiber, wyslij, czytaj), które będą działaly inaczej niż prawdziwe,
2. tworzyć zmienne, których spodziewa się algorytm synchroniczny (komX, stopien, id, id_los, ...),
które mogą być inne niż oryginalne zmienne w fiberze.
Otrzymany w ten sposób przeźroczysty synchronizator wypróbować z jakimś algorytmem synchronicznym,
np. LE/jednorodnym lub algorytmem znajdującym drzewo BFS.
Przykład jak zagnieżdżać interp w fiberze: q3_test.tcl

Zadanie 33a (impl.) (1.5pkt) "dist(a,b)≤x"
W ścieżce są 2 wierz a i b. Wierzchołek a chce odpowiedzieć na pytanie czy "dist(a,b)≤x".
Podaj i przetestuj wersję algorytmu, która działa pod synchronizatorem alfa,
w czasie O(x) wirtualnych rund.
Wierz a i b są oznaczone "ręcznie", dodatkowo wierz a ma podaną wartość x.
Użyj w algorytmie proc wirtalne_fiber_yield jako impl. synchronizatora alfa.

Zadanie 33b (impl.)(2pkt) "uogólnienie synch alfa"
Uogólnij synch alfa tak, aby przejście wierz "v" do następnej wirt rundy następowało
gdy kula o promieniu "q" i środku "v" jest bezpieczna...
Zbadaj działanie tej wersji synch jak w zadaniu 30, dla q=3.
Wskazówki: patrz: str 8 tutaj + literatura tam podana...

.............................. fault tolerance

Zadanie 34 (impl.)(1.5pkt) "Consensus"
Zaprojektuj eksperyment pokazujący nietrywialne działanie algorytmu Consensus...
Nasz symulator nie jest przystosowany do algorytmow synch. "psujących się w połowie rundy", dlatego
najlepiej użyc proc. blad {iter1 iter2}, ktora generuje blad fibera przy pomocy error "crash",
w odpowiednio dobranej chwili (patrz tutaj)
Uwaga: przez "nietrywialne działanie" rozumiemy takie, w którym coś się zmienia
także w ostatnich iteracjach pętli for...
Opis alg. Consensus patrz str 5 slajdów

Zadanie 34a (impl.) "Consensus - inna wersja"
Zaimpl. alg. Consensus, bez "przesunięcia fazowego" między rundami i iteracjami for.
Przetestuj swoje rozwiązanie (tak jak zwykle).

Zadanie 34b (impl.)(3pkt) "LE odporne na błędy"
Prawdopodobne rozwiązanie: Consensus, w którym liczba na którą wszyscy się zgadzają
należy do NIEpopsutego wierz ?!?!

.............................. dekompozycja Linial&Saks

Zadanie 35 (impl.)(1.5pkt) "wierzchołki w kulach, 'wariacja' na temat decomp L&S"
W sieci jest zbiór wierzchołków X (X jest podzbiorem V); każdy wierzchołek v z X ma promien r_v.
Chcemy, aby każdy wierz v z X "poznał" inne wierzchołki z X, które są w jego kuli o promieniu r_v.
Proszę zapisać odpowiedni algorytm w symulatorze, oraz przetestować go na sieci kratowej...
Uwaga: Proszę zauważyć, że nie wystarczy rozsyłać komunikaty na odległość r_v, gdyż wtedy
wierzchołki w kuli zobaczą ID_v, a my potrzebujemy czegoś wręcz odwrotnego!!

Zadanie 36 (impl.)(*)(4pkt) "obliczanie dekompozycji L&S"
Zaimplementuj w symulatorze algorytm losowy obliczający (logn, logn)-dekompozycję Liniala&Saksa.
"Zwizualizuj" wynik działania tego algorytmu, może na grafie kratowym (?).
Jak generować losowe promienie zgodnie z odp. rozkładem prawd. (?).
Model synchroniczny.
Zadanie musi być wykonane w symulatorze synch.!!

..............................

Zadanie 16 (impl.)(1.5pkt) "skojarzenie maximal w stałym czasie, G=(L,R,E), Delta(L)<const"
Proszę zaimpl. algorytm synch. obliczający skojarzenia maximal,
w grafie dwudzielnym G=(L,R,E), gdzie L i R to zbiory wierzchołków (lewa i prawa strona),
przy założeniu, że stopnie na L są stałe (np. <=5);
algorytm powinien działać w stałej liczbie rund.

Zadanie 37 (impl.)(3pkt) "obliczanie semi-skojarzeń (load balancing)"
W grafie G=(U,V,E), gdzie U to dolne wierz. (kli), V do górne wierz (ser),
oblicz stałą aproksymację semi-skojarzenia, przy pomocy skojarzeń lub q-skojarzeń maximal...
Założenie upraszczające: wierz. U mają stałe stopnie (to b. ułatwia obliczanie skojarzeń maximal!!).
W czasie trwania symulacji obserwuj rozmiar zbioru U.
Model synchroniczny.

Zadanie 38 (impl.) "ściąganie danych po ścieżce w modelu CONGEST"
Mamy ścieżkę o długości "x"; na 1 końcu jest "a" jednostek danych (logn bitów);
czas przesłania danych na 2 koniec ścieżki wynosi "a+x".
Mamy ścieżkę z dwoma źródłami danych o rozmiarach "a" i "b";
odległość między źródłami to "x"; odległość od źródła b do 2 końca to "y";
czas przesłania danych na 2 koniec ścieżki wynosi "a+max(x,b)+y".
Zbadaj na symulatorze (synch) czy powyższe wzory są prawidłowe.
Uwaga: w modelu CONGEST jest ograniczenie długości komunikatów;
w 1 komunikacie można umieścić tylko "jednostkę danych" czyli logn bitów.


Zadanie 38a (impl.)(2.5pkt) "ściąganie danych po ścieżce; 3 źródła"
Wymyśl wzór dla 3 źródeł o rozmiarach a,b,c; długości segmentów ścieżki to x,y,z.
Przetestuj wzór na symulatorze, tak jak w zadaniu 38!

Zadanie 38b (impl.)(4.5pkt) "ściąganie danych po ścieżce; 'n' źródeł"
Wymyśl wzór ogólny dla "n" źródeł.
Przetestuj wzór na symulatorze, tak jak w zadaniu 38, dla różnych wartości n.
Uwaga, 04.2023: zadanie w wersji ogólnej zostało wykonane przez p. Mateusza Dokowicza