Tematy wykładów

• Wstęp:
  • cechy systemów rozproszonych,
  • problem bizantyjskich generałów,
  • motywacje: LAN i WAN, odporność na błędy, przyspieszenie onliczeń,
  • problemy: komunikacja, niejednorodność, programowanie
  • typowe podstawowe zagadnienia: broadcasting, synchronizacja, wybór lidera, termination detection, alokacja zasobów, mutual exclusion, zakleszczenie, pamięć rozproszona,
  • procesy rozproszone a współbieżne
  • model warstwowy komunikacji
• Model obliczeń: procesy lokalne, konfiguracje, przejścia między konfiguracjami, metoda niezmienników, porządki dobrze ufundowane i ich zastosowanie do testowania algorytmów
  częściowy porządek zdarzeń, równoważne obliczenia, zegary logiczne
• Algorytmy komunikacyjne:
  • protokół sliding window, analiza niezmienników, dowód dostarczenia wszystkich pakietów
  • protokół z licznikami,
• Routing:
  • tablice routingu, drzewa rozpinające najkrótszych ścieżek,
  • all pairs shortest path:algorytm Floyda-Warshalla, rozproszona implementacja: Touega, Merlina-Segalla, Chandy-Misra
  • Netchange
  • routing z małymi tablicami : routing hierarchiczny i rozbicie na clustery, drzewo rozpinające i prefix routing, dowod poprawności schematu prefix routing, interval routing na kracie i ringu
• Unikanie zakleszczenia (deadlock):
  • typy deadlocku: store-and-forward, livelock, konfiguracja zakleszczająca
  • graf buforów i bg-kontroler, schematy: dest, hop-so-far
  • orientacje w grafach, acykliczne pokrycia, kontroler oparty na acyklicznych pokryciach
  • rozwiązania niestrukturalne: FC, BC, FS, BS
• Waves, traversals:
  • algorytmy typu wave, typowe zagadnienia redukujace sie do waves
  • algorytm przy ustalonym drzewie rozpinającym, algorytm echo,
• Leader election:
  • algorytmy na ringu, analiza czasu średniego
  • optymalny algorytm na ringu (worst-case)