//Pytanie: "Algorytmy wyboru koordynatora (tyrana, pierścieniowy)"//


 ====== Algorytmy elekcji ======

W wielu algorytmach rozproszonych stosuje się proces koordynujący, 
który wykonuje funkcje potrzebne innym pro­cesom w systemie.
Wśród funkcji tych znajdują się takie, jak: 
  * wymusza­nie wzajemnego wykluczania,
  * utrzymywanie globalnego grafu oczekiwania w celu wykrywania zakleszczenia, 
  * zastępowanie utraconych żetonów, 
  * kontrolowanie urządzeń wejścia/wyjścia w systemie. 

Jeśli proces koordynujący przestaje działać z powodu awarii stanowiska, na
którym przebywa, to w celu dalszej pracy system musi uruchomić nową kopię
koordynatora na jakimś innym stanowisku. Algorytmy rozstrzygające, gdzie
powinno nastąpić wznowienie kopii koordynatora, są nazywane algorytmami elekcji
(ang. election).

W algorytmach elekcji zakłada się, że z każdym aktywnym procesem w systemie
jest związany jednoznaczny numer priorytetu. W celu uproszczenia notacji
założymy, że i jest numerem priorytetu procesu P<sub>i</sub>. Dla prostoty przyjmiemy
też, że istnieje wzajemnie jednoznaczna odpowiedniość miedzy procesami i
stanowiskami, zatem do stanowisk będziemy się odwoływać tak jak do procesów.
Koordynatorem jest zawsze proces z najwyższym numerem priorytetu. Jeśli więc
koordynator ulegnie awarii, to algorytm musi wybrać ten spośród aktywnych
procesów, który ma największy numer priorytetu. Numer ten musi zostać wysłany
do każdego aktywnego procesu w systemie. Oprócz tego algorytm musi zawierać
mechanizm umożliwiający zidentyfikowanie bieżącego koordynatora przez proces
przywracany do działania.

W obu algorytmach na wykonanie elekcji potrzeba n komunikatów, przy czym n jest
liczbą procesów w systemie. Zakładamy, że proces, który uległ uszkodzeniu, ma o
tym informację podczas przywracania go do działania; podejmuje on zatem
odpowiednie czynności (opisane dalej), aby dołączyć do zbioru procesów
aktywnych.

===== Algorytm tyrana =====


Algorytm ma zastosowanie w tych systemach, w
których każdy proces może wysłać komunikat do dowolnego procesu w systemie.
Przypuśćmy, że proces P<sub>i</sub> wysyła zamówienie, które pozostaje bez odpowiedzi
ze strony koordynatora przez czas T. W tej sytuacji zakłada się, że koordynator
uległ awarii, a proces P<sub>i</sub> próbuje sam siebie obrać nowym koordynatorem,
posługując się następującym algorytmem.

Proces P<sub>i</sub> wysyła komunikat o elekcji do wszystkich procesów z wyż­szymi
numerami priorytetów. Następnie czeka przez czas T na nadejście odpowiedzi od
któregokolwiek z tych procesów.

Jeśli w czasie T nie nadejdzie żadna odpowiedź, to proces P<sub>i</sub> zakłada, że
wszystkie procesy z numerami priorytetów większymi od i uległy awariom i wybiera
siebie na nowego koordynatora. Proces P<sub>i</sub> wznawia kopię koordynatora i wysyła
komunikat informujący wszystkie procesy o numerach priorytetów mniejszych od i,
że P<sub>i</sub> został nowym koordynatorem.

Jeżeli jednak odpowiedź nadejdzie, to proces P<sub>i</sub> rozpoczyna czekanie przez
czas T', aby otrzymać komunikat, że koordynatorem został obrany jakiś proces o
wyższym numerze priorytetu. (Jakiś inny proces obrał się koordynatorem i
powinien powiadomić o tym w czasie T'). Jeśli przez czas T' nie nadejdzie żaden
komunikat, to przyjmuje się, że proces o wyższym numerze uległ awarii i proces
P<sub>i</sub> powinien wznowić wykonywanie algorytmu.

Jeśli proces P<sub>i</sub> nie jest koordynatorem, to w każdej chwili swojego działania
może otrzymać jeden z następujących dwu komunikatów od procesu P<sub>j</sub>

  -P<sub>j</sub> jest nowym koordynatorem (j > i). Proces P<sub>i</sub> odnotowuje tę informację.
  -P<sub>j</sub> rozpoczął elekcję (j < i).

Proces P<sub>i</sub> wysyła odpowiedź do P<sub>j</sub> i sam rozpoczyna wykonywać algorytm
elekcji, jeśli jeszcze go nie rozpoczął. Proces, który zakończy swój algorytm,
ma najwyższy numer, więc zostaje koordynatorem. Wysłał on swój numer do
wszystkich aktywnych procesów z mniejszymi numerami. Proces, który po awarii
powraca do działania, natychmiast rozpoczyna wykonywanie tego samego algorytmu.
Jeśli wśród aktywnych procesów nie ma procesów z wyższymi numerami, to
wznawiający działanie proces zmusza wszystkie procesy z niższymi numerami do
uznania go koordynatorem nawet wówczas, gdy istnieje wśród nich koordynator z
niższym numerem. Z tego powodu algorytm ten nazwano algorytmem tyrana.

=====  Algorytm pierścieniowy =====


Algorytm znajduje zastosowanie w systemach zorganizowanych w postaci
pierścienia (logicznego lub fizycznego). W algorytmie pierścieniowym (ang.
ring algorithm) zakłada się, że łącza są jednokierunkowe oraz że procesy
wysyłają komunikaty do swoich sąsiadów po prawej stronie. Główną strukturą
danych używaną przez algorytm jest lista aktywna (ang. active list), zawierająca
numery priorytetów wszystkich procesów aktywnych w systemie w chwili
zakończenia algorytmu. Każdy proces utrzymuje własną listę aktywną. Przebieg
algorytmu jest następujący:



  - Jeśli proces P<sub>i</sub> wykrywa awarię koordynatora, to tworzy nową listę aktywną, która początkowo jest pusta. Następnie wysyła komunikat ''elekcja(i)'' do swojego sąsiada po prawej stronie i dodaje numer **i** do swojej listy aktywnej.
  - Jeśli P<sub>i</sub> otrzyma komunikat elekcja(j) od procesu po lewej, to musi od­ powiedzieć w jeden z trzech sposobów:
    -Jeśli jest to pierwszy komunikat elekcja, z którym ma do czynienia lub który wysłał, to P<sub>i</sub> tworzy nową listę aktywną z numerami **i** i **j**. Wysyła wówczas komunikat ''elekcja(i)'' , a po nim komunikat ''elekcja(j)'' .
    -Jeśli **i <> j** (tj. otrzymany komunikat nie zawiera numeru procesu P<sub>i</sub>), to P<sub>i</sub> dodaje **j** do swojej listy aktywnej i przekazuje ten komunikat dalej, do swojego sąsiada po prawej stronie.
    -Jeśli **i = j** (tzn. P<sub>i</sub> otrzymuje komunikat ''elekcja(i)'' to lista aktywna procesu P<sub>i</sub> zawiera już numery wszystkich aktywnych procesów w systemie. Proces P<sub>i</sub> może teraz określić największy numer na liście aktywnej, aby wskazać nowy proces koordynujący.


W algorytmie tym nie sprecyzowano, w jaki sposób proces przywracany do działania
ma określić numer bieżącego koordynatora. Jednym z rozwiązań mogłoby być
wymaganie, aby proces reaktywowany wysłał komunikat z zapytaniem. Komunikat
taki, przekazywany naokoło pierścienia, dotarłby do bieżącego koordynatora,
który w odpowiedzi wysłałby wiadomość o swoim numerze.