Przetwarzanie rozproszone: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Szopen (dyskusja | edycje)
1922 edycje
Szopen (dyskusja | edycje)
1922 edycje
Nie podano opisu zmian
 
(Nie pokazano 53 wersji utworzonych przez 3 użytkowników)
Linia 4: Linia 4:
== Opis ==
== 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.
Celem przedmiotu jest przedstawienie podstawowych modeli i problemów przetwarzania rozproszonego oraz przykładów ich zastosowań.  
 
Wykład wprowadza podstawowe pojęcia i modele przetwarzania rozproszonego: formalny model środowiska i procesu (algorytmu) rozproszonego, analizę aktywności i warunki uaktywnienia procesów, klasyczne modele żądań, relację poprzedzania, diagramy przestrzenno-czasowe, grafy stanów osiągalnych, niedeterminizm przetwarzania, spójność obrazu stanu globalnego, predykaty globalne i ich własności, skalarne i wektorowe zegary logiczne, warunki poprawności algorytmów, złożoność czasową i komunikacyjną. Omawiane są następnie zagadnienia komunikacji zachowującej uporządkowanie wiadomości, konstrukcji spójnego obrazu stanu globalnego, detekcji zakleszczenia rozproszonego  oraz detekcji zakończenia przetwarzania rozproszonego. Wreszcie przedstawiona jest problematyka związana z niezawodnością przetwarzania w zawodnym środowisku rozproszonym, w tym zagadnienia: modelowania i klasyfikacji awarii, konstrukcji niezawodnych kanałów komunikacyjnych, realizacji detektorów awarii, niezawodnej komunikacji grupowej oraz konsensusu rozproszonego i jego zastosowań. Laboratorium pozwala nabyć praktyczne umiejętności  w konstrukcji i implementacji aplikacji rozproszonych w przykładowym środowisku. W ramach laboratoriów studenci konfrontują uzyskane wiadomości z praktyczną implementacją algorytmów rozproszonych, projektują i realizują algorytmy rozproszone w wybranym środowisku przetwarzania rozproszonego.


== Sylabus ==
== Sylabus ==


=== Autor sylabusa ===
=== Autor ===
* Dr hab. inż. Jerzy Brzeziński, prof. nadzw. Politechniki Poznańskiej
* Jerzy Brzeziński — Politechnika Poznańska
* 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 ===
=== Wymagania wstępne ===
* Znajomość tematyki omawianej w ramach przedmiotu ''Systemy operacyjne''
* Znajomość tematyki omawianej w ramach przedmiotu ''Systemy operacyjne''
* Podstawowe wiadomości z zakresu siec komputerowych
* Podstawowe wiadomości z zakresu sieci 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.
* Laboratoria wymagają znajomości języka C. Przygotowanie do pracy w omawianych środowiskach MPI oraz PVM wymaga podstawowych umiejętności związanych z konfiguracją i zarządzaniem systemem.


=== Zawartość ===
=== Zawartość ===
* '''Wykłady:'''  
==== Wykłady ====
 
* Moduł 1 - ''Wprowadzenie'' (2 godz.). W ramach modułu dotyczącego wprowadzenia do przetwarzania rozproszonego prezentowane są następujące zagadnienia: podstawowe definicje (węzły, łącza komunikacyjne i ich właściwości, topologia przetwarzania), charakterystyka środowiska przetwarzania rozproszonego, przykłady środowisk rozproszonych (Internet, GRID, projekty ..@Home, takie jak Seti@Home czy CureCancer, Google).
 
* Moduł 2 - ''Przetwarzanie rozproszone'' (2 godz.). W ramach modułu dotyczącego przetwarzania rozproszonego prezentowane są następujące zagadnienia: podstawowe definicje (proces sekwencyjny, komunikaty, kanały komunikacyjne, stan kanału, indywidualne i grupowe operacje komunikacyjne, komunikacja synchroniczna i asynchroniczna), model formalny procesu sekwencyjnego (stan procesu, zdarzenia, funkcja tranzycji), klasy zdarzeń (zdarzenia wysłania i odbioru, zdarzenia wewnętrzne), warunki uaktywnienia (zbiór warunkujący, gotowość zdarzeń), modele żądań (model jednostkowy, model AND, model OR, podstawowy model ''k spośród r'', model OR-AND, dysjunkcyjny model ''k spośród r'', model predykatowy).
 
* Moduł 3 - ''Proces rozproszony'' (2 godz.).  W ramach modułu dotyczącego procesu rozproszonego, prezentowane są następujące zagadnienia: model formalny procesu rozproszonego (stan globalny, zdarzenia, globalna funkcja tranzycji), wykonanie procesu, historia procesu, stany osiągalne, relacja poprzedzania zdarzeń (zdarzenia przyczynowo-zależne i niezależne), diagramy przestrzenno-czasowe, niedeterminizm przetwarzania (przetwarzanie deterministyczne, niedeterministyczne, quasi-deterministyczne), graf stanów osiągalnych, mechanizm monitora procesu, konwencja zapisu algorytmów.
 
* Moduł 4 - ''Czas wirtualny, złożoność algorytmów'' (2 godz.). W ramach modułu dotyczącego czasu wirtualnego i złożoności algorytmów, prezentowane są następujące zagadnienia: zegary logiczne (skalarne i wektorowe oraz algorytmy ich realizacji), niezawodne kanały komunikacyjne (FIFO, typu FC), komunikacja zachowująca przyczynowe uporządkowanie wiadomości, złożoność komunikacyjna i czasowa algorytmów rozproszonych, warunki poprawności algorytmów rozproszonych.
 
* Moduł 5 - ''Detekcja zakleszczenia (1)'' (2 godz.). W ramach pierwszego modułu dotyczącego detekcji zakleszczenia prezentowane są następujące  zagadnienia: pojęcia procesu aktywnego i pasywnego, nieformalna definicja zakleszczenia, klasyfikacja problemów detekcji zakleszczenia (detekcja wystąpienia zakleszczenia, detekcja zakleszczenia procesu, detekcja zakleszczenia zbioru procesów, detekcja maksymalnego zbioru procesów zakleszczonych), algorytmy detekcji zakleszczenia dla różnych modeli żądań (modelu OR, modelu AND, modelu ''k spośród r'' w środowisku synchronicznym).
 
* Moduł 6 - ''Detekcja zakleszczenia (2)'' (2 godz.). W ramach drugiego modułu dotyczącego detekcji zakleszczenia prezentowane są następujące zagadnienia: algorytmy detekcji zakleszczenia w środowisku asynchronicznym dla ''modelu k spośród r'' oraz dla modelu predykatowego.
 
* Moduł 7 - ''Konstrukcja spójnego obrazu stanu globalnego - wprowadzenie'' (2 godz.). W ramach modułu dotyczącego wprowadzenia w problematykę konstrukcji spójnego obrazu stanu globalnego prezentowane są następujące zagadnienia: pojęcia podstawowe (konfiguracja, konfiguracja spójna, odcięcie, odcięcie spójne, linia odcięcia), wybrane predykaty globalne stanu globalnego (''possibly'', ''definitely''), modele stanów globalnych, koncepcja konstrukcji spójnego obrazu stanu globalnego.
 
* Moduł 8 - ''Konstrukcja spójnego obrazu stanu globalnego - algorytmy'' (2 godz.). W ramach modułu dotyczącego algorytmów konstrukcji spójnego obrazu stanu globalnego, prezentowane są następujące algorytmy: algorytm Chandy-Lamporta, algorytm Matterna, algorytm Lai-Yang, algorytm z kolorowaniem procesów i wiadomości, algorytmy dla kanałów FC (algorytm Chandy-Lamporta ze znacznikami typu TF oraz ze znacznikami typu BF i FF).


* 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.  
* Moduł 9 - ''Detekcja zakończenia (1)'' (2 godz.). W ramach pierwszego modułu dotyczącego detekcji zakończenia prezentowane są następujące zagadnienia: przykłady problemów zakończenia (sortowanie rozproszone, algorytm Matterna konstrukcji spójnego obrazu stanu globalnego), definicje formalne zakończenia (zakończenie dynamiczne i statyczne, klasyczna definicja zakończenia), detekcja zakończenia dla synchronicznego modelu przetwarzania oraz dla dyfuzyjnego modelu przetwarzania.


* Celem kolejnego modułu kursu () 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. W następnej części wykładu 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. Na zakończenie przedstawione zostaną klasyczne modele żądań. Omówione zostaną ich definicje formalne i własności, a także zaprezentowana zostanie w sposób graficzny ich główna idea.
* Moduł 10 - ''Detekcja zakończenia (2)'' (2 godz.). W ramach drugiego modułu dotyczącego detekcji zakończenia prezentowane są następujące zagadnienia: algorytmy detekcji zakończenia w atomowym modelu przetwarzania (jednofazowy, wektorowy), algorytmy detekcji zakończenia statycznego i dynamicznego.


* Trzeci moduł kursu (6 godz.) jest poświęcony obiektowym i obiektowo-relacyjnym bazom danych. W ramach tej części kursu zostaną omówione następujące zagadnienia: obiektowy model danych (w tym: przesłanki pojawienia się nowej generacji baz danych, nowe dziedziny zastosowań systemów baz danych wymagające silniejszego i bardziej elastycznego modelu danych niż model relacyjny, podstawowe koncepcje obiektowego modelu danych (możliwość modelowania abstrakcyjnych typów danych, mechanizm dziedziczenia typów danych, konstruktory złożonych typów danych, jawne związki między danymi, hierarchiczne zależności między kolekcjami obiektów oraz mechanizmy polimorfizmu i późnego wiązania), rozwiązania służące do zapewnienia obiektom przechowywanym w bazie danych systemowej tożsamości i trwałości), architektura obiektowych i obiektowo-relacyjnych baz danych, model ODMG, język ODL i OQL, implementacja obiektowych baz danych (w tym: obiektowa architektura klient-serwer, buforowanie obiektów, logiczne i fizyczne identyfikatory obiektów, składowanie obiektów, zarządzanie dużymi obiektami, indeksowanie wyrażeń ścieżkowych, hierarchia ścieżek binarnych, indeksowanie hierarchii rozszerzeń klas, sygnatury zbiorów, indeks RD-drzewo).
* Moduł 11 - ''Niezawodność przetwarzania'' (3 godz.). W ramach modułu dotyczącego niezawodności przetwarzania prezentowane są następujące zagadnienia: pojęcia podstawowe (proces poprawny i niepoprawny, definicje awarii, błędu i wady), klasy awarii procesów (załamania, zaniechania, awarie powtarzalne, awarie dowolne), kanały komunikacyjne (rzetelne, wytrwałe, niezawodne), modele systemów rozproszonych w kontekście niezawodności (synchroniczne, asynchroniczne, częściowo synchroniczne), detektory awarii (definicje formalne, własności, zależności między detektorami), implementacja detektorów awarii klasy P i <math>\Diamond</math>P, elekcja w środowisku zawodnym.
* Czwarty moduł kursu (5 godz.) jest poświęcony systemom multimedialnych baz danych oraz standardowi języka SQL/MM (nowy standard uzupełniający język SQL o biblioteki do obsługi specjalistycznych danych i aplikacji, głównie multimedialnych). W ramach tej części kursu zostaną omówione następujące zagadnienia: specyfika i zastosowania multimedialnych baz danych, modele danych dla multimedialnych baz danych, metadane, standard MPEG-7, techniki wyszukiwania, składowania i prezentacji danych multimedialnych, geneza standardu SQL/MM, podstawowe części standardu SQL/MM poświęcone przetwarzaniu danych tekstowych, przestrzennych i obrazów w bazach danych.
* Piąty moduł kursu (7 godz.) jest poświęcony bazom danych dokumentów XML, jako przykład semistrukturalnych baz danych. W ramach tej części kursu zostaną omówione następujące zagadnienia: typy dokumentów XML i ich wpływ na bazy danych, charakterystyka języków zapytań wykorzystywanych do przetwarzania dokumentów XML, baza danych dokumentów XML i sposoby przechowywania i mechanizmy przetwarzania dokumentów XML, język zapytań XQuery (w roku 2005 język XQuery stał się standardem zatwierdzonym przez W3C), w tym: cechy języka Xquery, składnia, klauzule FOR, LET, WHERE, RETURN, ORDER BY, podzapytania, wyrażenia warunkowe i ilościowe, funkcje, przykłady zastosowań. W dalszej części tego modułu kursu zostaną omówione: charakterystyka innych języków semistrukturalnych baz danych, techniki modyfikacji dokumentów XML, w tym: wymagania dotyczące funkcjonalności języka modyfikacji, prosta wymiana i usuwanie dokumentów XML, DOM API oraz języki deklaratywne (Xupdate i rozszerzenia Xquery).
* Ostatni moduł kursu (5 godz.) jest poświęcony hurtowniom danych. W ramach tej części kursu zostaną omówione następujące zagadnienia: wprowadzenie do problematyki integracji rozproszonych i heterogenicznych baz danych, podstawowa architektura integracji danych oparta o hurtownię danych, oprogramowanie ETL, problem wykrywania zmian w źródłach danych, charakterystyka przetwarzania analitycznego (On-Line Analytical Processing - OLAP), wielowymiarowy model danych (wymiary i fakty), implementacja modelu wielowymiarowego w serwerach relacyjnych (ROLAP) (schemat gwiazdy, płatka śniegu i konstelacja faktów) oraz wielowymiarowych (MOLAP) (implementacja i operatory MOLAP). W dalszej części tego modułu kursu zostaną omówione zagadnienia implementacyjne i efektywność przetwarzania OLAP, w tym: odświeżanie hurtowni danych w czasie jej pracy, wykorzystanie perspektyw zmaterializowanych do implementowania hurtowni, techniki zwiększające efektywność przetwarzania analitycznego, m.in. przepisywanie zapytań w oparciu o perspektywy zmaterializowane, indeksowanie danych przy użyciu różnych struktur, partycjonowanie danych i indeksów, kompresja danych i indeksów, przetwarzanie równoległe w hurtowniach danych oraz metadane opisujące hurtownię.


* '''Laboratoria:'''
* Moduł 12 - ''Mechanizmy rozgłaszania niezawodnego'' (4 godz.). W ramach modułu dotyczącego mechanizmów rozgłaszania niezawodnego prezentowane są następujące zagadnienia: mechanizm podstawowego rozgłaszania niezawodnego, mechanizm zgodnego rozgłaszania niezawodnego (algorytm pasywny, algorytm aktywny), mechanizm jednolitego rozgłaszania niezawodnego (algorytm z potwierdzeniami od wszystkich, algorytm z potwierdzeniami od większości), mechanizm probabilistycznego rozgłaszania niezawodnego (algorytm pasywny, algorytm aktywny), mechanizm zgodnego rozgłaszania niezawodnego z przyczynowym uporządkowaniem wiadomości, mechanizm zgodnego rozgłaszania niezawodnego z globalnym uporządkowaniem wiadomości.


* Pierwszą część zajęć laboratoryjnych kursu stanowią trzy moduły (9 godz.) poświęcone systemom rozproszonych baz danych. Cykl tych trzech ćwiczeń ilustruje fundamentalne zagadnienia związane z projektowaniem i implementacją rozproszonych baz danych, tj. replikowanie danych, zarządzanie transakcjami rozproszonymi z wykorzystaniem protokołu 2PC, techniki optymalizacji zapytań rozproszonych. W ramach tej części kursu zostaną omówione i przećwiczone następujące zagadnienia: dostępu do zdalnej bazy danych za pomocą tzw. łącznika bazy danych, replikowanie danych za pomocą tzw. migawki, parametry migawki definiowane przez użytkownika mające wpływ na jej własności, problem przyrostowego odświeżania migawki, grupa odświeżania jako mechanizm jednoczesnego odświeżania wielu migawek, definicje i podstawowe cechy transakcji rozproszonej, role baz danych biorących udział w transakcji rozproszonej, implementacja protokołu zatwierdzania transakcji rozproszonej (protokół 2-Phase-Commit - 2PC), problemy związane z awariami rozproszonej bazy danych w trakcie zatwierdzania transakcji rozproszonej, procedura odtwarzania transakcji rozproszonej, która uległa awarii (zilustrowane studium przypadku), charakterystyka zapytania rozproszonego i plan jego wykonania, narzędzia Oracle analizy planu wykonania zapytania, studium przypadku obejmujące analizę technik filtrowania danych z tabeli zdalnej, grupowania i sortowania danych z tabeli zdalnej, łączenie tabeli lokalnej i zdalnej, zastosowanie tradycyjnych perspektyw (ang. view) w optymalizacji zapytań rozproszonych, zastosowanie wskazówek optymalizatora kosztowego w optymalizacji zapytań rozproszonych. Wszystkie powyższe problemy są ilustrowane rozwiązaniami i technikami implementowanymi w systemie Oracle9i/10g.
* Moduł 13 - ''Problem konsensusu'' (3 godz.). W ramach modułu dotyczącego problemu konsensusu prezentowane są następujące zagadnienia: konsensus jako przykład problemów uzgadniania, nierozwiązywalność problemu konsensusu w środowisku asynchronicznym, konsensus podstawowy (algorytmy rozgłoszeniowy, algorytm hierarchiczny), konsensus jednolity (algorytmy rozgłoszeniowy, algorytm hierarchiczny), konsensus probabilistyczny, konsensus a inne problemy (realizacja mechanizmu zgodnego rozgłaszania niezawodnego z globalnym uporządkowaniem wiadomości za pomocą mechanizmu konsensusu).
* Drugą część zajęć laboratoryjnych kursu stanowią trzy moduły (7 godz.) poświęcone systemom obiektowych baz danych. Cykl tych trzech ćwiczeń ilustruje podstawowe zagadnienia związane z implementacją, programowaniem i użytkowaniem obiektowych baz danych. W ramach tej części kursu zostaną omówione i przećwiczone następujące zagadnienia: charakterystyka i instalacja systemu zarządzania obiektową bazą danych (SZOBD) db4o razem ze środowiskiem programistycznym pozwalającym na tworzenie oprogramowania z nim współpracującego (db4o jest to system, pracujący na platformach Java i .NET, pozwalający na bezpośrednie składowanie obiektów w bazach danych; db4o jest rozpowszechniany bezpłatnie na licencji GPL oraz płatnie na licencji przeznaczonej dla zastosowań komercyjnych), konfiguracja środowiska Eclipse do współpracy z db4o, tworzenie nowego projektu, współpracującego z db4o, architektury aplikacji, jakie można zbudować w oparciu o SZOBD db4o, interfejsy i metody bibliotek SZOBD db4o pozwalające na wykonywanie podstawowych operacji na obiektach składowanych w obiektowej bazie danych, takich jak: zapisywanie obiektów do bazy danych, odszukiwanie i odczytywanie obiektów z bazy danych, modyfikacja obiektów w bazie danych, usuwanie obiektów z bazy danych. W dalszej części tego modułu kursu zostaną omówione zagadnienia dotyczące złożonych, dynamicznych struktur danych, w tym: sposoby zapisu, wyszukiwania, odczytu, modyfikacji i usuwania złożonych struktur danych.
 
* Trzecia część zajęć laboratoryjnych kursu stanowią trzy moduły (7 godz.) poświęcone systemom obiektowo - relacyjnych baz danych. Cykl tych trzech ćwiczeń ilustruje zagadnienia związane z programowaniem i użytkowaniem obiektowo- relacyjnych baz danych. W ramach tej części kursu zostaną omówione i przećwiczone następujące zagadnienia: różnice pomiędzy systemem zarządzania obiektowo-relacyjną bazą danych a SZOBD i systemem zarządzania relacyjną bazą danych, tworzenie typów obiektowych i ich instancji, składowanie obiektów w bazie danych (w tym: tworzenie typów obiektowych, składowanie obiektów), polecenia języka SQL pozwalającą na przeszukiwanie obiektów (w tym: deklaracja metod i konstruktorów, programowanie i implementacja metod i konstruktorów, aktywowanie metod, zapytania do atrybutów obiektów), posługiwanie się typami referencyjnymi (w tym: nawigowanie po referencjach, referencje puste i wiszące), inne obiekty o złożonej strukturze tj. kolekcje wartości, dwa rodzaje kolekcji: tablice o zmiennej długości (w tym: sposób, w jaki mogą być wykorzystywane z poziomu SQL i z poziomu PL/SQL) oraz zagnieżdżone tabele (w tym: różnice pomiędzy obydwoma rodzajami kolekcji, cechy charakterystyczne tabel zagnieżdżonych oraz praca z tym typem kolekcji zarówno z poziomu SQL, jak i z poziomu PL/SQL), konstrukcja CAST(MULTISET). W dalszej części tego modułu kursu zostaną omówione zagadnienia dotyczące motywacji implementacji pewnych cech modelu obiektowego w modelu relacyjnym, co zaowocowało systemami obiektowo-relacyjnych baz danych. Następnie, omówiona i przećwiczona zostanie składnia poleceń pozwalająca na: tworzenie typów dziedziczących ze zdefiniowanych wcześniej typów obiektowych, przesłanianie istniejących metod, deklarowanie typów i metod abstrakcyjnych, oraz omówiony i przećwiczony zostanie polimorfizm i związane z nim dynamiczne wiązanie metod, oraz sposób wykorzystania tych cech przy konstrukcji zapytań, w tym: operatory TREAT i IS OF pozwalające na wykonywanie zapytań do tabel przechowujących obiekty różnych podtypów.
==== Laboratoria ====
* Czwarta część zajęć laboratoryjnych kursu (2 godz.) dotyczy systemów multimedialnych baz danych. Ćwiczenie to ilustruje zagadnienia związane z programowaniem i użytkowaniem multimedialnych baz danych. W ramach tej części kursu zostaną omówione i przećwiczone następujące zagadnienia: możliwości przetwarzania danych multimedialnych wprowadzonych przez standard SQL/MM (w tym: część standardu, która dotyczy przetwarzania obrazów), ładowanie obrazów do bazy danych, odczytywanie ich parametrów, wykonywanie zapytań typu Content Based Retrieval i modyfikowanie obrazów zapisanych w bazie danych.
 
* Ostatnią część zajęć laboratoryjnych kursu stanowią trzy moduły (5 godz.) poświęcone systemom semistrukturalnych baz danych. Cykl tych trzech ćwiczeń ilustruje zagadnienia związane z programowaniem i użytkowaniem baz danych dokumentów XML. W ramach tej części kursu zostaną omówione i przećwiczone następujące zagadnienia: charakterystyka przykładowej bazy danych dokumentów XML – dbXML, wykonywanie zapytań Xpath, dostęp do bazy danych dbXML za pomocą WWW, duże kolekcje dokumentów i indeksy, zapytania dotyczące dokumentów umieszczonych w repozytorium XML oraz modyfikacje takich dokumentów.
* Pierwszą część zajęć laboratoryjnych kursu stanowi dziewięć modułów (20 godz.) poświęconych 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 <math>\Pi</math> metodą Monte-Carlo, łamania haseł, zegarów logicznych i detekcji zakończenia przetwarzania.  
 
* Drugą część zajęć laboratoryjnych kursu stanowią cztery moduły (10 godz.) przedstawiające alternatywne wobec PVM środowisko MPI. W ramach laboratorium przedstawiona zostanie instalacja i konfiguracja środowiska oraz wybrana część jego funkcjonalności.


=== Literatura ===
=== Literatura ===
* M. Ben-Ari. Podstawy programowania współbieżnego i rozproszonego. WNT, 1990
'''Literatura podstawowa'''
* Andrew S. Tanenebaum. Rozproszone Systemy Operacyjne. PWN, 1997
 
* Michel Raynal. Distributed Algorithms and Protocols. John Wiley & Sons, 1988
# M. Ben-Ari, ''Podstawy programowania współbieżnego i rozproszonego'', WNT, 1990
* Sape Müllender, ed. Distributed Systems. Addison-Wesley, 1993
# Brzeziński J. Ocena stanu globalnego w systemach rozproszonych, OWN 2001
* Gerard Tel. Introduction to Distributed Algorithms. Cambridge University Press, 1994
# Guerraoui R., Rodrigues L. Introduction to Reliable Distributed Programming, Springer-Verlag, 2006
* Nancy A. Lynch. Distributed algorithms. Morgan Kaufmann Publishers, 1996
# Lynch N. A. Distributed algorithms, Morgan Kaufmann Publishers, 1996
* Randy Chow, Theodore Johnson. Distributed Operating Systems & Algorithms, Addison Wesley Longman, 1997
# Müllender S., ed. Distributed Systems, Addison-Wesley, 1993
* Pradeep K. Sinha. Distributed Operating Systems. Concepts and Design, IEEE Computer Society Press, 1997
# Tel G. Introduction to Distributed Algorithms, Cambridge University Press, 1994
* J. Brzeziński. Ocena stanu globalnego w systemach rozproszonych, OWN 2001
 
 
'''Literatura uzupełniająca'''
# Attiya H., Welch J. Distributed computing. Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
# Chow R., Johnson T. Distributed Operating Systems & Algorithms, Addison Wesley Longman, 1997
# Garg K. V.: Principles of Distributed Systems, Kluwer Academic Publishers, 1996
# Raynal M. Distributed Algorithms and Protocols, John Wiley & Sons, 1988
# Sinha P. K.. Distributed Operating Systems. Concepts and Design, IEEE Computer Society Press, 1997
# Tanenbaum A. S.: Distributed Systems Principles and Paradigms, Prentice Hall 2002
# Tanenbaum A. S. Rozproszone Systemy Operacyjne, PWN, 1997


==Moduły==
==Moduły==
===Wykłady===
Podstawową postacią materiałów dydaktycznych są wykłady w postaci flash.
# Wykład [[pr-1st-1.1-m01-toc|Wprowadzenie]] ([[media:pr-1st-1.1-m01-print-bw.pdf|pdf]], [[media:pr-1st-1.1-m01-print-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-m01-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m01_lab|Wprowadzenie do środowiska PVM]] [[media:pr-1st-1.1-m01-lab.pdf|(wersja pdf)]]
* [[Informacja o autorach kursu PR|Informacja o autorach kursu]]; [[media:Pr-1st-1.1-m0.2.pdf|PDF]]
# Wykład [[pr-1st-1.1-m02-toc|Przetwarzanie rozproszone]] ([[media:pr-1st-1.1-m02-print-bw.pdf|pdf]], [[media:pr-1st-1.1-m02-print-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-m02-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m02_lab|Pierwsze kroki w PVM]] [[media:pr-1st-1.1-m02-lab.pdf|(wersja pdf)]]
* [[Literatura do przedmiotu PR|Literatura do przedmiotu PR]]; [[media:PR-1st-1.1-m0.3.pdf|PDF]]
# Wykład [[pr-1st-1.1-m03-toc|Proces rozproszony]] ([[media:pr-1st-1.1-m03-print-bw.pdf|pdf]], [[media:pr-1st-1.1-m03-print-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-m03-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m03_lab|Komunikacja między procesami]] [[media:pr-1st-1.1-m03-lab.pdf|(wersja pdf)]]
 
# Wykład [[pr-1st-1.1-m04-toc|Zegary logiczne, złożoność obliczeniowa]] ([[media:pr-1st-1.1-m04-print-bw.pdf|pdf]],[[media:pr-1st-1.1-m04-print-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-m04-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m04_lab|Zegary logiczne]] [[media:pr-1st-1.1-m04-lab.pdf|(wersja pdf)]]
Uwaga! Wersje w flashu najprawdopodobniej nie zostaną zaktualizowane. Zmieni się także format dołączonych plików pdf. Bedą dostępne trzy formaty plików: slajdy kolorowe (4 slajdy na stronie), slajdy czarnobiałe (4 slajdy na stronę) oraz osobno, notatki do slajdów.
# Wykład [[pr-1st-1.1-m05-toc|Detekcja zakleszczenia I]] ([[media:pr-1st-1.1-m05-print-bw.pdf|pdf]],[[media:pr-1st-1.1-m05-print-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-m05-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m05_lab|Komunikacja grupowa]] [[media:pr-1st-1.1-m05-lab.pdf|(wersja pdf)]]
 
# Wykład [[pr-1st-1.1-m06-toc|Detekcja zakleszczenia II]] ([[media:pr-1st-1.1-m06-print-bw.pdf|pdf]],[[media:pr-1st-1.1-m06-print-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-m06-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m06_lab|Obliczanie liczby Pi metodą montecarlo]] [[media:pr-1st-1.1-m06-lab.pdf|(wersja pdf)]]
# Wykład [[pr-1st-1.1-m01-toc|Wprowadzenie (brak aktualizacji)]] ([[media:pr-1st-1.1-w1.tresc-bw.pdf|pdf (zaktualizowane 9.03.2009)]], [[media:pr-1st-1.1-w1.tresc-kolor.pdf|pdf kolor (zaktualizowane 9.03.2009)]], [[media:pr-1st-1.1-w1-notatki.pdf|pdf notatki (zaktualizowane 27.02.2009)]]) / Laboratorium - [[pr_m01_lab|Wprowadzenie do środowiska PVM]] (zaktualizowane 9.03.2009) [[media:pr-1st-1.1-m01-lab.pdf|(wersja pdf)]] (brak aktualizacji) [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w1.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w1.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m07-toc|Konstrukcja spójnego obrazu stanu globalnego I]] ([[media:pr-1st-1.1-m07-print-bw.pdf|pdf]],[[media:pr-1st-1.1-m07-print-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-m07-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m07_lab|Łamanie haseł]] [[media:pr-1st-1.1-m07-lab.pdf|(wersja pdf)]]
# Wykład [[pr-1st-1.1-m02-toc|Przetwarzanie rozproszone (brak aktualizacji)]] ([[media:pr-1st-1.1-w2.tresc-bw.pdf|pdf (zaktualizowane 10.03.2009)]], [[media:pr-1st-1.1-w2.tresc-kolor.pdf|pdf kolor (zaktualizowane 10.03.2009)]],[[media:pr-1st-1.1-w2-notatki.pdf|pdf notatki (zaktualizowane 10.03.2009)]]) / Laboratorium - [[pr_m02_lab|Pierwsze kroki w PVM (brak aktualizacji)]] [[media:pr-1st-1.1-m02-lab.pdf|(wersja pdf) (brak aktualizacji)]] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w2.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w2.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m08-toc|Konstrukcja spójnego obrazu stanu globalnego II]] ([[media:pr-1st-1.1-m08-print-bw.pdf|pdf]], [[media:pr-1st-1.1-m08-print-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-m08-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m08_lab|Zaawansowane operacje grupowe]] [[media:pr-1st-1.1-m08-lab.pdf|(wersja pdf)]]
# Wykład [[pr-1st-1.1-m03-toc|Proces rozproszony (brak aktualizacji)]] ([[media:pr-1st-1.1-w3.tresc-bw.pdf|pdf (zaktualizowane 30.03.2009)]], [[media:pr-1st-1.1-w3.tresc-kolor.pdf|pdf kolor (zaktualizowane 30.03.2009)]],[[media:pr-1st-1.1-w3-notatki.pdf|pdf notatki (zaktualizowane 30.03.2009)]]) / Laboratorium - [[pr_m03_lab|Komunikacja między procesami]] [[media:pr-1st-1.1-m03-lab.pdf|(wersja pdf)]] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w3.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w3.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m09-toc|Detekcja zakończenia I]] ([[media:pr-1st-1.1-m09-print-bw.pdf|pdf]], [[media:pr-1st-1.1-m09-print-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-m09-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m09_lab|Detekcja zakończenia]] [[media:pr-1st-1.1-m09-lab.pdf|(wersja pdf)]]
# Wykład [[pr-1st-1.1-m04-toc|Zegary logiczne, złożoność obliczeniowa (brak aktualizacji)]] ([[media:pr-1st-1.1-w4.tresc-bw.pdf|pdf (zaktualizowane 30.03.2009)]],[[media:pr-1st-1.1-w4.tresc-kolor.pdf|pdf kolor (zaktualizowane 30.03.2009)]],[[media:pr-1st-1.1-w4-notatki.pdf|pdf notatki (zaktualizowane 30.03.2009)]]) / Laboratorium - [[pr_m04_lab|Zegary logiczne]] [[media:pr-1st-1.1-m04-lab.pdf|(wersja pdf)]] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w4.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w4.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m10-toc|Detekcja zakończenia II]] ([[media:pr-1st-1.1-m10-print-bw.pdf|pdf]], [[media:pr-1st-1.1-m10-print-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-m10-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m10_lab|Instalacja środowiska MPI w systemie operacyjnym Microsoft Windows]] [[media:pr-1st-1.1-m10-lab.pdf|(wersja pdf)]]
# Wykład [[pr-1st-1.1-m05-toc|Detekcja zakleszczenia I (brak aktualizacji)]] ([[media:pr-1st-1.1-w5.tresc-bw.pdf|pdf (zaktualizowane 30.03.2009)]],[[media:pr-1st-1.1-w5.tresc-kolor.pdf|pdf kolor (zaktualizowane 30.03.2009)]], [[media:pr-1st-1.1-w5-notatki.pdf|pdf notatki (zaktualizowane 30.03.2009)]]) / Laboratorium - [[pr_m05_lab|Komunikacja grupowa]] [[media:pr-1st-1.1-m05-lab.pdf|(wersja pdf)]] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w5.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w5.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m11-toc|Niezawodność przetwarzania]] ([[media:pr-1st-1.1-m11-print-bw.pdf|pdf]], [[media:pr-1st-1.1-m11-print-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-m11-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m11_lab|Instalacja środowiska MPI w systemie operacyjnym Linux]] [[media:pr-1st-1.1-m11-lab.pdf|(wersja pdf)]]  
# Wykład [[pr-1st-1.1-m06-toc|Detekcja zakleszczenia II (brak aktualizacji)]] ([[media:pr-1st-1.1-w6.tresc-bw.pdf|pdf (zaktualizowane 30.03.2009)]],[[media:pr-1st-1.1-w6.tresc-kolor.pdf|pdf kolor (zaktualizowane 30.03.2009)]], [[media:pr-1st-1.1-w6-notatki.pdf|pdf notatki (zaktualizowane 30.03.2009)]]) / Laboratorium - [[pr_m06_lab|Obliczanie liczby Pi metodą montecarlo]] [[media:pr-1st-1.1-m06-lab.pdf|(wersja pdf)]] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w6.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w6.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m12-toc|Niezawodne rozgłaszanie]] ([[media:pr-1st-1.1-m12-print-bw.pdf|pdf]],[[media:pr-1st-1.1-m12-print-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-m12-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m12_lab|Pierwsze kroki w środowisku MPI]] [[media:pr-1st-1.1-m12-lab.pdf|(wersja pdf)]]  
# Wykład [[pr-1st-1.1-m07-toc|Konstrukcja spójnego obrazu stanu globalnego I]] ([[media:pr-1st-1.1-w7.tresc-bw.pdf|pdf]],[[media:pr-1st-1.1-w7.tresc-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-w7-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m07_lab|Łamanie haseł]] [[media:pr-1st-1.1-m07-lab.pdf|(wersja pdf)]] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w7.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w7.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m13-toc|Problemy konsensusu]] ([[media:pr-1st-1.1-m13-print-bw.pdf|pdf]],[[media:pr-1st-1.1-m13-print-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-m13-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m13_lab|Komunikacja kolektywna w środowisku MPI]] [[media:pr-1st-1.1-m13-lab.pdf|(wersja pdf)]]  
# Wykład [[pr-1st-1.1-m08-toc|Konstrukcja spójnego obrazu stanu globalnego II]] ([[media:pr-1st-1.1-w8.tresc-bw.pdf|pdf]], [[media:pr-1st-1.1-w8.tresc-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-w8-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m08_lab|Zaawansowane operacje grupowe]] [[media:pr-1st-1.1-m08-lab.pdf|(wersja pdf)]] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w8.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w8.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m09-toc|Detekcja zakończenia I]] ([[media:pr-1st-1.1-w9.tresc-bw.pdf|pdf]], [[media:pr-1st-1.1-w9.tresc-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-w9-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m09_lab|Detekcja zakończenia]] [[media:pr-1st-1.1-m09-lab.pdf|(wersja pdf)]] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w9.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w9.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m10-toc|Detekcja zakończenia II]] ([[media:pr-1st-1.1-w10.tresc-bw.pdf|pdf]], [[media:pr-1st-1.1-w10.tresc-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-w10-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m10_lab|Instalacja środowiska MPI w systemie operacyjnym Microsoft Windows]] [[media:pr-1st-1.1-m10-lab.pdf|(wersja pdf)]]  [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w10.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w10.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m11-toc|Niezawodność przetwarzania]] ([[media:pr-1st-1.1-w11.tresc-bw.pdf|pdf]], [[media:pr-1st-1.1-w11.tresc-kolor.pdf|pdf kolor]], [[media:pr-1st-1.1-w11-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m11_lab|Instalacja środowiska MPI w systemie operacyjnym Linux]] [[media:pr-1st-1.1-m11-lab.pdf|(wersja pdf)]]  [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w11.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w11.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m12-toc|Niezawodne rozgłaszanie]] ([[media:pr-1st-1.1-w12.tresc-bw.pdf|pdf]],[[media:pr-1st-1.1-w12.tresc-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-w12-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m12_lab|Pierwsze kroki w środowisku MPI]] [[media:pr-1st-1.1-m12-lab.pdf|(wersja pdf)]]  [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w12.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w12.pytania/quizmaker.html Pytania]
# Wykład [[pr-1st-1.1-m13-toc|Problemy konsensusu]] ([[media:pr-1st-1.1-w13.tresc-bw.pdf|pdf]],[[media:pr-1st-1.1-w13.tresc-kolor.pdf|pdf kolor]],[[media:pr-1st-1.1-w13-notatki.pdf|pdf notatki]]) / Laboratorium - [[pr_m13_lab|Komunikacja kolektywna w środowisku MPI]] [[media:pr-1st-1.1-m13-lab.pdf|(wersja pdf)]]  [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w13.flash/player.html Flash] [http://osilek.mimuw.edu.pl/external/pr/pr-1st-1.1-w13.pytania/quizmaker.html Pytania]


===Tylko laboratoria:===
===Tylko laboratoria:===
*[[media:pr-1st-1.1-extras.tar.gz|Materialy do laboratoriow: przykladowe programy]] w postaci skompresowanego archiwum tar.
# Laboratorium - [[pr_m01_lab|Wprowadzenie do środowiska PVM]] [[media:pr-1st-1.1-m01-lab.pdf|(wersja pdf)]]
# Laboratorium - [[pr_m01_lab|Wprowadzenie do środowiska PVM]] [[media:pr-1st-1.1-m01-lab.pdf|(wersja pdf)]]
# Laboratorium - [[pr_m02_lab|Pierwsze kroki w PVM]] [[media:pr-1st-1.1-m02-lab.pdf|(wersja pdf)]]
# Laboratorium - [[pr_m02_lab|Pierwsze kroki w PVM]] [[media:pr-1st-1.1-m02-lab.pdf|(wersja pdf)]]

Aktualna wersja na dzień 07:53, 21 kwi 2010

Forma zajęć

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

Opis

Celem przedmiotu jest przedstawienie podstawowych modeli i problemów przetwarzania rozproszonego oraz przykładów ich zastosowań.

Wykład wprowadza podstawowe pojęcia i modele przetwarzania rozproszonego: formalny model środowiska i procesu (algorytmu) rozproszonego, analizę aktywności i warunki uaktywnienia procesów, klasyczne modele żądań, relację poprzedzania, diagramy przestrzenno-czasowe, grafy stanów osiągalnych, niedeterminizm przetwarzania, spójność obrazu stanu globalnego, predykaty globalne i ich własności, skalarne i wektorowe zegary logiczne, warunki poprawności algorytmów, złożoność czasową i komunikacyjną. Omawiane są następnie zagadnienia komunikacji zachowującej uporządkowanie wiadomości, konstrukcji spójnego obrazu stanu globalnego, detekcji zakleszczenia rozproszonego oraz detekcji zakończenia przetwarzania rozproszonego. Wreszcie przedstawiona jest problematyka związana z niezawodnością przetwarzania w zawodnym środowisku rozproszonym, w tym zagadnienia: modelowania i klasyfikacji awarii, konstrukcji niezawodnych kanałów komunikacyjnych, realizacji detektorów awarii, niezawodnej komunikacji grupowej oraz konsensusu rozproszonego i jego zastosowań. Laboratorium pozwala nabyć praktyczne umiejętności w konstrukcji i implementacji aplikacji rozproszonych w przykładowym środowisku. W ramach laboratoriów studenci konfrontują uzyskane wiadomości z praktyczną implementacją algorytmów rozproszonych, projektują i realizują algorytmy rozproszone w wybranym środowisku przetwarzania rozproszonego.

Sylabus

Autor

  • Jerzy Brzeziński — Politechnika Poznańska

Wymagania wstępne

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

Zawartość

Wykłady

  • Moduł 1 - Wprowadzenie (2 godz.). W ramach modułu dotyczącego wprowadzenia do przetwarzania rozproszonego prezentowane są następujące zagadnienia: podstawowe definicje (węzły, łącza komunikacyjne i ich właściwości, topologia przetwarzania), charakterystyka środowiska przetwarzania rozproszonego, przykłady środowisk rozproszonych (Internet, GRID, projekty ..@Home, takie jak Seti@Home czy CureCancer, Google).
  • Moduł 2 - Przetwarzanie rozproszone (2 godz.). W ramach modułu dotyczącego przetwarzania rozproszonego prezentowane są następujące zagadnienia: podstawowe definicje (proces sekwencyjny, komunikaty, kanały komunikacyjne, stan kanału, indywidualne i grupowe operacje komunikacyjne, komunikacja synchroniczna i asynchroniczna), model formalny procesu sekwencyjnego (stan procesu, zdarzenia, funkcja tranzycji), klasy zdarzeń (zdarzenia wysłania i odbioru, zdarzenia wewnętrzne), warunki uaktywnienia (zbiór warunkujący, gotowość zdarzeń), modele żądań (model jednostkowy, model AND, model OR, podstawowy model k spośród r, model OR-AND, dysjunkcyjny model k spośród r, model predykatowy).
  • Moduł 3 - Proces rozproszony (2 godz.). W ramach modułu dotyczącego procesu rozproszonego, prezentowane są następujące zagadnienia: model formalny procesu rozproszonego (stan globalny, zdarzenia, globalna funkcja tranzycji), wykonanie procesu, historia procesu, stany osiągalne, relacja poprzedzania zdarzeń (zdarzenia przyczynowo-zależne i niezależne), diagramy przestrzenno-czasowe, niedeterminizm przetwarzania (przetwarzanie deterministyczne, niedeterministyczne, quasi-deterministyczne), graf stanów osiągalnych, mechanizm monitora procesu, konwencja zapisu algorytmów.
  • Moduł 4 - Czas wirtualny, złożoność algorytmów (2 godz.). W ramach modułu dotyczącego czasu wirtualnego i złożoności algorytmów, prezentowane są następujące zagadnienia: zegary logiczne (skalarne i wektorowe oraz algorytmy ich realizacji), niezawodne kanały komunikacyjne (FIFO, typu FC), komunikacja zachowująca przyczynowe uporządkowanie wiadomości, złożoność komunikacyjna i czasowa algorytmów rozproszonych, warunki poprawności algorytmów rozproszonych.
  • Moduł 5 - Detekcja zakleszczenia (1) (2 godz.). W ramach pierwszego modułu dotyczącego detekcji zakleszczenia prezentowane są następujące zagadnienia: pojęcia procesu aktywnego i pasywnego, nieformalna definicja zakleszczenia, klasyfikacja problemów detekcji zakleszczenia (detekcja wystąpienia zakleszczenia, detekcja zakleszczenia procesu, detekcja zakleszczenia zbioru procesów, detekcja maksymalnego zbioru procesów zakleszczonych), algorytmy detekcji zakleszczenia dla różnych modeli żądań (modelu OR, modelu AND, modelu k spośród r w środowisku synchronicznym).
  • Moduł 6 - Detekcja zakleszczenia (2) (2 godz.). W ramach drugiego modułu dotyczącego detekcji zakleszczenia prezentowane są następujące zagadnienia: algorytmy detekcji zakleszczenia w środowisku asynchronicznym dla modelu k spośród r oraz dla modelu predykatowego.
  • Moduł 7 - Konstrukcja spójnego obrazu stanu globalnego - wprowadzenie (2 godz.). W ramach modułu dotyczącego wprowadzenia w problematykę konstrukcji spójnego obrazu stanu globalnego prezentowane są następujące zagadnienia: pojęcia podstawowe (konfiguracja, konfiguracja spójna, odcięcie, odcięcie spójne, linia odcięcia), wybrane predykaty globalne stanu globalnego (possibly, definitely), modele stanów globalnych, koncepcja konstrukcji spójnego obrazu stanu globalnego.
  • Moduł 8 - Konstrukcja spójnego obrazu stanu globalnego - algorytmy (2 godz.). W ramach modułu dotyczącego algorytmów konstrukcji spójnego obrazu stanu globalnego, prezentowane są następujące algorytmy: algorytm Chandy-Lamporta, algorytm Matterna, algorytm Lai-Yang, algorytm z kolorowaniem procesów i wiadomości, algorytmy dla kanałów FC (algorytm Chandy-Lamporta ze znacznikami typu TF oraz ze znacznikami typu BF i FF).
  • Moduł 9 - Detekcja zakończenia (1) (2 godz.). W ramach pierwszego modułu dotyczącego detekcji zakończenia prezentowane są następujące zagadnienia: przykłady problemów zakończenia (sortowanie rozproszone, algorytm Matterna konstrukcji spójnego obrazu stanu globalnego), definicje formalne zakończenia (zakończenie dynamiczne i statyczne, klasyczna definicja zakończenia), detekcja zakończenia dla synchronicznego modelu przetwarzania oraz dla dyfuzyjnego modelu przetwarzania.
  • Moduł 10 - Detekcja zakończenia (2) (2 godz.). W ramach drugiego modułu dotyczącego detekcji zakończenia prezentowane są następujące zagadnienia: algorytmy detekcji zakończenia w atomowym modelu przetwarzania (jednofazowy, wektorowy), algorytmy detekcji zakończenia statycznego i dynamicznego.
  • Moduł 11 - Niezawodność przetwarzania (3 godz.). W ramach modułu dotyczącego niezawodności przetwarzania prezentowane są następujące zagadnienia: pojęcia podstawowe (proces poprawny i niepoprawny, definicje awarii, błędu i wady), klasy awarii procesów (załamania, zaniechania, awarie powtarzalne, awarie dowolne), kanały komunikacyjne (rzetelne, wytrwałe, niezawodne), modele systemów rozproszonych w kontekście niezawodności (synchroniczne, asynchroniczne, częściowo synchroniczne), detektory awarii (definicje formalne, własności, zależności między detektorami), implementacja detektorów awarii klasy P i ◊P, elekcja w środowisku zawodnym.
  • Moduł 12 - Mechanizmy rozgłaszania niezawodnego (4 godz.). W ramach modułu dotyczącego mechanizmów rozgłaszania niezawodnego prezentowane są następujące zagadnienia: mechanizm podstawowego rozgłaszania niezawodnego, mechanizm zgodnego rozgłaszania niezawodnego (algorytm pasywny, algorytm aktywny), mechanizm jednolitego rozgłaszania niezawodnego (algorytm z potwierdzeniami od wszystkich, algorytm z potwierdzeniami od większości), mechanizm probabilistycznego rozgłaszania niezawodnego (algorytm pasywny, algorytm aktywny), mechanizm zgodnego rozgłaszania niezawodnego z przyczynowym uporządkowaniem wiadomości, mechanizm zgodnego rozgłaszania niezawodnego z globalnym uporządkowaniem wiadomości.
  • Moduł 13 - Problem konsensusu (3 godz.). W ramach modułu dotyczącego problemu konsensusu prezentowane są następujące zagadnienia: konsensus jako przykład problemów uzgadniania, nierozwiązywalność problemu konsensusu w środowisku asynchronicznym, konsensus podstawowy (algorytmy rozgłoszeniowy, algorytm hierarchiczny), konsensus jednolity (algorytmy rozgłoszeniowy, algorytm hierarchiczny), konsensus probabilistyczny, konsensus a inne problemy (realizacja mechanizmu zgodnego rozgłaszania niezawodnego z globalnym uporządkowaniem wiadomości za pomocą mechanizmu konsensusu).

Laboratoria

  • Pierwszą część zajęć laboratoryjnych kursu stanowi dziewięć modułów (20 godz.) poświęconych 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 Π metodą Monte-Carlo, łamania haseł, zegarów logicznych i detekcji zakończenia przetwarzania.
  • Drugą część zajęć laboratoryjnych kursu stanowią cztery moduły (10 godz.) przedstawiające alternatywne wobec PVM środowisko MPI. W ramach laboratorium przedstawiona zostanie instalacja i konfiguracja środowiska oraz wybrana część jego funkcjonalności.

Literatura

Literatura podstawowa

  1. M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego, WNT, 1990
  2. Brzeziński J. Ocena stanu globalnego w systemach rozproszonych, OWN 2001
  3. Guerraoui R., Rodrigues L. Introduction to Reliable Distributed Programming, Springer-Verlag, 2006
  4. Lynch N. A. Distributed algorithms, Morgan Kaufmann Publishers, 1996
  5. Müllender S., ed. Distributed Systems, Addison-Wesley, 1993
  6. Tel G. Introduction to Distributed Algorithms, Cambridge University Press, 1994


Literatura uzupełniająca

  1. Attiya H., Welch J. Distributed computing. Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
  2. Chow R., Johnson T. Distributed Operating Systems & Algorithms, Addison Wesley Longman, 1997
  3. Garg K. V.: Principles of Distributed Systems, Kluwer Academic Publishers, 1996
  4. Raynal M. Distributed Algorithms and Protocols, John Wiley & Sons, 1988
  5. Sinha P. K.. Distributed Operating Systems. Concepts and Design, IEEE Computer Society Press, 1997
  6. Tanenbaum A. S.: Distributed Systems Principles and Paradigms, Prentice Hall 2002
  7. Tanenbaum A. S. Rozproszone Systemy Operacyjne, PWN, 1997

Moduły

Podstawową postacią materiałów dydaktycznych są wykłady w postaci flash.

Uwaga! Wersje w flashu najprawdopodobniej nie zostaną zaktualizowane. Zmieni się także format dołączonych plików pdf. Bedą dostępne trzy formaty plików: slajdy kolorowe (4 slajdy na stronie), slajdy czarnobiałe (4 slajdy na stronę) oraz osobno, notatki do slajdów.

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

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)
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Przetwarzanie_rozproszone&oldid=75943”