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. 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 i wdrażają w wybranym środowisku przetwarzania rozproszonego.
Sylabus
Autorzy
- Michał Szychowiak
- Jerzy Brzeziński
Wymagania wstępne
- Systemy operacyjne
- Sieci komputerowe
Zawartość
Wykłady
- Charakterystyka systemów rozproszonych
- Struktura środowiska przetwarzania, topologie
- Kanały komunikacyjne, komunikacja synchroniczna i asynchroniczna
- Środowiska typu GRID, przykładowe zastosowania
- Model formalny procesu sekwencyjnego
- Modele żądań
- Konfiguracja spójna, odcięcie spójne
- Predykaty globalne i ich własności
- Czas wirtualny, zegary logiczne, zegary skalarne
- Środowisko komunikacyjne zachowujące uporządkowanie przyczynowe wiadomości
- Komunikacja grupowa
- Warunki poprawności algorytmów rozproszonych
- Złożoność czasowa i komunikacyjna algorytmów rozproszonych
- Stan globalny systemu (modele, graf stanów, ocena)
- Konstrukcja spójnego obrazu stanu globalnego
- Różne realizacje przetwarzania rozproszonego klient-serwer
- Problem detekcji zakończenia przetwarzania
- Detekcja zakończenia dla synchronicznego modelu przetwarzania
- Detekcja zakończenia dla dyfuzyjnego modelu przetwarzania
- Detekcja zakończenia dla atomowego modelu przetwarzania
- Detekcja zakończenia statycznego
- Detekcja zakończenia dynamicznego
- Problem elekcji i głosowania
- Problemy uzgadniania
- Consensus
- Uzgadnianie bizantyjskie
- Niezawodność przetwarzania rozproszonego
- Komunikacja w środowisku zawodnym
- Niezawodne detektory uszkodzeń
- Odtwarzanie stanu systemu rozproszonego
Laboratoria
- środowisko PVM
- standard MPI / MPI2 i jego implementacje
- problematyka konstrukcji procesów rozproszonych i zrównoleglania obliczeń w środowisku rozproszonym, architektury procesów rozprosznych (np. master-slave)
- komunikacja grupowa
- mechanizmy rozproszonej synchronizacji procesów (np. bariery, spotkania symetryczne)
- 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ład Wprowadzenie / Laboratorium - Wprowadzenie do środowiska PVM (wersja pdf)
- Wykład Przetwarzanie rozproszone / Laboratorium - Pierwsze kroki w PVM (wersja pdf)
- Wykład Proces rozproszony / Laboratorium - Komunikacja między procesami (wersja pdf)
- Wykład Zegary logiczne, złożoność obliczeniowa / Laboratorium - Zegary logiczne (wersja pdf)
- Wykład Detekcja zakleszczenia I / Laboratorium - Komunikacja grupowa (wersja pdf)
- Laboratorium - Obliczanie liczby Pi metodą montecarlo (wersja pdf)
- Wykład Konstrukcja spójnego obrazu stanu globalnego I / Laboratorium - Łamanie haseł (wersja pdf)
- Wykład Konstrukcja spójnego obrazu stanu globalnego II / Laboratorium - Zaawansowane operacje grupowe (wersja pdf)
- Wykład Detekcja zakończenia I / Laboratorium - Detekcja zakończenia (wersja pdf)
- Wykład Detekcja zakończenia II
- Wykład Niezawodność przetwarzania
- Wykład Niezawodne rozgłaszanie
- Wykład Problemy konsensusu
Tylko laboratoria:
- Laboratorium - Wprowadzenie do środowiska PVM (wersja pdf)
- Laboratorium - Pierwsze kroki w PVM (wersja pdf)
- Laboratorium - Komunikacja między procesami (wersja pdf)
- Laboratorium - Zegary logiczne (wersja pdf)
- Laboratorium - Komunikacja grupowa (wersja pdf)
- Laboratorium - Obliczanie liczby Pi metodą montecarlo (wersja pdf)
- Laboratorium - Łamanie haseł (wersja pdf)
- Laboratorium - Zaawansowane operacje grupowe (wersja pdf)
- Laboratorium - Detekcja zakończenia (wersja pdf)
