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
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.
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:
system jest synchroniczny i używa mechanizmu przekroczenia czasu do wykrywania awarii koordynatora,
każdy węzeł posiada unikalny numer w celu odróżnienia go od pozostałych,
każdy węzeł zna numery wszystkich pozostałych węzłów,
węzły nie wiedzą, które węzły są w danej chwili sprawne, a które nie,
podczas wyboru, węzeł o najwyższym numerze jest wybierany na lidera, kiedy pozostałe węzły zgodzą się na taki wybór,
węzeł, który uległ awarii może powrócić do systemu po naprawieniu.
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:
„wiadomość wybory” (pytanie), która jest wysyłana jako ogłoszenie wyborów,
„wiadomość odpowiedzi” (ok), która jest wysyłana w odpowiedzi na wiadomość „wybory”,
„wiadomość lidera” (zwycięzcy) wysyłana w celu poinformowania pozostałych węzłów o wyborze nowego lidera.
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ń:
Węzeł P wysyła „wiadomość wybory” do wszystkich węzłów z wyższymi numerami niż jego. Jeżeli P nie otrzyma odpowiedzi od żadnego z tych procesów wygrywa wybory i wysyła „widomość lidera”.
Jeśli węzeł P otrzyma odpowiedź z wyższym numerem, węzeł P rezygnuje i czeka na „wiadomość lidera” od jednego z węzłów o wyższym numerze. Następnie nowy węzeł inicjuje wybory poprzez wysłanie „wiadomości wybory”. W ten sposób wszystkie węzły poddadzą się za wyjątkiem węzła o najwyższym numerze spośród wszystkich sprawnych węzłów, który zostanie wybrany nowym koordynatorem. Węzeł ten ogłasza się nowym liderem poprzez wysłanie rozgłoszeniowej „wiadomości lidera”.
Natychmiast po naprawieniu uszkodzonego węzła zostaje uruchomiony algorytm tyrana.
Algorytm tyrana posiada następujące ograniczenia:
Głównym ograniczeniem algorytmu tyrana jest duża ilość wiadomości przekazywanych podczas wyboru lidera - O(n2).
Kiedy proces zaobserwuje, że lider uległ awarii ogłasza nowe wybory. W rezultacie może wystąpić n „wiadomości wybory” w systemie w tym samym czasie, co zwiększa natężenie ruchu w sieci.
Ponieważ nie ma gwarancji dostarczenia wiadomości dwa węzły mogą deklarować się jako lider w tym samym czasie. Na przykład węzeł P inicjuje wybory i nie otrzyma żadnej odpowiedzi od węzła Q, gdzie węzeł Q ma wyższy numer niż węzeł P. W tym przypadku węzeł P ogłosi siebie jako koordynatora, jak również węzeł Q będzie inicjował nowe wybory i deklarował siebie jako lidera, jeśli nie będzie węzłów o wyższym numerze niż Q.
Jeżeli lider działa niezwykle powoli (na przykład, dlatego, że system nie działa poprawnie z jakiś powodów) lub jeśli połączenie między węzłem a liderem jest uszkodzone, inny proces może nie wykryć koordynatora i zainicjować wybory. Jednak lider jest sprawny a wybory są niepotrzebne.
Jeżeli węzeł P z mniejszym numerem niż aktualny lider ulegnie awarii, po czym ponownie stanie się sprawny, zainicjuje wybory z obecnego stanu.
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:
Gdy węzeł P zaobserwuje, że lider nie działa inicjuje wybory poprzez wysłanie „wiadomości wybory” do wszystkich węzłów o wyższym numerze od niego. Gdy żaden węzeł nie odpowie węzłowi P, ten deklaruje siebie jako nowego lidera. Natomiast jeżeli któryś z węzłów odpowie, węzeł P wybiera węzeł o najwyższym numerze i wysyła „wiadomość nadania” do wybranego węzła. Ostatecznie wybrany węzeł rozgłasza „wiadomość lidera” do wszystkich pozostałych węzłów. Jeśli któryś z węzłów o wyższym numerze jest sprawny uruchomi algorytm ponownie.
Aby wyeliminować zbieżne wybory, gdy węzeł P zaobserwuje awarię lidera zainicjuje wybory. Jeżeli węzeł Q otrzyma „wiadomość wybory” od węzła z niższym numerem, czeka krótki okres czasu i odpowiada węzłowi z najniższym numerem i zatrzymuje własny algorytm. Ale jeśli węzeł P nie otrzymuje żadnej odpowiedzi ani żadnej „wiadomość wybory” od innego węzła o niższym numerze, to deklaruje siebie jako lidera.
Algorytm ten posiada następujące wady:
Jeśli węzeł P ulegnie awarii po wysłaniu „wiadomości wybory” do węzłów o wyższych numerach lub otrzymaniu od nich odpowiedzi, węzeł o wyższym numerze będzie czekał trzykrotną długość średniego opóźnienia propagacji na „wiadomość lidera” i jeśli jej nie otrzyma rozpocznie wykonanie algorytmu ponownie. Jeżeli istnieje Q węzłów o wyższym numerze zostanie uruchomionych Q instancji tego algorytmu. Są to nadmiarowe wybory.
Jeżeli węzeł P wyśle „wiadomość nadania” do węzła o najwyższym numerze i węzeł P nie otrzyma „wiadomości lidera” od tego węzła w czasie równym średniej długości opóźnienia, węzeł P powtórzy algorytm, który będzie nadmiarowym wyborem.
Mimo, że węzeł Q wysyła wiadomość stopu do węzła P, jeśli węzeł R o niższym numerze niż Q wysyła „wiadomość wyboru” do Q z tego warunku R < P < Q, to zajmuje zasoby sieci do wysłania wiadomości stopu i zwiększa ruch w sieci.
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:
Pi wysyła „wiadomość wyboru” do węzła Pj, który ma najwyższy numer. Jeżeli Pi = Pj to Pi zostaje liderem.
Jeśli Pi otrzyma odpowiedź od Pj, to Pj zostaje nowym liderem.
Jeśli Pj nie wyśle odpowiedzi (ulegnie awarii), to dwa poprzednie kroki są powtarzane.
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).
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ę.
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).
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.
G. Le Lann, “Distributed System – Towards a Formal Approach”, In Information Processing 77, B. Gilchrist, Ed.Amsterdam, Thenetherlands: North-Holland, 1977, pp. 155- 160.
H. Garcia-Molina, “Elections in Distributed Computing System”, IEEE Transaction Computer, Vol. C- 31, 1982, pp. 48- 59.
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.
D. P. Gawali, “Leader Election Problem in Distributed Algorithm”, 2012.
A. Tanenbaum, “Rozproszone systemy operacyjne”, PWN, 1997 (rozdział 3: Synchronizacja w systemach rozproszonych).
A. Silberschatz, P. Galvin, “Podstawy systemów operacyjnych”, WNT, 2000 (rozdział 18: Koordynacja rozproszona).
G. Coulouris, J. Dollimore, T. Kindberg, “Systemy rozproszone, podstawy I projektowanie”, WNT, 1998 (rozdział 10: Czas I koordynacja).