Rozproszony wybór lidera

Algorytmy Równoległe i Rozproszone

projekt

ROZPROSZONY WYBÓR LIDERA

Autorzy:

Bartłomiej Nowak 119413

Bartosz Próchniak 119428

Mariusz Redwanz 119436

Gdańsk, 2012

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. Wyznaczenie pojedynczego węzła jako organizatora w systemach rozproszonych jest zagadnieniem trudnym, które wymaga użycia odpowiednich algorytmów wyboru. W systemach rozproszonych węzły komunikują się ze sobą za pomocą pamięci współdzielonej lub poprzez przekazywanie komunikatów. Kluczowym wymogiem dla węzłów do wykonania jakichkolwiek rozproszonych zadań jest koordynacja. W czystym systemie rozproszonym nie istnieje żaden centralny węzeł, który rozstrzyga decyzje, a tym samym każdy węzeł musi komunikować się z pozostałymi węzłami w celu podjęcia właściwego wyboru. Często w trakcie procesu decyzyjnego nie wszystkie węzły podejmują tą samą decyzję, a zatem komunikacja między węzłami oraz cały proces decyzyjny są czasochłonne. Koordynacja między węzłami staje się trudna, gdy konieczna jest spójność między wszystkimi węzłami. Scentralizowane węzły sterujące mogą być wybrane z grupy dostępnych węzłów w celu zmniejszenia złożoności i czasochłonności procesu decyzyjnego.

Wiele rozproszonych algorytmów wymaga, aby jeden węzeł pełnił rolę koordynatora, inicjatora lub wykonywał inną specjalną funkcję. Wybór lidera jest techniką, która może być wykorzystana do złamania symetrii systemu rozproszonego. Celem wyboru lidera jest wyznaczenie węzła, który będzie koordynował działanie systemu. Zwykle w algorytmie wyboru lidera, węzeł koordynujący wybierany jest na podstawie jakiegoś kryterium, takiego jak wybór węzła o największym identyfikatorze. Kiedy lider zostanie wybrany węzły osiągają pewien stan, zwany stanem końcowym. W algorytmach wyboru lidera wyróżnia się dwa stany końcowe – stan wybranego i niewybranego jako lider. Kiedy węzeł wejdzie w jeden ze stanów pozostaje w nim przez cały czas.

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.

Przegląd algorytmów

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 zostało przedstawione na Rysunku 1.

Rysunek Algorytm tyrana: a) węzeł 3 wykrył awarię lidera, b) węzeł 3 wysłał wiadomość "wybory" do węzłów 4-9, c) węzły 4-9 odpowiedziały węzłowi 3, aby zakończył wybory, d) węzły 4-9 wysłały wiadomość "wybory", e) węzeł 8 odpowiedział węzłom 4-7, węzeł 7 odpowiedział węzłom 4-6, itd., f) węzeł 8 wygrał i ogłasza to wszystkim pozostałym węzłom.

Algorytm tyrana definiuje trzy typy wiadomości:

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ń:

Algorytm tyrana posiada następujące ograniczenia:

M. S. Kordafshari i inni [3] 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.

Rysunek Zmodyfikowany algorytm tyrana przez M. S. Kordafshari’ego i innych: a) węzeł 3 wykrył awarię lidera, b) węzeł 3 wysyła „wiadomość wybory” do węzłów 4-9, c) węzły 4-9 odpowiadają podając swój numer, d) węzeł 3 wybiera najwyższy numer i wysyła wiadomość do jego właściciela, e) węzeł 8 wysyła „wiadomość lidera” do wszystkich węzłów.

Algorytm zaproponowany przez M. S. Kordafshari i innych:

Algorytm ten posiada następujące wady:

Każdy nadmiarowy wybór zabiera zasoby, zwiększa ilość przekazywanych wiadomości, a więc również ruch w sieci.

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. Procedura ta może być powtórzona wielokrotnie.

Jeśli węzeł Pi wykryje, że lider uległ awarii rozpoczyna poniższy algorytm wyboru nowego lidera:

Rysunek Zmodyfikowany algorytm tyrana przez S. Mahdi Jameii i innych: a) węzeł 3 wykrył awarię lidera, b) węzeł 3 wysyła „wiadomość wybory: tylko do węzła o numerze 8, ponieważ ma on najwyższy numer, c) węzeł 8 wysyła „wiadomość lidera” do pozostałych węzłów.

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.

W wariancie zaproponowanym przez A. Tanenbauma [5] 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ę.

Rysunek Algorytm pierścieniowy według A. Tanenbauma: a) węzły 2 i 5 jednocześnie wykryły awarię lidera – 7, b) węzeł 2 i 5 tworzy „wiadomość wybory” i wysyła do następnika, c) „wiadomości wybory” przekazywane są dalej przez kolejne węzły (z powodu braku komunikacji wiadomość z węzła 6 przekazywana jest do węzła 0), d) „wiadomości wybory” okrążają pierścień i wracają do nadawców, e) „wiadomości wybory” zostają zastąpione „wiadomościami lider”, f) „wiadomości lider” zostają usunięte przez nadawcę, a pierścień zostaje zmodyfikowany (pozostają tylko aktywne węzły).

W algorytmie pierścieniowym zaproponowanym przez A. 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.

Rysunek Algorytm pierścieniowy według Coulourisa: a) węzły 2 i 5 jednocześnie wykryły awarię lidera – 7, tworzą „wiadomości wybory”, wysyłają je do następnika oraz zmieniają stan na uczestnik, b) „wiadomości wybory” przekazywane są dalej przez kolejne węzły (z powodu braku komunikacji wiadomość z węzła 6 przekazywana jest do węzła 0) – węzeł 3 i 6 zamieniają numery zawarte w wiadomości na własne i stają się uczestnikami, c) „wiadomości wybory” są przekazywane dalej przez kolejne węzły – węzeł 4 zmienia numer w wiadomości na własny i, podobnie jak węzeł 0, staje się uczestnikiem, d) „wiadomość wybory” odebrana przez węzeł 5 zostaje usunięta, natomiast komunikat odebrany przez węzeł 1 zostaje przekazany dalej, a węzeł staje się uczestnikiem, e) wiadomość wybory” okrąża pierścień i wraca do nadawców – węzła 6, który zastępuje ją „wiadomością lider”, f) „wiadomość lider” zostaje usunięta przez nadawcę, a pierścień zostaje zmodyfikowany (pozostają tylko aktywne węzły).

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 dziesięciokrotnie, a w tabeli zamieszczone zostały wyniki uśrednione.

Tabela Wyniki testów.

Ilość wątków Garcia-Molina

M. S. Kordafshari

i innych

S. Mahdi Jameii

i innych

Tanenbauma Coulourisa
8 42 19 9 36 16
16 134 29 17 162 28
24 386 44 25 367 46
32 892 67 33 880 64
40 1156 98 41 1231 90
48 1857 147 49 2003 138
56 2498 186 57 2754 191
64 2921 213 65 3576 223

Wykres 1 Ilość przesyłanych wiadomości podczas pojedynczego wyboru lidera w poszczególnych algorytmach z uwzględnieniem różnej ilości węzłów (wątków).

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.

Z tabeli, jak i z wykresu, można zaobserwować, że topologia systemu nie ma wpływu na ilość przesyłanych wiadomości podczas działania algorytmu wyboru lidera. Algorytmy Garcia-Molina i Tanenbauma oraz Kordafshari’ego i Coulourisa osiągają zbliżone wyniki.

Bibliografia

  1. G. Le Lann, “Distributed System – Towards a Formal Approach”, In Information Processing 77, B. Gilchrist, Ed.Amsterdam, Thenetherlands: North-Holland, 1977, pp. 155- 160.

  2. H. Garcia-Molina, “Elections in Distributed Computing System”, IEEE Transaction Computer, Vol. C- 31, 1982, pp. 48- 59.

  3. M. S. Kordafshari, M. Gholipour, M. Jahanshahi, A. T. Haghighat, “Modified bully election algorithm in distributed system”, WSEAS Conferences, Cancun, Mexico, 2005, May 11-14.

  4. D. P. Gawali, “Leader Election Problem in Distributed Algorithm”, 2012.

  5. A. Tanenbaum, “Rozproszone systemy operacyjne”, PWN, 1997 (rozdział 3: Synchronizacja w systemach rozproszonych).

  6. A. Silberschatz, P. Galvin, “Podstawy systemów operacyjnych”, WNT, 2000 (rozdział 18: Koordynacja rozproszona).

  7. G. Coulouris, J. Dollimore, T. Kindberg, “Systemy rozproszone, podstawy I projektowanie”, WNT, 1998 (rozdział 10: Czas I koordynacja).


Wyszukiwarka