Samostabilizacja - Self-stabilization

Samostabilizacja to koncepcja odporności na awarie w systemach rozproszonych . Biorąc pod uwagę dowolny stan początkowy, samostabilizujący się system rozproszony znajdzie się w poprawnym stanie po skończonej liczbie kroków wykonawczych .

Na pierwszy rzut oka gwarancja samostabilizacji może wydawać się mniej obiecująca niż bardziej tradycyjne algorytmy odporności na awarie, których celem jest zagwarantowanie, że system zawsze pozostanie w prawidłowym stanie przy pewnych rodzajach zmian stanu. Jednak ta tradycyjna odporność na awarie nie zawsze może zostać osiągnięta. Na przykład nie można tego osiągnąć, gdy system zostanie uruchomiony w niewłaściwym stanie lub zostanie uszkodzony przez intruza. Ponadto, ze względu na ich złożoność, bardzo trudno jest debugować i analizować systemy rozproszone. Dlatego bardzo trudno jest zapobiec osiągnięciu przez system rozproszony nieprawidłowego stanu. Rzeczywiście, niektóre formy samostabilizacji są włączone do wielu nowoczesnych sieci komputerowych i telekomunikacyjnych , ponieważ daje im to możliwość radzenia sobie z błędami, których nie przewidziano w projekcie algorytmu.

Wiele lat po przełomowym artykule Edsgera Dijkstry w 1974 koncepcja ta pozostaje ważna, ponieważ stanowi ważną podstawę dla samozarządzających się systemów komputerowych i systemów odpornych na uszkodzenia . W rezultacie artykuł Dijkstry otrzymał nagrodę 2002 ACM PODC Influential-Paper Award , jedno z najwyższych wyróżnień w społeczności komputerów rozproszonych. Co więcej, po śmierci Dijkstry nagroda została przemianowana i nosi obecnie nazwę Nagroda Dijkstry.

Historia

EW Dijkstra w 1974 r. przedstawił koncepcję samostabilizacji, co skłoniło do dalszych badań w tym zakresie. Jego demonstracja obejmowała prezentację samostabilizujących się algorytmów wzajemnego wykluczania . Pokazał także pierwsze algorytmy samostabilizujące, które nie opierały się na silnych założeniach dotyczących systemu. Niektóre poprzednie protokoły używane w praktyce faktycznie się ustabilizowały, ale tylko przy założeniu istnienia zegara globalnego dla systemu i przy założeniu znanej górnej granicy czasu trwania każdej zmiany systemu. Dopiero dziesięć lat później Leslie Lamport zwrócił uwagę na znaczenie pracy Dijkstry na konferencji w 1983 roku zatytułowanej Symposium on Principles of Distributed Computing, kiedy badacze skierowali swoją uwagę na tę elegancką koncepcję tolerancji błędów. W swoim przemówieniu Lamport stwierdził:

Uważam to za najwspanialsze dzieło Dijkstry, a przynajmniej jego najgenialniejszy opublikowany artykuł. To prawie zupełnie nieznane. Uważam to za kamień milowy w pracy nad odpornością na błędy... Uważam, że samostabilizacja jest bardzo ważnym pojęciem w zakresie tolerancji błędów i jest bardzo żyznym polem badawczym.

Następnie praca Dijkstry została nagrodzona wpływową nagrodą ACM-POPDC, która następnie stała się nagrodą ACM (Association for Computing Machinery) Dijkstra Prize in Distributed Computing przyznawaną na dorocznym sympozjum ACM-POPDC.

Przegląd

Rozprowadzane algorytm jest samo-stabilizujący, jeśli począwszy od dowolnego stanu, to jest gwarantowana zbiegać do legalnego państwa i pozostają w uzasadnionych zbiór stanów później. Stan jest uzasadniony, jeśli począwszy od tego stanu algorytm spełnia swoją specyfikację. Właściwość samostabilizacji umożliwia algorytmowi rozproszonemu odzyskanie sprawności po zwarciu przejściowym, niezależnie od jego natury. Co więcej, algorytm samostabilizujący nie musi być inicjowany, ponieważ w końcu zaczyna działać poprawnie niezależnie od swojego stanu początkowego.

Artykuł Dijkstry, który wprowadza pojęcie samostabilizacji, przedstawia przykład w kontekście „token ringu” – sieci komputerów uporządkowanych w okrąg. Tutaj każdy komputer lub procesor może „zobaczyć” cały stan jednego procesora, który bezpośrednio go poprzedza i że ten stan może sugerować, że procesor „ma token” lub „nie ma tokena”. Jednym z wymagań jest to, że dokładnie jeden z nich musi „trzymać token” w danym momencie. Drugie wymaganie przewiduje, że każdy węzeł „przekazuje token” do komputera/procesora po nim, tak aby token ostatecznie krążył w pierścieniu.

  • Brak posiadania tokena jest poprawnym stanem dla każdego komputera w tej sieci, ponieważ token może być przechowywany przez inny komputer. Jeśli jednak każdy komputer jest w stanie „nie trzyma tokena”, to cała sieć nie jest w prawidłowym stanie.
  • Podobnie, jeśli więcej niż jeden komputer „posiada token”, to nie jest to prawidłowy stan sieci, chociaż nie można zaobserwować, że jest niepoprawny, patrząc na dowolny komputer z osobna. Ponieważ każdy komputer może „obserwować” tylko stany swoich dwóch sąsiadów, komputerom trudno jest zdecydować, czy cała sieć jest w prawidłowym stanie.

Pierwsze algorytmy samostabilizujące nie wykrywały jednoznacznie błędów w celu ich późniejszej naprawy. Zamiast tego nieustannie pchali system w kierunku legalnego stanu. Ponieważ tradycyjne metody wykrywania błędu były często bardzo trudne i czasochłonne, takie zachowanie uznano za pożądane. (Metoda opisana w cytowanym powyżej artykule zbiera ogromną ilość informacji z całej sieci w jednym miejscu; następnie próbuje ustalić, czy zebrany stan globalny jest poprawny; nawet to określenie może być trudnym zadaniem).

Poprawa wydajności

Niedawno naukowcy przedstawili nowsze metody wykrywania lekkich błędów w systemach samostabilizujących się przy użyciu sprawdzania lokalnego. oraz do zadań ogólnych.

Termin lokalny odnosi się do części sieci komputerowej. Gdy stosowane jest wykrywanie lokalne, komputer w sieci nie musi komunikować się z całą siecią w celu wykrycia błędu — błąd można wykryć, gdy każdy komputer komunikuje się tylko z najbliższymi sąsiadami. Te lokalne metody detekcji znacznie uprościły zadanie projektowania algorytmów samostabilizujących. Dzieje się tak, ponieważ mechanizm wykrywania błędów i mechanizm naprawczy można zaprojektować oddzielnie. Nowsze algorytmy oparte na tych metodach wykrywania również okazały się znacznie wydajniejsze. Co więcej, artykuły te sugerowały dość wydajne ogólne transformatory do przekształcania algorytmów niesamostabilizujących się, aby stały się samostabilizujące. Chodzi o to,

  1. Uruchom jednocześnie niesamostabilizujący się protokół,
  2. wykrywanie usterek (podczas realizacji danego protokołu) z wykorzystaniem ww. metod detekcji,
  3. następnie zastosuj (samostabilizujący się) protokół „resetowania”, aby przywrócić system do określonego z góry stanu początkowego, a na koniec
  4. zrestartuj podany (nie samostabilizujący się) protokół.

Kombinacja tych 4 części jest samostabilizująca (o ile nie ma wyzwalania zwarcia podczas faz zwarcia korekcyjnego, np.). W powyższych artykułach przedstawiono również wstępne protokoły samostabilizujące. Bardziej wydajne protokoły resetowania zostały przedstawione później, np.

Dodatkową wydajność wprowadzono wraz z pojęciem protokołów adaptacyjnych w czasie. Ideą, która się za nimi kryje, jest to, że gdy pojawia się tylko niewielka liczba błędów, czas odzyskiwania może (i powinien) być krótki. Oryginalne algorytmy samostabilizacji Dijkstry nie mają tej właściwości.

Przydatną właściwością algorytmów samostabilizujących się jest to, że mogą one składać się z warstw, jeśli warstwy nie wykazują żadnych zależności kołowych . Czas stabilizacji kompozycji jest wtedy ograniczony przez sumę indywidualnych czasów stabilizacji każdej warstwy.

Później pojawiły się nowe podejścia do twórczości Dijkstry, jak np. przypadek Krzysztofa Apta i Ehsana Shoji, które pokazały, jak samostabilizację można w naturalny sposób formułować za pomocą standardowych koncepcji gier strategicznych, zwłaszcza koncepcji ścieżki doskonalenia. Ta konkretna praca miała na celu wykazanie związku między samostabilizacją a teorią gier.

Złożoność czasu

Czas złożoność algorytmu samostabilizujących mierzy się w (asynchroniczny) rundach lub cykli.

  • Okrągły najkrótsza ślad wykonanie, w którym każdy z procesorów wykonuje co najmniej jeden etap.
  • Podobnie cykl jest najkrótszym śladem wykonania, w którym każdy procesor wykonuje co najmniej jedną kompletną iterację swojej wielokrotnie wykonywanej listy poleceń.

Aby zmierzyć czas stabilizacji wyjścia, zdefiniowano podzbiór zmiennych stanu, aby był widoczny z zewnątrz ( wyjście ). Niektóre stany wyjść są zdefiniowane jako prawidłowe (uprawnione). Mówi się, że zestaw wyjść wszystkich elementów systemu ustabilizował się w momencie, gdy zaczyna być poprawny, pod warunkiem, że pozostaje poprawny w nieskończoność, chyba że wystąpią dodatkowe usterki. Czas stabilizacji wyjścia to czas (liczba (asynchronicznych) rund ) do ustabilizowania się wyjścia.

Definicja

System stabilizuje się samoczynnie wtedy i tylko wtedy, gdy:

  1. Zaczynając od dowolnego stanu, mamy gwarancję, że system ostatecznie osiągnie stan prawidłowy ( konwergencja ).
  2. Biorąc pod uwagę, że system jest w prawidłowym stanie, gwarantujemy, że pozostanie w prawidłowym stanie, pod warunkiem, że nie wystąpi awaria ( zamknięcie ).

Mówi się, że system jest losowo samostabilizujący się wtedy i tylko wtedy, gdy sam się stabilizuje, a oczekiwana liczba rund potrzebnych do osiągnięcia prawidłowego stanu jest ograniczona przez pewną stałą .

Powszechnie wiadomo, że projektowanie samostabilizacji w powyższym sensie jest trudną pracą. W rzeczywistości klasa algorytmów rozproszonych nie ma właściwości sprawdzania lokalnego: legalność stanu sieci nie może być oceniona przez pojedynczy proces. Najbardziej oczywistym przypadkiem jest zdefiniowany powyżej token-ring Dijkstry: żaden proces nie może wykryć, czy stan sieci jest prawidłowy, czy nie w przypadku, gdy więcej niż jeden token jest obecny w procesach niesąsiadujących. Sugeruje to, że samostabilizacja systemu rozproszonego jest rodzajem zbiorowej inteligencji, w której każdy komponent podejmuje lokalne działania, w oparciu o swoją lokalną wiedzę, ale ostatecznie gwarantuje to globalną konwergencję na końcu.

Aby pomóc przezwyciężyć trudności związane z zaprojektowaniem samostabilizacji, jak zdefiniowano powyżej, opracowano inne rodzaje stabilizacji. Na przykład słaba stabilizacja to właściwość polegająca na tym, że rozproszony system ma możliwość osiągnięcia prawidłowego zachowania z każdego możliwego stanu. Słaba stabilizacja jest łatwiejsza do zaprojektowania, ponieważ gwarantuje możliwość zbieżności dla niektórych przebiegów systemu rozproszonego, a nie zbieżności dla każdego przebiegu.

Algorytm samostabilizujący jest cichy wtedy i tylko wtedy, gdy zbiega się do stanu globalnego, w którym wartości rejestrów komunikacyjnych wykorzystywanych przez algorytm pozostają stałe.

Powiązana praca

Rozszerzeniem pojęcia samostabilizacji jest pojęcie superstabilizacji . Celem jest tutaj radzenie sobie z dynamicznymi systemami rozproszonymi, które podlegają zmianom topologicznym. W klasycznej teorii samostabilizacji arbitralne zmiany są postrzegane jako błędy, w przypadku których nie ma gwarancji, dopóki system nie ustabilizuje się ponownie. W przypadku systemów superstabilizujących istnieje predykat przejścia, który jest zawsze spełniony podczas rekonfiguracji topologii systemu.

Bibliografia

Linki zewnętrzne