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