Algorytm konsensusu Chandry – Touega
Algorytm konsensusu Chandra-Toueg , opublikowany przez Tushara Deepaka Chandrę i Sama Touega w 1996 roku, jest algorytmem rozwiązywania konsensusu w sieci niewiarygodnych procesów wyposażonych w ostatecznie silny detektor awarii . Detektor awarii jest abstrakcyjną wersją limitów czasu ; sygnalizuje każdemu procesowi, kiedy inne procesy mogły ulec awarii. Wykrywacz ostatecznie silnych awarii to taki, który nigdy nie identyfikuje jakiegoś konkretnego procesu, który nie jest wadliwy, jako uszkodzony po pewnym początkowym okresie dezorientacji, a jednocześnie ostatecznie identyfikuje wszystkie wadliwe procesy jako nieudane (gdzie wadliwy proces to proces, który ostatecznie kończy się niepowodzeniem lub awarią, a niewadliwy proces nigdy nie zawodzi). Algorytm konsensusu Chandry-Touega zakłada, że liczba błędnych procesów, oznaczona przez f , jest mniejsza niż n/2 (czyli mniejszość), czyli przyjmuje f < n /2, gdzie n jest całkowitą liczbą procesów.
Algorytm
Algorytm przebiega w rundach i wykorzystuje rotacyjnego koordynatora: w każdej rundzie r proces, którego tożsamość jest określona przez r mod n , jest wybierany jako koordynator. Każdy proces śledzi swoją aktualną preferowaną wartość decyzyjną (początkowo równą wejściu procesu) oraz ostatnią rundę, w której zmienił swoją wartość decyzyjną (sygnatura czasowa wartości ) . Akcje przeprowadzane w każdej rundzie to:
- Wszystkie procesy wysyłają (r, preferencje, znacznik czasu) do koordynatora.
- Koordynator czeka na komunikaty od co najmniej połowy procesów (w tym od siebie).
- Następnie wybiera jako swoją preferencję wartość z najnowszym znacznikiem czasu spośród wysłanych.
- Koordynator wysyła (r, preferencje) do wszystkich procesów.
- Każdy proces czeka (1) na otrzymanie (r, preferencja) od koordynatora lub (2) na to, że jego detektor awarii zidentyfikuje koordynatora jako uszkodzony.
- W pierwszym przypadku ustawia własne preferencje na preferencje koordynatora i odpowiada ack(r).
- W drugim przypadku wysyła nack(r) do koordynatora.
- Koordynator czeka na potwierdzenie od większości procesów.
- Jeśli otrzyma ack(r) od większości, wysyła decyzyjną (preferencję) do wszystkich procesów.
- Każdy proces, który po raz pierwszy otrzyma decyzję (preferencję), przekazuje decyzję (preferencję) wszystkim procesom, a następnie decyduje o preferencjach i kończy działanie.
Należy zauważyć, że ten algorytm jest używany do decydowania tylko o jednej wartości.
Poprawność
Definicja problemu
Algorytm „rozwiązujący” problem konsensusu musi zapewniać następujące właściwości:
- zakończenie: wszystkie procesy decydują o wartości;
- porozumienie: wszystkie procesy decydują o tej samej wartości; I
- ważność: wszystkie procesy decydują o wartości, która była wartością wejściową jakiegoś procesu;
Założenia
Zanim argumentujemy, że algorytm konsensusu Chandry – Touega spełnia trzy powyższe właściwości, przypomnijmy sobie, że ten algorytm wymaga n = 2 * f + 1 procesów, z których co najwyżej f jest błędnych.
Ponadto zauważ, że ten algorytm zakłada istnienie ostatecznie silnego detektora awarii (które są dostępne i mogą być użyte do wykrycia awarii węzła). Ostatecznie silny wykrywacz awarii to taki, który nigdy nie identyfikuje określonego , niewadliwego (lub poprawnego) procesu jako nieudanego, po pewnym początkowym okresie zamieszania, a jednocześnie ostatecznie identyfikuje wszystkie wadliwe procesy jako nieudane.
Dowód poprawności
Zakończenie się utrzymuje, ponieważ w końcu wykrywacz awarii przestaje podejrzewać jakiś niewadliwy proces p i ostatecznie p staje się koordynatorem. Jeśli algorytm nie zakończył działania, zanim to nastąpi w jakiejś rundzie r, to każdy prawidłowy proces w rundzie r czeka na otrzymanie preferencji p i odpowiada ack(r). Pozwala to p na zebranie wystarczającej liczby potwierdzeń, aby wysłać decyzję (preferencja), powodując zakończenie każdego procesu. Alternatywnie może się zdarzyć, że jakiś wadliwy koordynator wysyła decyzje tylko do kilku procesów; ale jeśli którykolwiek z tych procesów nie jest wadliwy, rozgłaszają decyzję do wszystkich pozostałych procesów, powodując ich podjęcie decyzji i zakończenie.
Trafność wynika z faktu, że każda preferencja zaczyna się jako dane wejściowe jakiegoś procesu; w protokole nie ma niczego, co generuje nowe preferencje.
Porozumienie jest potencjalnie najtrudniejsze do osiągnięcia. Może się zdarzyć, że koordynator w jednej rundzie r wyśle wiadomość decyzyjną z pewnej wartości v, która rozprzestrzeni się tylko do kilku procesów, zanim jakiś inny koordynator w późniejszej rundzie r' wyśle wiadomość decyzyjną dla innej wartości v '. Aby pokazać, że tak się nie dzieje, zauważmy, że zanim pierwszy koordynator będzie mógł wysłać seek(v), musi otrzymać potwierdzenie(r) od większości procesów; ale wtedy, gdy dowolny późniejszy koordynator odpytuje większość procesów, późniejsza większość będzie nakładać się na wcześniejszą, a v będzie ostatnią wartością. Tak więc dowolne dwa koordynatory, które wysyłają decyzyjny komunikat, wysyłają tę samą wartość.