Przetwarzanie rozproszone
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
Typ zajęć:
- Wykład (30 godz.) + laboratorium (30 godz.)
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 rozproszonego wzajemnego wykluczania
- Algorytm Lamporta
- Algorytm Ricarta-Arawali
- Algorytm Carvallo-Roucairola
- Algorytm Suzuki-Kasami
- 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
- Samostabilizacja
- Laboratoria:
- środowisko PVM
- standard MPI / MPI2 i jego implementacje
- standard CORBA i jego implementacje
- programowanie rozproszone w standardzie Ada95
- 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
