Seminarium: Systemy Rozproszone
21 marca 2019, godzina 12:15,
sala
U podstaw działania wielu dzisiejszych systemów stoją algorytmy rozproszone. Stanowią one ciekawy i trudny temat, a przy ich projektowaniu i implementacji łatwo popełnić błąd.
Często nieoczywiste jest, czy dany problem w ogóle da się rozwiązać przy pomocy takiego algorytmu. Słynny wynik z 1985 roku, znany między innymi jako FLP theorem mówi, że w całkowicie asynchronicznym systemie, którego poszczególne procesy komunikują się ze sobą poprzez przesyłanie komunikatów i w którym choć jeden proces może przestać działać (tzw. crash failure), nie da się rozwiązać problemu konsensusu. Od tego czasu włożono wiele pracy w próby pełnego scharakteryzowania problemów, które dają się rozwiązać takim algorytmem.
Czym jednak jest "problem"? Co to znaczy "rozwiązać problem algorytmem rozproszonym"? Aby móc się precyzyjnie wyrażać i dowodzić twierdzenia, potrzebujemy pewnych formalnych narzędzi. Podczas mojej prezentacji chciałbym pokazać Wam podstawowy zestaw formalizmów i przykład modelu obliczeń rozproszonych. Kiedy już uda nam się ustalić wspólny język, przedstawię nadzwyczajny wynik łączący obliczalność w modelu rozproszonym z pewnymi obiektami mającymi korzenie w dziedzinie matematyki zwanej Topologią Algebraiczną. Za ten wynik autorzy tytułowej pracy dostali w 2004 roku Nagrodę Gödla.
Zapraszam!
Kamil Braun
Bibliografia: