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

1. Charakterystyka systemów rozproszonych
2. Struktura środowiska przetwarzania, topologie
3. Kanały komunikacyjne, komunikacja synchroniczna i asynchroniczna
4. Środowiska typu GRID, przykładowe zastosowania
5. Model formalny procesu sekwencyjnego
6. Modele żądań
7. Konfiguracja spójna, odcięcie spójne
8. Predykaty globalne i ich własności
9. Czas wirtualny, zegary logiczne, zegary skalarne
10. Środowisko komunikacyjne zachowujące uporządkowanie przyczynowe wiadomości
11. Komunikacja grupowa
12. Warunki poprawności algorytmów rozproszonych
13. Złożoność czasowa i komunikacyjna algorytmów rozproszonych
14. Stan globalny systemu (modele, graf stanów, ocena)
15. Konstrukcja spójnego obrazu stanu globalnego
16. Różne realizacje przetwarzania rozproszonego klient-serwer
17. Problem detekcji zakończenia przetwarzania
18. Detekcja zakończenia dla synchronicznego modelu przetwarzania
19. Detekcja zakończenia dla dyfuzyjnego modelu przetwarzania
20. Detekcja zakończenia dla atomowego modelu przetwarzania
21. Detekcja zakończenia statycznego
22. Detekcja zakończenia dynamicznego
23. Problem elekcji i głosowania
24. Problemy uzgadniania
25. Consensus
26. Uzgadnianie bizantyjskie
27. Niezawodność przetwarzania rozproszonego
28. Komunikacja w środowisku zawodnym
29. Niezawodne detektory uszkodzeń
30. Odtwarzanie stanu systemu rozproszonego

Laboratoria

1. środowisko PVM
2. standard MPI / MPI2 i jego implementacje
3. standard CORBA i jego implementacje
4. programowanie rozproszone w standardzie Ada95
5. problematyka konstrukcji procesów rozproszonych i zrównoleglania obliczeń w środowisku rozproszonym, architektury procesów rozprosznych (np. master-slave)
6. komunikacja grupowa
7. mechanizmy rozproszonej synchronizacji procesów (np. bariery, spotkania symetryczne)
8. 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