Seminarium: Systemy Rozproszone
6 października 2005, godzina 12:15,
sala
Synchronizacja pomiędzy procesami jest jednym z kluczowych problemów w systemach rozproszonych. Zwykle chcemy mieć określone gwarancje co do kolejności wykonywania pewnych czynności na danym zbiorze maszyn czy też niepodzielności niektórych operacji nawet w obecności awarii lub błędów komponentów wchodzących w skład systemu. Przykładów jest mnóstwo. Warto wymienić choćby zapewnienie aby modyfikacje bazy danych zreplikowanej na wielu maszynach odbywały się wszędzie w tej samej kolejności, czy porządkowanie "post"-ów na rozproszonych grupach dyskusyjnych tak, aby u każdego użytkownika odpowiedź pojawiała się zawsze po pytaniu, niezależnie od tego, na którym serwerze dany post został wysłany.
Najczęściej stosowanym rozwiązaniem są algorytmy używające różnych wariacji zegarów logicznych zaprezentowanych już bardzo dawno temu przez Leslie'go Lamport'a. Mają one tę cechę, że kolejne zdarzenia porządkowane są w zależności od wartości pewnych liczników zliczających (być może inne) zdarzenia w systemie. Liczniki te mogą być uaktualniane w momencie wymiany komunikatów pomiędzy maszynami. Zaletą takiego rozwiązania jest brak konieczności odwoływania się do globalnego czasu. Do wad należy zaliczyć przede wszystkim znaczną komplikację takich algorytmów w porównaniu z sytuacją, gdyby jednak globalny czas był dostępny. Dodatkowo w niektórych wypadkach są niewystarczające, ponieważ użytkownicy, przyzwyczajeni do naturalnego pojęcia czasu, żądają go od systemu.
Normalną konsekwencją było opracowanie rozmaitych algorytmów służących do synchronizacji czasu fizycznego w systemach rozproszonych. Łatwo jest zauważyć, że zadanie to jest bardzo trudne, jeśli chcemy osiągnąć zadowalającą dokładność. Jeśli dodatkowo weźmiemy pod uwagę fakt, że nasz system może składać się z ogromnej ilości maszyn, można w ogóle zacząć się zastanawiać nad zasadnością zajmowania się tym problemem. Okazuje się jednak, że jeśli pogodzimy się z faktem pewnej niedokładności, to globalny czas nie tylko może być dostępny dla użytkowników jako właściwość systemu, ale także można zaprojektować nowe, ciekawe algorytmy rozwiązujące pewne inne problemy.
Podczas prezentacji chciałbym przedstawić badania, które prowadziłem na Vrije Universiteit w Amsterdamie w ramach przygotowywania pracy magisterskiej dotyczącej synchronizacji czasu w dużych, skalowalnych systemach rozproszonych. Opowiem więc generalnie o obecnym podejściu do synchronizacji czasu i problemach z nim związanych. Dalej przedstawię tzw. epidemic protocols używane m.in. do bardzo szybkiej propagacji informacji w takich systemach. Wreszcie, zaprezentuję wyniki i opowiem trochę o samych badaniach. Na koniec, jeśli będzie zainteresowanie, opiszę studia w Amsterdamie, ofertę dydaktyczną, warunki życia stypendysty i oczywiście wspomnę o tzw. "życiu towarzyskim", z którego Amsterdam słynie.
Serdecznie zapraszam,
Konrad Iwanicki.