opis do prezentacji

Wprowadzenie

Wybór lidera stał się przedmiotem intensywnych badań od czasu, gdy został opisany po raz pierwszy przez Gerarda Le Lann [1] w 1977 roku. Kluczowym wymogiem dla węzłów do wykonania jakichkolwiek rozproszonych zadań jest koordynacja. Wiele rozproszonych algorytmów wymaga, aby jeden węzeł pełnił rolę koordynatora, inicjatora lub wykonywał inną specjalną funkcję. Celem wyboru lidera jest wyznaczenie węzła, który będzie koordynował działanie systemu. Każdy algorytm wyboru lidera musi spełniać wymogi bezpieczeństwa i żywotności (ang. liveness), aby rozwiązanie można było uznać za dopuszczalne. Wymóg żywotności oznacza, że każdy z węzłów ostatecznie przyjmuje stan wybranego lub niewybranego jako lider. Warunek bezpieczeństwa dla wyboru lidera wymaga, aby tylko jeden węzeł mógł przejść do stanu wybranego jako lider i ewentualnie zostać koordynatorem systemu rozproszonego. Informacje są wymieniane między węzłami poprzez przekazywanie wiadomości aż do osiągnięcia porozumienia. Gdy decyzja zostanie podjęta, jeden węzeł zostaje wybrany jako lider a wszystkie pozostałe węzły uznają rolę tego węzła jako lidera.

Algorytm tyrana

Algorytm tyrana (ang. bully algorithm) jest jednym z najpowszechniejszych algorytmów wyboru lidera, który został zaproponowany przez Garcia-Molina [2] w 1982 roku. Algorytm ten opiera się na kilku podstawowych założeniach:

Działanie algorytmu tyrana

Kiedy węzeł P wykryje, że aktualny lider uległ awarii poprzez przekroczenie limitu czasu wiadomości lub niezdolność koordynatora do zainicjowania negocjacji, podejmowana jest następująca sekwencja działań:

Ograniczenia algorytmu tyrana

Algorytm tyrana posiada następujące ograniczenia:

Algorytm tyrana według M. S. Kordafshari i innych - działanie

M. S. Kordafshari i inni przedyskutowali wszystkie wady algorytmu tyrana zaproponowanego przez Garcia Molinę i zmodyfikowali go optymalizując algorytm wiadomości. Wykazali, że ich algorytm jest efektywniejszy od oryginalnego, ponieważ przekazywane jest mniejsza liczba wiadomości i występuje mniej faz.

Algorytm zaproponowany przez M. S. Kordafshari i innych:

Algorytm S. Mahdi Jameii i innych

Kolejna modyfikacja algorytmu tyrana została stworzona przez S. Mahdi Jameii i innych. W tym algorytmie zawsze, gdy węzeł wykryje, że lider uległ awarii wysyła „wiadomość wybory” do węzła z najwyższym numerem. Węzeł ten zostanie nowym liderem, dlatego nie jest konieczne angażowanie pozostałych węzłów w wybory. Za każdym razem, gdy węzeł otrzyma „wiadomość wybory” powinien zadeklarować siebie jako nowego lidera. W innym przypadku węzeł będący adresatem wiadomości mógł ulec awarii, podobnie jak lider. Jeśli nadawca nie otrzyma odpowiedzi, węzeł inicjujący wysyła „wiadomość wybory” do kolejnego węzła o najwyższym numerze.

Algorytm pierścieniowy Tanenbauma

Inny typ algorytmu wyboru lidera ma zastosowanie w systemach zorganizowanych w postaci pierścienia. Przyjmujemy, że węzły są fizycznie lub logicznie uporządkowane, a więc każdy węzeł zna swojego następnika.

Zakłada się, że łącza są jednokierunkowe i że węzły wysyłają komunikaty zgodnie z ruchem wskazówek zegara. Węzły mogą ulegać awarii, a każdy węzeł może się komunikować bezpośrednio z każdym innym. Główną strukturą danych jest lista aktywna zawierająca numery priorytetów wszystkich aktywnych węzłów w systemie w chwili zakończenia działania algorytmu. Każdy węzeł utrzymuje własną listę.

Gdy jakiś węzeł zaobserwuje, że lider nie funkcjonuje, tworzy „wiadomość wybory” zawierającą jego numer węzła i wysyła wiadomość do następcy. Jeśli następca również nie funkcjonuje, węzeł nadawczy pomija swojego następcę i przesyła wiadomość do kolejnego węzła wzdłuż pierścienia, i tak aż do zlokalizowania aktywnego węzła. W każdym kroku nadawca dodaje swój numer do listy w wiadomości. Ewentualnie wiadomość powróci do węzła, który ją stworzył. Węzeł rozpoznaje wówczas, że otrzymana wiadomość zawiera jego własny numer. W takim przypadku wiadomość ta zostaje zastąpiona „wiadomością lider” i przesłana ponownie przez pierścień w celu poinformowania pozostałych węzłów o wybraniu nowego lidera – zostaje nim członek listy o najwyższym numerze – oraz jakie węzły tworzą nowy pierścień, i w jakiej kolejności. Gdy wiadomość okrąży pierścień zostaje usunięta przez nadawcę.

Algorytm pierścieniowy Coulourisa

W algorytmie pierścieniowym zaproponowanym przez Tanenbauma można wyróżnić dwie rundy przekazywania wiadomości w pierścieniu. Pierwsza po wykryciu awarii lidera i wysłaniu „wiadomości wybory”. Druga, po zamianie „wiadomości wybory” na „wiadomość lider”. W celu zredukowania przesyłanych wiadomości algorytm pierścieniowy został zmodyfikowany przez Coulourisa. Inicjalnie każdy węzeł oznaczony jest jako nie uczestnik (ang. non-participant). Gdy węzeł zaobserwuje awarię lidera wysyła „wiadomość wybory” z własnym numer do następnika oraz zostaje uczestnikiem. Każdy węzły po otrzymaniu takiej wiadomości porównuje numer zawarty w otrzymanej wiadomości i swój własny. Jeżeli numer zawarty w wiadomości jest wyższy to przesyła komunikat dalej. Jeżeli numer węzła jest wyższy niż ten zawarty w wiadomości, a węzeł jest nie uczestnikiem to zastępuje numer w wiadomości swoim i przesyła komunikat dalej. Jeżeli jest uczestnikiem to nie przesyła wiadomości dalej. Węzeł po przekazaniu wiadomości do następnika staje się uczestnikiem. Jeśli węzeł otrzyma wiadomość ze swoim numerem to oznacza, że wygrał wybory. W tym przypadku zastępuje „wiadomość wybory” „wiadomością lider” i staje się ponownie nie uczestnikiem. Inne węzły po otrzymaniu „wiadomości lider” również zmieniają stan na nie uczestnik przygotowując się do kolejnych wyborów.

Implementacja algorytmów

Powyższe algorytmy zostały zaimplementowane w języku programowania C#. Stworzonych zostało pięć programów, w których każdy węzeł reprezentowany był przez pojedynczy wątek. Po uruchomieniu programu spośród wątków wybierany był jeden pełniący od tego momentu rolę lidera. W wszystkich programach algorytm wyboru lidera był wykonywany po wykryciu awarii dotychczasowego koordynatora, dlatego po uruchomieniu programu pierwszy lider był wybierany losowo, a dopiero następni zgodnie z algorytmem. W naszych implementacjach lider koordynował działanie pozostałych węzłów poprzez przydzielanie kolejnych zadań – zadaniem było odliczanie do pewnej liczby, podanej przez lidera, począwszy od zera. Po zakończeniu obliczeń węzeł zgłaszał liderowi gotowość do wykonania kolejnych zadań poprzez wysłanie odpowiedniego komunikatu. W przypadku, gdy lider nie odpowiedział w określonym czasie węzeł uznawał, że uległ on awarii i uruchamiał algorytm wyboru nowego lidera. Wątek pełniący rolę lidera po pewnym losowym czasie przestawał odpowiadać na komunikaty pozostałych węzłów symulując awarię. Również po pewnym okresie czasu powracał do normalnej pracy imitując naprawę.

Testy algorytmów

Wszystkie testy zostały przeprowadzone na komputerze z procesorem Intel Core 2 Duo P7350 @ 2.00GHz 2.00GHz i zainstalowaną pamięcią RAM 3,00GB. Jakiekolwiek pomiary opóźnień lub czasów działania na komputerze tej klasy byłyby niemiarodajne. Tym bardziej, że w implementacjach wykorzystywane były wartości pseudolosowe.

Zdecydowaliśmy się na pomiar, naszym zdaniem najbardziej znaczącej, wartości – ilości przesłanych wiadomości podczas pojedynczego wyboru nowego lidera przy różnej ilości węzłów.

Każdy test był wykonywany minimum trzykrotnie (jeśli wartości różniły się o więcej niż 5% to więcej razy), a w tabeli zamieszczone zostały wyniki uśrednione.

Podsumowanie

Wybór lidera w systemie rozproszonym jest zagadnieniem trudnym, które wymaga użycia odpowiednich algorytmów wyboru.

Na podstawie przedstawionych wyników testów można zauważyć, że istnieją lepsze i gorsze, pod względem ilości przekazywanych wiadomości a co za tym idzie również obciążenia sieci, algorytmy wyboru lidera. Najgorsze z przedstawionych algorytmów – algorytm tyrana Garcia Moliny oraz algorytm pierścieniowy zaproponowany przez A. Tanenbauma – przekazują O(n2) wiadomości, gdzie n jest liczbą węzłów. Nieznaczne ulepszenie, jak w przypadku algorytmów M. S. Kordafshari i innych, czy też Coulourisa, może znacząco obniżyć ilość przesyłanych komunikatów – do O(n). Możliwe jest także stworzenie algorytmów, które niezależnie od ilości węzłów przesyłają bardzo niewielką liczbę wiadomości – O(1), jak chociażby algorytm stworzony przez S. Mahdi Jameii i innych.


Wyszukiwarka

Podobne podstrony:
opis do prezentacji o elewacjach
Choroby związane za zmianą liczby chromosomów opis do prezentacji
Opis do prezentacji Analiza rynku nieruchomości komercyjnych w Krakowie w latach 2008-2012, Zarządza
opis do prezentacji
OPIS do prezentacji dot RYZYKA?DANIA  03 2013
kompozyty Opis do prezentowanych na zajęciach slajdów, I Semestr, Materiały I
OPIS DO PREZENTACJI START SYSTEMÓW WINDOWS
opis do prezentacji
opis slajow do prezentacji poprawionej 2
opis slajow do prezentacji poprawionej
Wykład IV-do prezentacji, Organizacja rachunkowości
Odpady - materiał do prezentacji, Budownictwo UTP, I rok, I semestr, Prezentacja
do prezentacji
NOTATKA DO PREZENTACJI
do prezentacji
Mikroskopy konspekt do prezentacji
karta do prezentacji zajecia id Nieznany
Do prezentacji, filozofia kultury

więcej podobnych podstron