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

Autor sylabusa

• Dr hab. inż. Jerzy Brzeziński, prof. nadzw. Politechniki Poznańskiej
• E-mail: Jerzy.Brzeziński@cs.put.poznan.pl

Autorzy kursu

• Kurs został przygotowany przez zespół pracowników Instytutu Informatyki Politechniki Poznańskiej pod kierunkiem dr hab. inż. Jerzego Brzezińskiego, prof. nadzw. PP, w składzie: dr inż. Michał Sajkowski, mgr inż. Jacek Kobusiński oraz mgr inż. Arkadiusz Danilecki.

Wymagania wstępne

• Znajomość tematyki omawianej w ramach przedmiotu Systemy operacyjne
• Podstawowe wiadomości z zakresu siec komputerowych
• Laboratoria wymagają znajomości języka C. Przygotowanie do pracy omawianych środowisk MPI oraz PVM wymaga podstawowych umiejętności związanych z konfiguracją i zarządzaniem systemu.

Zawartość

• Wykłady:

• Pierwszą część kursu stanowi moduł wprowadzający w tematykę przetwarzania rozproszonego (41). Wykład rozpocznie się od krótkiego wprowadzenia, którego celem będzie zapoznanie słuchacza z bieżącym stanem wiedzy w tej dziedzinie. Następnie przedstawione zostaną proste definicje dotyczące środowiska przetwarzania. W kolejnych punktach wykładu przedstawione zostaną pewne reprezentatywne środowiska przetwarzania rozproszonego. Pierwszym takim środowiskiem będzie Internet. Przedstawiona zostanie jego krótka historia i obecne trendy rozwoju. Następnie krótko scharakteryzowane zostanie środowisko typu GRID. W kolejnym punkcie wykładu opisane zostaną popularne obecnie projekty nazywane potocznie @HOME. Jako przykłady posłużą projekty Seti@HOME, CureCancer, FightAnthrax. Na zakończenie omówiony zostanie projekt środowiska rozproszonego wyszukiwarki internetowej Google.

• Celem kolejnej części kursu, składającej się z dwóch modułów (56+36) będzie zapoznanie słuchacza z podstawowymi pojęciami i problemami związanymi z przetwarzaniem rozproszonym. Wykład obejmie omówienie m. in. definicji procesu sekwencyjnego, komunikatu, kanału komunikacyjnego czy też stanu kanału. W dalszej części wykładu omówione zostaną różnego rodzaju operacje komunikacyjne, a także scharakteryzowane zostaną rodzaje komunikacji. Student zapozna się także z formalnym modelem procesu sekwencyjnego. Zdefiniowane zostanie pojęcie zdarzenia i podane zostaną definicje różnych ich rodzajów. Kolejnym tematem który zostanie poruszony będzie pojęcie warunku uaktywnienia i definicje z tym związane. Przedstawione zostaną klasyczne modele żądań oraz omówione zostaną ich definicje formalne i własności, a także zaprezentowana zostanie w sposób graficzny ich główna idea.

Następnie przedstawiona będzie definicja procesu rozproszonego, wykonania, globalnego stanu spójnego czy też historii realizacji. Następnie zdefiniowana i omówiona zostanie relacja poprzedzania zdarzeń, a także zaprezentowane i omówione zostaną diagramy przestrzenno-czasowe. Przedstawione zostaną pojęcia przetwarzania niedeterministycznego i grafu stanów osiągalnych. Przedostatnim tematem poruszonym w trakcie tego wykładu będzie mechanizm monitora procesu. Na zakończenie krótko omówiona zostanie ujednolicona konwencja zapisu algorytmów, które będą prezentowane na kolejnych wykładach.

• Trzecia część kursu (?) ma na celu zaznajomienie studenta z pojęciem zegara logicznego, scharakteryzowanie różnych rodzajów kanałów komunikacyjnych, a także przedstawienie analizy poprawności i złożoności algorytmów rozproszonych. Przedstawione zostaną dwa typy zegarów logicznych tzw. zegary skalarne i wektorowe oraz pojęcia z tym związane. Następnie zaprezentowane i omówione zostaną kanały komunikacyjne FIFO i typu FC. Dla każdego z omawianych mechanizmów przedstawiony zostanie przykładowy algorytm zawierający jego implementację. Zdefiniowane zostaną także pojęcia takie, jak rząd funkcji, czy też funkcja kosztu. Pojęcia te zostaną wykorzystane następnie przy omawianiu złożoności komunikacyjnej i czasowej algorytmów rozproszonych. Na zakończenie przedstawione zostaną warunki poprawności algorytmu rozproszonego.

• Tematyka czwartej części kursu, składająca się z dwóch modułów (51+32), związana jest z problematyką detekcji zakleszczenia. Wykład obejmie omówienie podstawowych pojęć związanych z przedstawianą tematyką. Przedstawione zostaną definicje zakleszczenia dla różnych modeli żądań. Następnie omówiona zostanie klasyfikacja problemów detekcji zakończenia. Przedstawione zostanie sześć przykładowych algorytmów detekcji zakleszczenia: dla modeli OR, AND, algorytmy detekcji zakleszczenia w środowisku synchronicznym i asynchronicznym dla modelu k spośród r, dwufazowy algorytm detekcji zakleszczenia i na koniec algorytm detekcji zakleszczenia dla modelu predykatowego.

• Kolejna część kursu składa się z dwóch modułów () i poświęcona jest problematyce konstrukcji spójnego obrazu stanu globalnego. Omówione zostaną podstawowe pojęcia związane z przedstawianą tematyką, takie jak konfiguracja, konfiguracja spójna, odcięcie, linia odcięcia, predykaty globalne, modele stanów globalnych. Pokazane zostaną relacje między tymi pojęciami. Wyjaśnione zostanie znaczenie problemu wyznaczania stanu globalnego oraz przyczyny dla których jest to problem nietrywialny. Zostanie omówiona koncepcja konstrukcji spójnego obrazu stanu globalnego przy przyjęciu pewnych dodatkowych, upraszczających założeń. Przedstawione też będą następujące algorytmy: algorytm Chandy-Lamporta dla kanałów FIFO, algorytm Matterna stosujący zegary wektorowe, Lai-Yang dla kanałów non-FIFO, algorytm kolorujący procesy i wiadomości, oraz dwa algorytmy dla kanałów typu FC (Chandy-Lamporta i stosujący znaczniki BF i FF). Dla niektórych algorytmów zostanie omówiona ich złożoność czasowa oraz dowiedziona ich poprawność.

• Szósta część kursu, składająca się z dwóch modułów(), zajmuje się tematyką detekcji zakończenia. Wykład obejmie przedstawienie przykładów ilustrujących potrzebę problemy detekcji zakończenia w systemach rozproszonych (zakończenie sortowania rozproszonego oraz algorytm Matterna konstrukcji spójnego obrazu stanu globalnego), następnie różne definicje zakończenia (zarówno nieformalną jak i formalną, a także definicja klasyczna zakończenia), pojęcia zakończenia dynamicznego i statycznego i relacje między nimi, zagadnienia związane z detekcją zakończenia w różnych modelach przetwarzania, takich jak model synchroniczny i dyfuzyjny. Student zapozna się również z algorytmami detekcji zakończenia Dijkstry, Feijena, van Gastarena, algorytmem Dijkstry-Scholtena oraz algorytmem Misry dla systemów asynchronicznych,

a także z detekcją zakończenia w atomowym modelu przetwarzania: algorytmem z wykorzystaniem liczników wiadomości, jednofazowy algorytm detekcji zakończenia, wektorowy algorytm detekcji zakończenia. Przedstawione zostaną również algorytmy detekcji zakończenia statycznego oraz dynamicznego. Zostaną również pokazane dowody poprawności tych algorytmów oraz uwagi na temat ich złożoności obliczeniowej.

• Siódma część kursu () ma na celu wprowadzenie do tematyki przetwarzania rozproszonego w środowisku zawodnym. Obejmie ona omówienie podstawowych definicji związanych z niezawodnością, w tym pojęcia awarii, błędu i wady oraz klasy awarii. Następnie wprowadzone zostaną precyzyjne definicje mechanizmów (abstrakcji) kanałów komunikacyjnych o różnych właściwościach. W kontekście niezawodności scharakteryzowane zostaną też podstawowe modele systemów rozproszonych: model asynchroniczny, synchroniczny i częściowo synchroniczny. W kolejnym punkcie zaprezentowany będzie mechanizm detektora awarii. Przedstawione zostaną podstawowe klasy detektorów i relacje pomiędzy poszczególnymi klasami, wybrane metryki służące do oceny detektorów awarii, oraz implementacje detektorów awarii klas P, P. Na zakończenie omówiony będzie problem elekcji w środowisku zawodnym i jego związek z detektorami awarii.

• Celem przedostatniej części kursu () jest prezentacja zagadnień związanych z implementacją niezawodnej komunikacji w zawodnym środowisku rozproszonym. Wykład obejmie omówienie abstrakcyjnych mechanizmów rozgłaszania wiadomości, takich jak: podstawowe rozgłaszanie niezawodne (ang. best-effort), zgodne rozgłaszanie niezawodne (ang. regular reliable broadcast), jednolite rozgłaszanie niezawodne (ang. uniform reliable broadcast) i probabilistyczne rozgłaszanie niezawodne (ang. probabilistic reliable broadcast). Przedstawione zostaną wybrane algorytmy implementujące wspomniane operacje rozgłaszania wiadomości, w tym: algorytm podstawowego rozgłaszania niezawodnego pasywny i aktywny, algorytmy zgodnego rozgłaszania niezawodnego z potwierdzeniami od wszystkich i z potwierdzeniami od większości, aktywny i pasywny algorytm probabilistycznego rozgłaszania niezawodnego, algorytmy zgodnego rozgłaszania niezawodnego z przyczynowym i globalnym uporządkowaniem wiadomości.

• Ostatnia część kursu () obejmuje tematykę konsensusu i jego wykorzystania w systemach rozproszonych. Wykład obejmie omówienie różnych problemów decyzyjnych oraz konsensus jako przykład tego rodzaju problemów. Pokazana jest niemożliwość rozwiazania konsensusu w asynchronicznym środowisku przetwarzania, jeżeli choć jeden proces może ulec awarii. Omówione zostaną problemy konsensusu (podstawowego), konsensusu (jednolitego), konsensusu probabilistycznego i algorytmy je rozwiązujące, takie jak algorytmy rozgłoszeniowy oraz hierarchiczny dla konsensusu podstawowego. Wyjaśnione zostanie na czym polega ważność tego problemu oraz relacje z innymi zagadnieniami pojawiającymi się w systemach rozproszonych.

• Laboratoria:

• Pierwszą część zajęć laboratoryjnych kursu stanowią dziewięć moduły (9 godz.) poświęcone implementacji algorytmów rozproszonych za pomocą biblioteki PVM. Pierwszym zagadnieniem poruszonym w ramach laboratoriów będzie przygotowanie środowiska PVM do pracy. Przedstawiona zostanie podstawowa funkcjonalność biblioteki PVM. W ramach ćwiczeń pokazane zostaną programy demonstrujące wybraną użyteczność biblioteki PVM, a także implementacje algorytmów wyliczania liczby $\mathrm{\Pi }$ metodą Monte-Carlo, łamania haseł, zegarów logicznych i detekcji zakończenia przetwarzania.

• Drugą część zajęć laboratoryjnych kursu stanowią cztery moduły () przedstawiające alternatywne wobec PVM środowisko MPI. W ramach laboratorium przedstawiona zostanie instalacja i konfiguracja środowiska oraz wybrana część jego funkcjonalności.

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)