ALR - algorytmy rozproszone - wykład i ćwiczenia

Prowadzący: Michał Hanćkowiak

Ocena z przedmiotu

uwaga skierowana do studentów wybierających ten przedmiot:
jeśli nie możecie Państwo chodzić na wykłady to b. proszę NIE wybierać tego przedmiotu !!!
takie osoby mają potem BARDZO DUŻE problemy ze zdaniem egzaminu...
egzamin pisemny z wykładu
termin egzaminu: 25.06.2024, 11:30, A0-1, poprawkowego: 10.09.2024, 12:00, B3-34 (lub A0-3)
https://lms.amu.edu.pl/sci/course/view.php?id=514
kolokwium dotyczące ćwiczeń, ostatnie ćwiczenia, 19.06.2024
może obniżyć ocenę ze sprawozdań o: 0, 0.5, 1
Uwaga: kolokwium dotyczy wszystkich tematów (ale głównie A,B)
https://lms.amu.edu.pl/sci/course/view.php?id=514
sprawozdania z wykonania zadań na ćwiczeniach
wysyłać mailem po oficjalnym zamknięciu danego tematu; w subject podać "ALR, Temat X", X=A,B,...
sprawozdania muszą mieć następujący format
za każde wykonane zadanie otrzymujemy 1pkt (chyba że napisano inaczej)
sprawozdania muszą zawierać: kod, wydruki, komentarze, odp. na pytania itp
sprawozdania piszemy SAMODZIELNIE !!!
(dotyczy to też robienia zadań, wykonywania eksperymentów itp)
w przypadku stwierdzenia plagiatu lub innych nieprawidłowości
następuje automatyczne odesłanie na termin poprawkowy !!!
Uwaga: do maila proszę dołączyć .zip z pełnymi plikami źródłowymi (nazwy plików typu zadanie1.tcl itp)
tutaj są (będą) *** oceny *** sprawozdań...
mini-referaty na ćwiczeniach
mini-referat może dotyczyć zadań z tematów A i B, oznaczonych (*)
(być może także z innych tematów, ale trzeba to uzgodnić z MH)
1. należy omówić algorytm przy tablicy
2. należy zademonstrować działanie algorytmu na symulatorze z wizualizacją (rzutnik)
3. należy omówić kod źródłowy implementacji w symulatorze (rzutnik)
4. referat musi być wygłoszony w trakcie zajęć, przy obecności studentów
mini-referat powoduje dodanie liczby 0.5 do oceny z egzaminu oraz z ćwiczeń

Ćwiczenia

symulator algorytmów (wszystko co potrzebne)
temat A - symulator synch
(zamknięty 20.03.2024)
temat B - symulator synch/asynch
(zamknięty 08.05.2024)
temat C - zadania inżynieryjne, gniazdka, MOM
temat D - współbieżność (model asynch ze wsp. pamięcią), j. BACI,
pkt z tego tematu zostaną pomnożone przez 0.85 (przez MH)
temat E - weryfikacja/ model checking: Spin/Promela, Sieci Petriego
(CDE zamknięte 19.06.2024)
ostateczny termin przysyłania sprawozdań to 23.06.2024
ostateczny termin przysyłania sprawozdań poprawkowych to ???
proszę każdy temat wysłać w osobnym mailu !!

Plan wykładu

modele obliczeń wieloprocesorowych "message passing" i "shared memory"
message passing - wersja asynchroniczna i synchroniczna
pojęcia: konfiguracja, zdarzenie, egzekucja, ...
algorytmy wyboru lidera "LE" w cyklu, asynch i synch
asynch: wysyłające O(n^2) i O(nlogn) komunikatów
synch: jednorodny, wysyłający O(n) kom.
dolne oszacowanie na liczbę kom. (tylko szkic??)
powyższe algorytmy opisane w rozdz 2 książki H.A. distrib_alg-Attiya.pdf
kolorowanie wierzchołkowe w drzewie ukorzenionym i uogólnienia
algorytm C&V (Cole&Vishkin), tree.pdf str 3-8, simplemis.pdf od str 6; patrz też: -1-
skojarzenie maximal w grafie (dwudzielnym)
alg. oparty o spannery, działający w czasie O(log^4n), patrz fmatch.pdf rozdz 2
nowe prace: 2017, M. Fischer, poszukaj "Improved Deterministic Distributed Matching via Rounding"
aproksymacja MIS/MWIS, MM, MDS w grafach planarnych przy pomocy klastrów
planar2.pdf (slajdy), szybkie obl. klastrów: disc2008.pdf (slajdy)
obliczanie MST (= Minimum Spanning Tree) w grafie dowolnym
alg. asynch [GHS], ogólna zasada działania, z wykladu H.A.
alg. synch [GKP], krótkie komunikaty, opisane w GKP.pdf
synchronizatory alfa, beta, gamma oraz inne
alfa, beta, gamma z wykladu H.A.; eta_1 i teta są opisane tutaj LPCR9410.pdf
klastry typu "partition" i "cover" na użytek synchronizatorów
dekompozycja L&S (Linial&Saks)
algorytm losowy znajdujący dekompozycje, zastosowania dekomp., -1- (str 327-329)
sieci popełniające błędy (fault tolerance)
algorytm znajdujący "Consensus", z wykladu H.A.
problem 2 generałów, dowód niewykonalności, z wykladu H.A.
model shared memory (współbieżność)
slajdy, problem sekcji krytycznej, inne problemy współbieżności, semafory, monitory
weryfikacja (= model checking) czyli automatyczne dowodzenie poprawności alg. asynch
slajdy, dwa podejścia: Spin/Promela, Sieci Petriego, literatura: patrz ćw/temat E
dowód, że stałej aproksymacji MIS w cyklu nie da się znaleźć w stałym czasie
opisane w chwdisc08.pdf, rozdział 4.1 (str 9); konsekwencje tego faktu (5-aproks MDS)
--- tu skończyliśmy ---
semi-skojarzenie czyli load-balancing,
stała aproks przez redukcję do mssc.pdf (str 4-6), slajdy (str 2 i 12-17)
obliczanie stałej aproksymacji MDS w grafach "planarno podobnych"
aproksymacja ważonego skojarzenia (MWM) w grafach planarnych
klastry wierzchołkowe i krawędziowe chcocoon07-exp.pdf
asynch. LE w grafie pełnym
opisane w afek.ps str 12-14 (algorytm B), oraz wykład H.A. rozdz 3

Literatura

główna książka: Hagit Attiya "Distributed algorithms" distrib_alg-Attiya.pdf
artykuły omawiające konkretne algorytmy - podane w planie wykładu
Hagit Attiya, Jennifer Welch, "Distributed Computing - Fundamentals, Simulations, and Advanced Topics"
Nancy Lynch "Distributed Algorithms"
pomocniczy folder z plikami pdf oraz innymi... (tutaj są też slajdy do wykładów online 03.2020)

na wypadek problemów z teams i przełączaniem slajdów...
potrzebne programy putty.exe i vncviewer.exe z folderu

References to this Page: pl:strona_glowna, pl:zar_mgr