Konsenzuální algoritmus Chandra – Toueg - Chandra–Toueg consensus algorithm - Wikipedia

The Konsenzuální algoritmus Chandra – Toueg, publikovaný Tushar Deepak Chandra a Sam Toueg v roce 1996, je algoritmus pro řešení shoda v síti nespolehlivých procesů vybavených nakonec silný detektor poruch. Detektor selhání je abstraktní verzí časové limity; signalizuje každému procesu, když mohlo dojít k selhání jiných procesů. Nakonec silný detektor selhání je ten, který nikdy neidentifikuje nějaký konkrétní nezávadný proces, jako by selhal po určité počáteční době záměny a zároveň nakonec identifikuje Všechno vadné procesy jako selhané (kde vadný proces je proces, který nakonec selže nebo spadne a nezávadný proces nikdy selže). Konsenzuální algoritmus Chandra – Toueg předpokládá, že počet vadných procesů, označený jako F, je menší než n / 2 (tj. menšina), tj. předpokládá F < n/ 2, kde n je celkový počet procesů.

Algoritmus

Algoritmus postupuje v kolech a používá rotujícího koordinátora: v každém kole r, proces, jehož identita je dána r mod n je vybrán jako koordinátor. Každý proces sleduje svoji aktuální preferovanou rozhodovací hodnotu (původně rovnou vstupu procesu) a poslední kolo, kde změnil svoji rozhodovací hodnotu (hodnota časové razítko ). Akce prováděné v každém kole jsou:

  1. Všechny procesy odesílají (r, preference, časové razítko) koordinátorovi.
  2. Koordinátor čeká na příjem zpráv od nejméně poloviny procesů (včetně sebe).
    1. Poté vybere jako svou preferenci hodnotu s nejnovějším časovým razítkem mezi odeslanými.
  3. Koordinátor odesílá (r, preference) všem procesům.
  4. Každý proces čeká (1) na přijetí (r, preference) od koordinátora, nebo (2), až jeho detektor selhání identifikuje koordinátora jako havarovaného.
    1. V prvním případě nastaví vlastní preference na preference koordinátora a odpoví ack (r).
    2. Ve druhém případě pošle koordinátorovi nack (r).
  5. Koordinátor čeká na přijetí ack (r) nebo nack (r) z většiny procesů.
    1. Pokud obdrží potvrzení (r) od většiny, odešle rozhodnout (preference) ke všem procesům.
  6. Jakýkoli proces, který poprvé přijme rozhodnutí (preference), rozhodne (preference) pro všechny procesy, poté rozhodne o preference a ukončí se.

Všimněte si, že tento algoritmus se používá k rozhodnutí pouze o jedné hodnotě.

Správnost

Definice problému

Algoritmus, který „řeší“ konsensuální problém, musí zajistit následující vlastnosti:

  1. ukončení: všechny procesy rozhodují o hodnotě;
  2. dohoda: všechny procesy rozhodují o stejné hodnotě; a
  3. platnost: všechny procesy rozhodují o hodnotě, která byla vstupní hodnotou nějakého procesu;

Předpoklady

Než budete tvrdit, že konsensuální algoritmus Chandra – Toueg splňuje tři výše uvedené vlastnosti, připomeňte si, že tento algoritmus vyžaduje n = 2*F + 1 procesů, z nichž nejvýše f je vadných.

Dále si všimněte, že tento algoritmus předpokládá existenci případně detektor silné poruchy (které jsou přístupné a lze je použít k detekci selhání uzlu). Nakonec je to silný detektor selhání nikdy identifikuje nějaký konkrétní vadný (nebo správný) proces, který selhal, po určité počáteční době záměny a současně případně identifikuje Všechno vadné procesy jako selhaly.

Důkaz správnosti

Ukončení drží, protože nakonec detektor poruchy přestane tušit nějaký nezávadný proces p a nakonec p se stane koordinátorem. Pokud algoritmus nebyl ukončen dříve, než k tomu dojde v nějakém kole r, pak každý nezávadný proces v kole r čeká na přijetí preference p a odpoví ack (r). To umožňuje p shromáždit dostatek potvrzení k odeslání rozhodnutí (preference), což způsobí ukončení každého procesu. Alternativně se může stát, že některé vadné odeslané koordinátory se rozhodnou pouze pro několik procesů; ale pokud některý z těchto procesů není vadný, odešlou rozhodnutí všem zbývajícím procesům a způsobí jejich rozhodnutí a ukončení.

Platnost vyplývá ze skutečnosti, že každá preference začíná jako vstup nějakého procesu; v protokolu není nic, co by generovalo nové preference.

Dohoda je potenciálně nejobtížnější dosáhnout. Je možné, že koordinátor v jednom kole r může poslat rozhodovací zprávu z nějaké hodnoty v, která se šíří pouze na několik procesů, než nějaký jiný koordinátor v pozdějším kole r 'pošle rozhodovací zprávu pro nějakou jinou hodnotu v '. Chcete-li ukázat, že k tomu nedochází, pozorujte, že než první koordinátor může odeslat rozhodnutí (v), musí obdržet ack (r) od většiny procesů; ale potom, když kterýkoli pozdější koordinátor vyzve většinu procesů, pozdější většina překryje dřívější a v bude nejnovější hodnota. Takže libovolní dva koordinátoři, kteří odesílají, rozhodují o odeslání zprávy stejnou hodnotu.

Reference