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 (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.
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.
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 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:
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.
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.
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ę.
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.
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 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.
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.