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 rozproszonego wzajemnego wykluczania
18. Algorytm Lamporta
19. Algorytm Ricarta-Arawali
20. Algorytm Carvallo-Roucairola
21. Algorytm Suzuki-Kasami
22. Problem detekcji zakończenia przetwarzania
23. Detekcja zakończenia dla synchronicznego modelu przetwarzania
24. Detekcja zakończenia dla dyfuzyjnego modelu przetwarzania
25. Detekcja zakończenia dla atomowego modelu przetwarzania
26. Detekcja zakończenia statycznego
27. Detekcja zakończenia dynamicznego
28. Problem elekcji i głosowania
29. Problemy uzgadniania
30. Consensus
31. Uzgadnianie bizantyjskie
32. Niezawodność przetwarzania rozproszonego
33. Komunikacja w środowisku zawodnym
34. Niezawodne detektory uszkodzeń
35. Odtwarzanie stanu systemu rozproszonego
36. Samostabilizacja

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