SY (systemy sieciowe i komputerowe)AZ (algorytmika i złożoność obliczeniowa)
Opis przedmiotu:
Obliczenia rozproszone stanowią obecnie naturalny sposób przetwarzania
informacji – od sieci globalnych jak Internet do systemów wieloprocesorowych
czy wielordzeniowych. Środowisko rozproszone daje możliwość przyspieszenia
obliczeń dzięki podziale zadań na wiele komputerów. Jednocześnie dane, na
których prowadzone są obliczenia są często rozproszone w sieci (niedostępne w
całości poszczególnym komputerom), co stanowi istotne utrudnienie i wymaga
kosztownej komunikacji. Dlatego oprócz czasu obliczeń i zużywanej lokalnie
pamięci, w konstrukcji algorytmów rozproszonych kluczowe są też inne miary
jakości, m. in.:
* liczba rund komunikacji koniecznych do zakończenia obliczeń,
* rozmiar przesyłanych pojedynczych wiadomości jak i sumaryczny ruch w sieci konieczny do rozwiązania problemu,
* opóźnienia (latency) w dostarczaniu wiadomości,
* stabilizacja (osiągnięcie stabilnego pożądanego stanu obliczeń).
Celem wykładu jest zapoznanie studentów z najpopularniejszymi obecnie modelami
obliczeń rozproszonych oraz problemami **algorytmicznymi** w nich
występującymi. W szczególności wykład skoncentrowany będzie na rozwiązywaniu
problemów grafowych w środowisku rozproszonym, a także na problemach
algorytmicznych związanych komunikacją i koordynacją współpracujących
jednostek, odpornościa na błędy, współdzieleniem łączy komunikacyjnych i
innych zasobów. Rozważane będą klasyczne modele obliczeń rozproszonych (Local,
Congest, pamięć dzielona) jak i nowsze (Congested Clique, radio/wireless
networks, MapReduce).
Wykład obejmować będzie m.in. następujące problemy w różnych modelach obliczeń
**rozproszonych** :
1. Rozproszone kolorowanie grafu (sieci)
2. Wyznaczenie składowych spójności grafu, (minimalnych) drzew spinających, BFS
3. Wyznaczanie najkrótszych ścieżek, problemy rutingu
4. Wyznaczanie maksymalnego zbioru niezależnego, minimalnego zbioru dominującego
5. Wyznaczanie minimalnych/maksymalnych cięć w grafie
6. Klastrowanie i dekompozycja sieci
7. Rozgłaszanie (broadcasting) i zbieranie (gathering) informacji, elekcja lidera, łamanie symetrii w sieciach (ad hoc).
8. Problemy algorytmiczne w środowisku z pamięcią dzieloną.
Tematyka wykładu będzie zbliżona m.in. do wykładów:
* [ETH](https://disco.ethz.ch/courses/podc/)
* [Aalto](https://users.ics.aalto.fi/suomela/da/)
* [Yale](http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf)
Na wykładzie przyjmuje się, że studenci znają materiał z przedmiotu Algorytmy
i Strutkury Danych, posiadają też podstawową wiedzę z rachunku
prawdopodobieństwa.
Uwaga. Program przedmiotu nie pokrywa się z programem przedmiotu _Algorytmy
rozproszone_ prowadzone. Studenci mogą zaliczać oba przedmioty.
**Literatura**
1. David Peleg. Distributed Computing: A Locality-Sensitive Approach Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8
2. Hagit Attiya, Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6
3. Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, Walter Unger. Dissemination of Information in Communication Networks Springer-Verlag, Berlin Heidelberg, 2005, ISBN 3-540-00846-2
4. Skrypty do wymienionych powyżej wykładów na różnych uczelniach.
###### Przewidywana formie zajęć w przypadku konieczności prowadzenia zajęć zdalnie:
- wykłady i ćwiczenia będą prowadzone w formie wideokonferencji.
