Przetwarzanie rozproszone

Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin)

Opis

Celem przedmiotu jest przedstawienie podstawowej problematyki przetwarzania rozproszonego oraz przykładów elementarnych rozwiązań wybranych problemów szczegółowych. Wykład wprowadza podstawowe pojęcia i przedstawia podstawowe elementy modelu przetwarzania rozproszonego, m.in.: formalny model środowiska przetwarzania rozproszonego, analizę aktywności i warunki uaktywnienia, klasyczne modele żądań, wykonanie procesu rozproszonego, właściwości przetwarzania rozproszonego (relacja poprzedzania, diagramy przestrzenno-czasowe, grafy stanów osiągalnych, niedeterminizm przetwarzania, spójność stanu, predykaty globalne i ich własności) oraz charakterystyki algorytmów rozproszonych (warunki poprawności algorytmów, złożoność czasowa i komunikacyjna). Omawiane są zagadnienia komunikacji zachowującej uporządkowanie wiadomości, wyznaczania stanu globalnego, synchronizacji czasu oraz detekcji zakończenia przetwarzania rozproszonego. Wreszcie przedstawiona jest problematyka związana z niezawodnością przetwarzania w zawodonym środowisku rozproszonym. Laboratorium pozwala nabrać praktycznej intuicji w konstrukcji i implementacji aplikacji rozproszonych w przykładowym środowisku. Na laboratorium studenci konfrontują uzyskane wiadomości z praktyczną implementacją algorytmów rozproszonych, projektują algorytmy rozproszone wdrażając je następnie w wybranym środowisku przetwarzania rozproszonego.

Sylabus

Autorzy

• Michał Szychowiak
• Jerzy Brzeziński

Wymagania wstępne

• Systemy operacyjne
• Sieci komputerowe

Zawartość

Wykłady

1. Charakterystyka systemów rozproszonych
2. Struktura środowiska przetwarzania, topologie
3. Kanały komunikacyjne, komunikacja synchroniczna i asynchroniczna
4. Środowiska typu GRID, przykładowe zastosowania
5. Model formalny procesu sekwencyjnego
6. Modele żądań
7. Konfiguracja spójna, odcięcie spójne
8. Predykaty globalne i ich własności
9. Czas wirtualny, zegary logiczne, zegary skalarne
10. Środowisko komunikacyjne zachowujące uporządkowanie przyczynowe wiadomości
11. Komunikacja grupowa
12. Warunki poprawności algorytmów rozproszonych
13. Złożoność czasowa i komunikacyjna algorytmów rozproszonych
14. Stan globalny systemu (modele, graf stanów, ocena)
15. Konstrukcja spójnego obrazu stanu globalnego
16. Różne realizacje przetwarzania rozproszonego klient-serwer
17. Problem detekcji zakończenia przetwarzania
18. Detekcja zakończenia dla synchronicznego modelu przetwarzania
19. Detekcja zakończenia dla dyfuzyjnego modelu przetwarzania
20. Detekcja zakończenia dla atomowego modelu przetwarzania
21. Detekcja zakończenia statycznego
22. Detekcja zakończenia dynamicznego
23. Problem elekcji i głosowania
24. Problemy uzgadniania
25. Consensus
26. Uzgadnianie bizantyjskie
27. Niezawodność przetwarzania rozproszonego
28. Komunikacja w środowisku zawodnym
29. Niezawodne detektory uszkodzeń
30. Odtwarzanie stanu systemu rozproszonego

Laboratoria

1. środowisko PVM
2. standard MPI / MPI2 i jego implementacje
3. problematyka konstrukcji procesów rozproszonych i zrównoleglania obliczeń w środowisku rozproszonym, architektury procesów rozprosznych (np. master-slave)
4. komunikacja grupowa
5. mechanizmy rozproszonej synchronizacji procesów (np. bariery, spotkania symetryczne)
6. rozwiązania podstawowych problemów przetwarzania rozproszonego (np. wzajemnego wykluczanie, detekcja zakończenia przetwarzania)

Literatura

• M. Ben-Ari. Podstawy programowania współbieżnego i rozproszonego. WNT, 1990
• Andrew S. Tanenebaum. Rozproszone Systemy Operacyjne. PWN, 1997
• Michel Raynal. Distributed Algorithms and Protocols. John Wiley & Sons, 1988
• Sape Müllender, ed. Distributed Systems. Addison-Wesley, 1993
• Gerard Tel. Introduction to Distributed Algorithms. Cambridge University Press, 1994
• Nancy A. Lynch. Distributed algorithms. Morgan Kaufmann Publishers, 1996
• Randy Chow, Theodore Johnson. Distributed Operating Systems & Algorithms, Addison Wesley Longman, 1997
• Pradeep K. Sinha. Distributed Operating Systems. Concepts and Design, IEEE Computer Society Press, 1997
• J. Brzeziński. Ocena stanu globalnego w systemach rozproszonych, OWN 2001

Moduły

Wykłady

1. Wykład Wprowadzenie (pdf, pdf kolor, pdf notatki) / Laboratorium - Wprowadzenie do środowiska PVM (wersja pdf)
2. Wykład Przetwarzanie rozproszone (pdf, pdf kolor,pdf notatki) / Laboratorium - Pierwsze kroki w PVM (wersja pdf)
3. Wykład Proces rozproszony (pdf, pdf kolor,pdf notatki) / Laboratorium - Komunikacja między procesami (wersja pdf)
4. Wykład Zegary logiczne, złożoność obliczeniowa (pdf,pdf kolor,pdf notatki) / Laboratorium - Zegary logiczne (wersja pdf)
5. Wykład Detekcja zakleszczenia I (pdf,pdf kolor, pdf notatki) / Laboratorium - Komunikacja grupowa (wersja pdf)
6. Wykład Detekcja zakleszczenia II (pdf,pdf kolor, pdf notatki) / Laboratorium - Obliczanie liczby Pi metodą montecarlo (wersja pdf)
7. Wykład Konstrukcja spójnego obrazu stanu globalnego I (pdf,pdf kolor,pdf notatki) / Laboratorium - Łamanie haseł (wersja pdf)
8. Wykład Konstrukcja spójnego obrazu stanu globalnego II (pdf, pdf kolor,pdf notatki) / Laboratorium - Zaawansowane operacje grupowe (wersja pdf)
9. Wykład Detekcja zakończenia I (pdf, pdf kolor, pdf notatki) / Laboratorium - Detekcja zakończenia (wersja pdf)
10. Wykład Detekcja zakończenia II (pdf, pdf kolor, pdf notatki) / Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Microsoft Windows (wersja pdf)
11. Wykład Niezawodność przetwarzania (pdf, pdf kolor, pdf notatki) / Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Linux (wersja pdf)
12. Wykład Niezawodne rozgłaszanie (pdf,pdf kolor,pdf notatki) / Laboratorium - Pierwsze kroki w środowisku MPI (wersja pdf)
13. Wykład Problemy konsensusu (pdf,pdf kolor,pdf notatki) / Laboratorium - Komunikacja kolektywna w środowisku MPI (wersja pdf)

Tylko laboratoria:

1. Laboratorium - Wprowadzenie do środowiska PVM (wersja pdf)
2. Laboratorium - Pierwsze kroki w PVM (wersja pdf)
3. Laboratorium - Komunikacja między procesami (wersja pdf)
4. Laboratorium - Zegary logiczne (wersja pdf)
5. Laboratorium - Komunikacja grupowa (wersja pdf)
6. Laboratorium - Obliczanie liczby Pi metodą montecarlo (wersja pdf)
7. Laboratorium - Łamanie haseł (wersja pdf)
8. Laboratorium - Zaawansowane operacje grupowe (wersja pdf)
9. Laboratorium - Detekcja zakończenia (wersja pdf)
10. Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Microsoft Windows (wersja pdf)
11. Laboratorium - Instalacja środowiska MPI w systemie operacyjnym Linux (wersja pdf)
12. Laboratorium - Pierwsze kroki w środowisku MPI (wersja pdf)
13. Laboratorium - Komunikacja kolektywna w środowisku MPI (wersja pdf)