Gbcast - Gbcast

Gbcast (také známý jako skupinové vysílání) je spolehlivý protokol vícesměrového vysílání, který zajišťuje objednané, na chyby odolné (vše nebo žádné) doručování zpráv ve skupině příjemců v síti počítačů, u kterých došlo k selhání.^[1][2][3] Protokol je schopen řešit Shoda v síti nespolehlivých procesorů a lze je použít k implementaci replikace stavového stroje.^[4][5] Gbcast lze použít samostatně nebo může podporovat virtuální synchronizace model provádění, kdy se pro správu členství ve skupině obvykle používá Gbcast, zatímco pro rutinní komunikační úkoly se často upřednostňují jiné, rychlejší protokoly.

Dějiny

Představen v roce 1985,^[1] Gbcast byl první široce nasazený spolehlivý protokol vícesměrového vysílání, který implementoval replikaci stavového stroje s dynamicky rekonfigurovatelným členstvím. Ačkoli tento problém byl v předchozí práci teoreticky řešen pod různými modely, Gbcast inovoval ukázkou, že stejné vícesměrové vysílání používané k aktualizaci replikovaných dat ve stavovém stroji lze také použít k dynamickému překonfigurování členství ve skupině, které se pak může vyvinout a umožnit členům připojit se a odejít dle libosti, kromě toho, že budou odstraněny při selhání Tato funkce spolu s mechanismem přenosu stavu používaným k inicializaci spojujících členů představuje základ virtuální synchronizace model provádění skupiny procesů.

Termín replikace stavového stroje poprvé navrhl Leslie Lamport ^[4] a byl široce přijat po zveřejnění průzkumného příspěvku, který napsal Fred B. Schneider.^[6] Model pokrývá jakýkoli systém, ve kterém je replikován nějaký deterministický objekt (stavový stroj) takovým způsobem, že lze na repliky bezchybně použít řadu příkazů. Rekonfigurovatelný stavový stroj je takový, který může měnit své členství, přidávat nové členy nebo odebírat staré.^[7] Některé protokoly stavových strojů mohou také odstranit dočasnou nedostupnost podmnožiny aktuálních členů, aniž by bylo nutné překonfigurovat, když nastanou takové situace, včetně Gbcast a také Paxos,^[5] Lamportův široce citovaný protokol pro replikaci stavových strojů.

Replikace stavového stroje úzce souvisí s distribuovanou Shoda problém,^[8] ve kterém se soubor procesů musí shodnout na nějakém výsledku rozhodnutí, například na vítězi voleb. Zejména je možné ukázat, že jakékoli řešení problému replikace stavového stroje by bylo také schopné vyřešit distribuovaný konsenzus. Důsledkem je nemožnost pro distribuovaný konsenzus ^[9] použít na řešení problému replikace stavového stroje. Důsledky tohoto zjištění jsou diskutovány níže živost.

Gbcast je poněkud neobvyklý v tom, že většina řešení problému replikace stavového stroje je úzce integrována s replikovanou aplikací. Gbcast je naopak navržen jako vícesměrové vysílání API a implementován knihovnou, která doručuje zprávy členům skupiny. Lamport, Malkhi a Zhou poznamenávají, že několik spolehlivých protokolů vícesměrového vysílání má vlastnosti trvanlivosti požadované pro správnou implementaci modelu stavového stroje. Gbcast vykazuje nezbytné vlastnosti.^[7]

Protokol Gbcast byl poprvé popsán v publikaci z roku 1985, která pojednávala o infrastruktuře podporující virtuální synchronizace model v sadě nástrojů Isis.^[1] Další podrobnosti byly uvedeny v pozdějším článku z roku 1987,^[2] a verze protokolu s otevřeným zdrojovým kódem byla vydána vývojáři Cornell v listopadu téhož roku. Isis použila protokol primárně k udržení členství ve skupinách procesů, ale také nabídla API, které by mohli volat přímo koncoví uživatelé. Tato technologie se široce používala od roku 1988, kdy byl systém Isis komercializován a byla k dispozici podpora. Komerční podpora systému skončila v roce 1998, kdy se společnost Stratus Computer, tehdy mateřská společnost společnosti Isis Distributed Systems, znovu zaměřila čistě na hardwarová řešení pro telekomunikační průmysl.

Mezi příklady systémů, které používaly Isis v produkčním prostředí, patří Newyorská burza cenných papírů, kde byla přibližně deset let používána ke správě konfigurovatelné, na chyby odolné a samoléčebné infrastruktury pro hlášení obchodní platformy, k předávání nabídek a obchodních zpráv z „back office“ systémy používané výměnou k zpětnému zobrazení. Francouzský systém řízení letového provozu nadále používá Isis; od roku 1996 je systém používán k vytváření klastrů pracovních stanic odolných vůči poruchám pro použití řídícími letového provozu a ke spolehlivému předávání aktualizací směrování mezi středisky řízení letového provozu; v průběhu času byla francouzská technologie přijata i jinými evropskými systémy ATC. Americké námořnictvo AEGIS používá Isis od roku 1993 k podpoře spolehlivé a samoléčebné komunikační infrastruktury. Isis také měla několik stovek dalších produkčních uživatelů v oblastech financí, telekomunikací, řízení procesů, SCADA a dalších kritických infrastruktur. Více podrobností naleznete v.^[3]

Problémové prohlášení

Základní problém vyřešený Gbcastem je tento: dostáváme počáteční sadu členové skupiny a chtějí podporovat abstrakci vícesměrového vysílání, která členům skupiny umožňuje odesílat zprávy, které kódují různé příkazy nebo požadavky. Protokol se musí dohodnout na zprávách, které mají být doručeny, a na jejich objednání, takže pokud některý člen skupiny pošle zprávu, každý člen skupiny, který nezklame, obdrží tuto zprávu a ve stejném pořadí s ohledem na ostatní doručené zprávy.

Sada členů skupiny se mění pokaždé, když člen selže nebo se připojí, a Gbcast se také používá k udržení členství ve skupině pomocí speciálních vícesměrových vysílání, která se doručují do aplikace jako události „nového zobrazení“, ale které také upravují udržovaný seznam členů skupiny knihovnou protokolu Gbcast. Aplikace tedy vidí řadu pohledů na členství, které začínají „počátečním pohledem“, když se určitý člen skupiny připojí, a poté se vyvíjejí v průběhu času a které jsou řazeny s ohledem na jiné události měnící pohled a zprávy vícesměrového vysílání. Tyto vícesměrové vysílání se doručují všem nezklamaným členům uvedeným v zobrazení, během kterého je naplánováno doručení, vlastnost označovaná jako virtuální synchronizace.

Síťové oddíly mohou rozdělit skupinu na dvě nebo více disjunktních podskupin, což vytváří riziko rozdělit mozek chování, při kterém někteří členové skupiny přijmou rozhodnutí (možná vystartovat raketu), aniž by věděli, že nějaký jiný oddíl skupiny přijal jiné, protichůdné rozhodnutí. Gbcast nabízí ochranu před touto hrozbou: protokol zajišťuje, že k pokroku dojde pouze v jedné primární oddíl skupiny. Pokud by tedy vznikl síťový oddíl, nanejvýš jedna podskupina členů bude pokračovat v operacích, zatímco druhá se jistě zastaví a vypne.

Pokud by se člen, který selhal, zotavil (nebo pokud selhání rozdělení způsobilo, že některý člen byl nesprávně vnímán jako vadný, a proto spadl z pohledu), může se po obnovení komunikace znovu připojit. An inkarnační číslo se používá k zabránění nejednoznačnosti: čítač, který se zvýší pokaždé, když se proces připojí ke skupině, a považuje se za součást identifikátoru procesu. Libovolná daná n-tice (ID procesoru, ID procesu, číslo inkarnace) se ke skupině připojí nejvýše jednou, poté ve skupině zůstane, dokud selže, nebo je nucena odejít, protože došlo k vypršení časového limitu.

Jakýkoli dynamicky rekonfigurovatelný systém, včetně Gbcast i Paxos, může vstoupit do stavů, ze kterých již není možný žádný další pokrok. Například k tomu může dojít, pokud jsou provozní procesy nesprávně odebrány z konfigurace a v ostatních členech pohledu dojde k příliš mnoha skutečným zhroucením. V takových situacích je infrastruktura správy datového centra zodpovědná za restartování celé aplikace. To je na rozdíl od chování nerekonfigurovatelného (vanilka ) Paxos, který může tolerovat narušení na neomezenou dobu a poté bude pokračovat, jakmile bude k dispozici dostatek členů skupiny, bez zásahu do infrastruktury pro správu. V podrobném popisu protokolu jsou použity následující termíny.

Procesy

• Procesy běží na procesorech, které pracují libovolnou rychlostí.
• Procesy mohou narazit na selhání (zastavení).
• Proces je jednoznačně identifikován trojicí: (id procesoru, id procesu, číslo inkarnace).
• Procesy se stabilním úložištěm se mohou znovu připojit k protokolu po selhání (podle modelu selhání po zotavení z havárie), po zvýšení čísla inkarnace.
• Procesy se neshodují, nelžou ani se jinak nepokoušejí rozvrátit protokol. (To znamená, byzantské neúspěchy ^[10] nenastávají.)

Síť

• Všechny procesy v systému mohou odesílat zprávy všem ostatním procesům v systému.
• Zprávy jsou odesílány asynchronně: na doručení zprávy není časově vázán.
• Zprávy mohou být ztraceny, přeuspořádány nebo duplikovány.
• Zprávy jsou doručovány bez poškození.

Jedná se o slabé předpoklady: síť, která nikdy nedoručuje žádné zprávy, by je uspokojila (řekli bychom, že taková síť prochází úplným a trvalým selhání rozdělení). Níže jsou popsány podmínky sítě požadované pro Gbcast k zajištění pokroku. V praxi se Gbcast běžně používá v datových centrech; tito mají sítě, které mohou zaznamenat přechodná selhání, ale ve kterých jsou selhání rozdělení velmi vzácné a obecně mají dopad pouze na malé podmnožiny uzlů. Pro účely analýzy tedy předpokládáme tvrdší síťové prostředí, než jaké by vzniklo při skutečném nasazení.

Pro zjednodušení prezentace předpokládáme, že a TCP je použito schéma potvrzení / opětovného přenosu, které vytváří iluzi spolehlivého, sekvenovaného, ​​neopakujícího se kanálu zpráv mezi každou dvojicí procesů. A Časový limit nastane, pokud se tato abstrakce kanálu opakuje opakovaně a není schopna získat potvrzení pro nějakou zprávu. Pomocí stejných kanálů podobných protokolu TCP můžeme také podporovat schopnost 1: vše, kdy jediný proces posílá nějakou zprávu přes své kanály všem ostatním členům nějakého pohledu na nějakou skupinu. To se provádí mapováním požadavku 1: vše na více zpráv 1: 1. Všimněte si, že těmto kanálům 1 na všechny chybí záruka atomicity: pokud odesílatel selže při odesílání zprávy, může dosáhnout jen na některé z cílů.

Zpracujte skupiny a pohledy

Gbcast je definován s ohledem na „skupinu procesů:“ sadu procesů. V nasazeném systému může mít taková skupina název (například název souboru), způsob, jak nejprve kontaktovat skupinu, a další atributy, například parametry řízení toku. Tyto druhy podrobností jsou zde však pro stručnost vynechány.

Termín zobrazení členství je seznam členů seřazený podle věku (určený podle pohledu, ve kterém se každý člen naposledy připojil ke skupině) a s vazbami porušenými pravidlem lexikografického řazení.

Počáteční členství ve skupině určuje externí agent a definuje první pohled na členství ve skupině.

Následné zobrazení členství vznikne přihlášením přidat a odstranit příkazy a jsou identifikovány pořadovým číslem.

Nové pohledy jsou hlášeny do procesů patřících k tomuto pohledu prostřednictvím událostí „nového pohledu“. Aplikace je informována prostřednictvím upcall (volání z knihovny do obslužné rutiny definované aplikačním programem).

Multicast zprávy

Členové výběru mohou požadovat zasílání zpráv vícesměrového vysílání skupině procesů bez znalosti členství, které bude platit v době doručení.

Protokol Gbcast provádí tyto operace se sérií záruk, které jsou popsány níže.

Doručování probíhá upcall do aplikace, která může provádět jakoukoli akci, kterou zpráva požaduje.

Role

Gbcast lze nejlépe chápat z hlediska souboru rolí.

aplikace

Aplikace odpovídá programu, který lze spustit na jednom nebo více procesorech. Každý proces aplikace se poté připojí k jedné nebo více skupinám procesů.

Proces aplikace patřící do skupiny iniciuje nové vícesměrové vysílání vyvoláním Gbcast. Protokol se považuje za ukončený, když všichni členové cílové skupiny buď potvrdili doručení zprávy, nebo byli pomocí níže vysvětleného mechanismu detekováni jako vadní.

Příchozí zprávy Gbcast jsou doručovány prostřednictvím upcallů, stejně jako oznámení o změně zobrazení.

Jak již bylo zmíněno dříve, členové skupiny sledují stejnou posloupnost upcallů počínaje jejich počátečním připojením: počáteční pohled a poté sled nových pohledů a zpráv vícesměrového vysílání. Všichni členové skupiny obdrží jakékoli konkrétní vícesměrové vysílání ve stejném zobrazení a vícesměrové vysílání se doručí všem nezklamaným členům tohoto pohledu.

Vůdce

Vedoucí skupiny je definován s ohledem na určitý pohled na skupinu a je členem s nejnižší hodností v pohledu. Jak již bylo uvedeno, hodnost je seřazená podle věku (starší členové mají nižší hodnost) a vazby jsou narušeny pomocí lexikografického řazení.

Detekce poruchy

Všechny součásti systému mají povoleno účastnit se role „detekce“ poruch. Detekce se liší od hlášení selhání (k němuž dochází prostřednictvím nového pohledu a je objednáno s ohledem na doručování zpráv).

Abstrakce kanálu podporovaná síťovou vrstvou snímá selhání podle vypršení časového limitu. (Všimněte si, že v rámci modelu sítě bude proces, který se pokusí odeslat zprávu havarovanému cílovému procesu, vždy vypršet časový limit, ale je také možné, že abstrakce kanálu může chybně nahlásit provozní proces jako chybný, pokud jsou zprávy zpožděny kvůli přechodné selhání rozdělení).

Jakýkoli proces, u kterého dojde k vypršení časového limitu, může deklarovat, že koncový bod přidruženého kanálu selhal.

Pokud se proces dozví o selhání některé n-tice (ID procesoru, ID procesu, Incarnation-Number), zahrnuje tyto informace o další odchozí zprávě na všech kanálech.

Proces, který považuje nějaký jiný proces za neúspěšný, odmítne zprávy z neúspěšné inkarnace a odpoví „vy jste selhali“. (To znamená, že zpracovává drby o selháních a vyhýbá se neúspěšným členům skupiny).

S příchozí zprávou z nové inkarnace neúspěšného procesu se zachází jako se zprávou z „nového“ procesu.

Proces se nezdařil

Jakýkoli člen aktuálního pohledu, který byl detekován jako neúspěšný, je považován za neúspěšný proces.

Operační proces, který zjistí, že je považován za neúspěšný (pokusem o komunikaci s nějakým jiným procesem, který zprávu odmítne, čímž se jí „vyhne“), by mohl ze systému odejít, nebo může zvýšit své inkarnační číslo a znovu se připojit.

Nový vůdce

Pokud je každý proces s nižším hodnocením v aktuálním zobrazení neúspěšným procesem, je jako nový vedoucí označen další nejlépe hodnocený neúspěšný proces.

Aby se vedoucí stal novým vedoucím, musí spustit protokol popsaný níže.

Kvora

Kvora se používají k zajištění bezpečnostních vlastností Gbcastu zajištěním jediné globálně dohodnuté sekvence skupinových zobrazení a zpráv vícesměrového vysílání a zabráněním pokroku ve více než jednom oddílu, pokud dojde k fragmentaci skupiny na dva nebo více oddílů (disjunktní podmnožiny) členů, kteří mohou komunikovat s ostatními členy jejich podmnožin, ale ne s členy jiných podmnožin). Kvora jsou definována pro konkrétní pohled.

Daný pohled i s n členové {A, B, C….}, kvorum tohoto pohledu je jakákoli většinová podmnožina členů tohoto pohledu. Všimněte si, že je to na rozdíl od způsobu, jakým je tento pojem definován v systémech, které mají statické základní členství: u Gbcastu se velikost kvora bude v průběhu času měnit, jak se mění členství ve skupině a definují se nové pohledy.

Bezpečnostní a živé vlastnosti

Aby byla zajištěna bezpečnost, Gbcast definuje tři bezpečnostní vlastnosti a zajišťuje jejich zachování bez ohledu na vzor poruch:

Bezvýznamnost

Doručeny jsou pouze vícesměrové vysílání skutečně odeslané některým členem skupiny. Pokud proces obdrží zprávu od člena skupiny, kterou považuje za neúspěšnou, odmítne tyto zprávy.

Konzistence

Pokud kterýkoli člen pohledu doručuje vícesměrové vysílání (nebo hlásí nové zobrazení) v určitém pořadí ve srovnání s jinými vícesměrovými vysílání, pak všichni ostatní členové stejného pohledu, kteří doručují stejnou zprávu (nebo hlásí stejný pohled), tak učiní ve stejném objednat.

Podmíněná živost

Pokud vícesměrové vysílání M je odeslán v nějakém pohledu a odesílatel zůstane v provozu, pak nakonec všichni členové tohoto pohledu (s výjimkou jakéhokoli selhání) doručí M. Živost nelze zaručit za všech podmínek, proto ukládáme další podmínku: požadujeme tuto vlastnost pouze v případě, že dostatečně mnoho procesů zůstává nezávadných (o tom pojednáme níže).

Základní Gbcast

Tento protokol se používá za normálních podmínek.

Připomeňme, že v Gbcastu má každý operační proces aktuální pohled a každý pohled definuje vůdce. Pouze proces, který se považuje za vůdce v současném pohledu, může iniciovat nový multicast; ostatní členové musí předávat vícesměrové vysílání tak, že je pošlou vedoucímu, přes spojení 1: 1 a poté čekají na spuštění protokolu vedoucím.

Pokud vedoucí selže, zatímco se některý člen, který není vedoucí, pokouší předat vícesměrové vysílání, musí odesílatel určit stav jeho nevyřízeného požadavku. Toho lze dosáhnout následujícím způsobem: Všimněte si, že členové pozorují doručení svých vlastních vícesměrových vysílání. Pokud tedy bude definován nový pohled, ve kterém selhal starý vůdce, bylo doručeno vícesměrové vysílání (v takovém případě to odesílatel ví, protože to byl jeden z příjemců), nebo doručení nového pohledu mu umožňuje uzavřít že vůdce nedokázal předat nevyřízenou zprávu a že by měl být odmítnut tím, že požádá nového vůdce, aby ji předal (non-trivialita).

Připravte krok

Vedoucí navrhuje určitou sekvenci jedné nebo více zpráv vícesměrového vysílání pomocí spolehlivé síťové vrstvy 1: všichni k odeslání zprávy členům nejaktuálnějšího pohledu, přičemž každou identifikuje pomocí celočíselného pořadového čísla. Pořadová čísla se resetují na 1, protože každý nový pohled je definován (prostřednictvím speciálního druhu vícesměrového vysílání, jak je vysvětleno níže). Vedoucí „mluví sám se sebou“ a účastní se protokolu stejně jako ostatní členové. Během obnovy (popsáno níže) může nový vedoucí znovu navrhnout některé dříve navržené zobrazení nebo zprávu, protože se nový vedoucí pokusí dokončit protokoly, které starý vůdce mohl spustit, ale nepodařilo se ho dokončit. Když k tomu dojde, nový vedoucí bude respektovat původní řazení a znovu navrhne stejný pohled nebo zprávu.

Slibný krok

Každý příjemce si ponechá kopii zprávy (zpráv) a odpoví příslibem, že je doručí (takový příslib bude splněn, pokud samotný příjemce zůstane členem skupinového pohledu, ale pokud příjemce selže, příslib nemusí provést). Během obnovy může příjemce obdržet duplikovaný požadavek na přípravu stejné zprávy. Pokud je nějaká zpráva znovu navržena se stejným pořadovým číslem, příjemce jednoduše zopakuje svůj slib.

Krok spáchání

Vedoucí sbírá slibné zprávy, dokud u každého člena skupiny nemá buď slibovou zprávu, nebo nedošlo k vypršení časového limitu, což způsobí, že vedoucí podezřívá příslušného člena jako vadného (připomeňme, že v tomto druhém případě se vedoucí vyhýbá podezřelému členovi , a protože subsystém odesílání zpráv tyto informace přenáší na další zprávy, které odesílá, jakýkoli proces přijímající následnou zprávu od vedoucího se také začne vyhýbat těmto nově podezřelým členům).

Pokud vedoucí obdrží sliby z kvora členů, jak je definováno s ohledem na pohled, ve kterém protokol spouští, odešle spáchat žádost. Pokud vůdci chybí usnášeníschopnost, a proto má podezření na více než většinu členů skupiny, nebude již nikdy schopen dosáhnout pokroku a vedoucí proto ukončí (aplikační program se může ke skupině znovu připojit pomocí nového názvu procesu, ale další postup tímto procesem ve starém pohledu pod starým názvem procesu je nemožné).

Všimněte si, že vedoucí se také mohl dozvědět o selháních během fáze přípravy nebo fáze návrhu.

V přípravné fázi někteří členové pohledu pravděpodobně nepotvrdili požadavek na návrh, v takovém případě bude mít kanál vedoucího k těmto členům časový limit. Vedoucí je označil jako členy, kteří selhali.

Může se navíc stát, že po obdržení slibných zpráv ve fázi slibu se vedoucí dozvěděl o neúspěšných členech, které byly zjištěny jinými členy skupiny. Na začátku fáze potvrzení tedy má vedoucí kvorum slibů spolu s případně prázdným seznamem neúspěšných členů pohledu.

Vedoucí proto odešle zprávu „Potvrdit“ členům pohledu, kteří nezklamali, spolu s návrhem události změny pohledu, která z pohledu odebere člena (členy), který selhal, čímž spojí krok potvrzení a krok návrhu do jedné akce. Připomeňme, že jakmile dojde k jakékoli detekci selhání, první zpráva každému členovi ve skupině vezme zpět informace o detekci selhání a členové se vyhýbají členům, kteří selhali. Členové, kteří se dozvěděli o selhání, se tak okamžitě začnou vyhýbat selhávajícím členům a vedoucí provede další krok zahájením protokolu pro změnu pohledu (jehož dokončení pak bude nějakou dobu trvat).

Pokud návrh změnil pohled přidáním členů, vedoucí odešle nový pohled spojujícím členům; stane se jejich počátečním pohledem a oni se pak mohou účastnit jakýchkoli dalších běhů protokolu.

Během obnovy může účastník obdržet duplicitní potvrzení pro dříve potvrzenou zprávu. Pokud ano, vstupuje do doručovací fáze, ale nedoručuje zprávu ani pohled do aplikace.

Dodací krok

Pokud člen obdrží zprávu Commit, doručí přidružené zprávy nebo nové pohledy do aplikace v pořadí, v jakém byly navrženy vedoucím. Vedoucí zjistí, že tento krok uspěl, když jsou přijata potvrzení použitá spolehlivým kanálem 1: 1.

Tok zpráv: Základní Gbcast, nejjednodušší případ

(Velikost kvora = 2, zhlédnutí1 = {A, B, C})

Vedoucí členů Členové Aplikační vrstva A A B C A B C | | | | | | | | X --------> | | | | | | | Požádejte vedoucího o odeslání vícesměrového vysílání M | X ---------> | -> | -> | | | | Navrhněte (1.1: M) (pohled 1, sekvence 1, zpráva M) | | <--------- X - X - X | | | Slib (1.1) | X ---------> | -> | -> | | | | Potvrdit (1.1) | | <---------X--X--X------> M-> M-> M Committed (1.1); Přináší M | | | | | | | |

Případy chyb v základním Gbcastu

Nejjednodušší případy chyb jsou ty, ve kterých jeden nebo více členů selžou, ale kvorum zůstává aktivní. V níže uvedeném příkladu skupinu tvoří {A, B, C}, kde A hraje vůdčí roli. C selže během fáze slibu a ve spolehlivém kanálu dojde k vypršení časového limitu od vedoucího k procesu C. Vedoucí se tedy zaváže k dodání M, ale současně iniciuje protokol k odstranění C ze skupiny, která se zaváže, a vytvoří nový pohled {A, B}. Pokud C ve skutečnosti selhal, může se nyní znovu připojit ke skupině, ale s novým inkarnačním číslem: ve skutečnosti se C musí znovu připojit jako C '. Jakékoli zprávy z C do A nebo B budou odmítnuty od okamžiku, kdy se každý dozví o zjevném selhání: C bude vyhýbán A a B.

Tok zpráv: Základní Gbcast, selhání člena jiného než Leader

(Velikost kvora = 2, zhlédnutí1 = {A, B, C})

Vedoucí členů Členové Aplikační vrstva A A B C A B C | | | | | | | | X --------> | | | | | | | Žádost (M) | X ---------> | -> | -> | | | | Navrhnout (1.1: M) | | | | * | | * !! C FAILS !! | | <--------- X - X | | Slib (1.1) | X ---------> | -> | | | Potvrdit (1.1); Navrhnout (1.2: "odebrat C") | | <---------X--X---------> M-> M Committed (M); Dodává M; Slib (1.2) | X ---------> | -> | -> | | | Potvrdit (1.2); | | <---------X--X--X------> V-> V Committed (1.2); Poskytuje view2 = {A, B} | | | | | | 

Všimněte si, že závazek a nový návrh (a oznámení o neúspěšném selhání) jsou sloučeny do jedné zprávy. Tím je zajištěno, že jakýkoli proces, který spáchá akci poté, co byla detekována nová chyba, se současně o této chybě dozví a bude se vyhýbat přidruženému procesu a že tento proces bude rychle odstraněn z pohledu. Pokud C nezhroutil, může se znovu připojit zvýšením svého inkarnačního čísla (nyní se tedy jmenuje C ') a poté požádat, aby ho vedoucí přidal zpět do skupiny. Bude přidán do seznamu členů s novým názvem a bude mít nejvyšší hodnost (protože je to nejmladší člen) mezi členy pohledu.

Tok zpráv: Základní Gbcast, přidejte členy {D, E, F}, selhání jiného člena než vůdce

V níže uvedeném příkladu je skupina, která původně obsahuje členy {A, B, C}, požádána o přidání {D, E, F}, ale člen C během protokolu selže. Žádosti o změnu členství jsou považovány za speciální druh vícesměrového vysílání a sled událostí je stejný. Příklad je tedy téměř totožný s předchozím, ale nyní je do aplikace doručena řada nových událostí zobrazení. (Velikost kvora = 2, view1 = {A, B, C})

Vedoucí členů Členové Aplikační vrstva A A B C D E F A B C D E F | | | | | | | | | | | X --------> | | | | | | | | | | Žádost ("přidat D, E, F") | X ---------> | -> | -> | | | | | | | Navrhnout (1.1: "přidat D, E, F") | | | | * | | * | | | !! C FAILS !! | | <--------- X - X | | | | | Slib (1.1) | X ---------> | -> | | | | | | Potvrdit (1.1); Navrhnout (2.1: "odebrat C") | | <---------X--X-----X--X--X------> V-> V ----> V-> V-> V Závazek (1.1); Poskytnout view2 = {A, B, C, D, E, F}; Slib (2.1) | X ---------> | -> | ----> | -> | -> | | | | | | Potvrdit (2.1) | | <---------X--X-----X--X--X------> V-> V ----> V-> V-> V Závazek (2.1); Poskytnout view3 = {A, B, D, E, F} | | | | | | | | | | | |

Na konci protokolu je nové aktivní zobrazení view3 = {A, B, D, E, F} a nová velikost kvora je 3. Všimněte si však, že existovalo „přechodné“ zobrazení, view2 = {A, B , C, D, E, F} s kvorem velikosti 4. Kdyby vůdce neobdržel 4 sliby do fáze návrhu, která odstranila C, nebyl by schopen spustit fázi potvrzení pro view3. To ilustruje základní zásadu: kvorum potřebné k potvrzení nového pohledu je vždy založeno na velikosti předchozího pohledu.

Převzetí protokol, který se používá, když vůdce selže

Dalším případem selhání je selhání vůdce, jehož výsledkem je nový vůdce. Aby nový vůdce převzal pozici vůdce, nejprve provede protokol o převzetí a poté může nový vůdce spustit základní Gbcast, jak je uvedeno výše. Protokol o převzetí je následující:

Krok dotazu

Nový vůdce pošle 1:n zpráva vyslýchající členy, kteří nezklamali, aby se dozvěděli o všech zprávách, které slíbili doručit.

Krok seznamu slibů

Každý příjemce odešle vedoucímu aktuální seznam slíbených zpráv. Pokud příjemci chybí původní pohled, odešle požadavek na úvodní pohled vedoucímu.

Nový vedoucí čeká, dokud neobdrží seznam příslibů od každého z členů, které kontaktoval, nebo vypršel časový limit. Pokud dojde k vypršení časového limitu, nový vedoucí podezřívá dotyčného člena a bude se mu vyhýbat, stejně jako ostatní členové, s nimiž kontaktuje. Nakonec navrhne pohled, který tyto vyloučené členy vylučuje, jak je vysvětleno níže.

Opakujte, pokud je to nutné

Nový vedoucí zkoumá seznam slibů a hledá zprávy o změně členství, které přidávají nové členy. Pokud jsou k dispozici, iteruje fázi dotazu a fázi sběru seznamu slibů a zasílá dotazy novým členům. To by zase mohlo vést k objevení dalších návrhů, které přidají ještě další členy. Proces končí, když každý člen (současný nebo navržený k přidání) odpověděl seznamem slibů nebo byl podezřelý novým vůdcem.

Zkontrolujte kvora

Na konci fáze dotazu vůdce obdržel slibné odpovědi od některých procesů, které kontaktoval; budou nyní podezřelí všichni neodpovídající členové. Nový vůdce vytvoří seznam navrhovaných pohledů. Aby mohl nový vedoucí postoupit do dalšího kroku návrhu převzetí, musí obdržet kvorum odpovědí od každého ze závazných nebo navrhovaných názorů na tomto seznamu. Pokud se mu nepodařilo získat kvorum odpovědí na jakékoli potvrzené nebo navrhované zobrazení v seznamu, nový vůdce nepřevzal vedení jako vůdce a nikdy neuspěje. Ukončí protokol a musí se znovu připojit k systému jako nový člen pomocí nového inkarnačního čísla procesu.

Začněte jako nový vůdce

Po úspěšném ověření kvora se nový vůdce stává vůdcem. Nyní může spustit základní protokol. Znovu navrhuje všechny slíbené zprávy nebo změny zobrazení v pořadí, v jakém se je naučil ze seznamů slibů, a následuje je novým příkazem pro změnu zobrazení, který odstraní starého vůdce a všechny ostatní členy, kteří během fáze dotazování neodpověděli. . Pokud kterýkoli člen během fáze seznamu příslibů odpověděl, že mu chybí původní pohled, nový vedoucí pošle příslušnému počátečnímu pohledu příslušného člena.

Soubojoví vůdci

Je možné, že seznamy příslibů obsahují dva nebo více odlišných návrhů pro stejný slot. K tomu dochází (pouze), pokud se první vedoucí A stal oddělením od systému, ale přesto podal návrh X to viděla jen malá (ne kvora) sada členů. Nový vůdce B poté úspěšně převzal vedení, ale nedozvěděl se o návrhu A (který nemohl být spáchán). B nyní navrhuje Y, opět u malé menšiny členů. Nyní se předpokládá, že B selhal a C převezme kontrolu. Je možné, aby se C dozvěděl o návrzích X a Y, pro stejný slot. C by měl ignorovat návrh spojený se starším vůdcem, A, ale ponechat si návrh spojený s novějším vůdcem, B: v této situaci návrh X nemohla dosáhnout usnášeníschopnosti, a tudíž nemohla být spáchána, zatímco návrh Y předložený novějším vůdcem by mohl být spáchán (jinak, to znamená, že pokud by bylo možné dosáhnout X kvora, B by se o tom dozvěděl a tudíž opakovaný návrh X; tedy proto, že B se o tom nedozvěděl X, X nemusí být usnášeníschopné).

Všimněte si, že protokol převzetí C používá k určení tohoto návrhu deterministické uspořádání mezi vedoucími A a B. X je odsouzena k zániku, protože vůdce B se musel vyhýbat A, aby se stal vůdcem. Naopak C musí předpokládat, že návrh Y se může stát spáchaným, i když A měl podezření, že B selhal, protože návrh Y se protínal s krokem převzetí C. Pravidlo je implementováno: postupným číslováním vůdců a zahrnutím čísla vůdce do návrhu. Během kroku dotazování může nový vedoucí použít návrh od vedoucího s větším počtem, pokud obdrží konfliktní návrhy pro stejný slot.

Podezření na selhání Piggyback u odchozích zpráv

Všimněte si, že nový vůdce věří, že selhal starý vůdce, a může také věřit, že selhali ostatní členové. Fáze dotazu a nebo nová fáze návrhu tedy mohou také nést zprávy o neúspěšném selhání pro jednoho nebo více členů. This is a central requirement for the protocol, because it ensures that those members will subsequently be shunned: if further communication is received from a shunned member, the receiver will reject those messages. It follows that if any member executes the promise-list phase for an old leader L, no further propose or commit messages from L will be processed by that member. From this we can see that the promise-list collected by the new leader will be complete, containing all promised messages that could possibly have achieved a quorum in the current view. It may also contain some additional promised messages that have not yet achieved a quorum.

Message flow: Basic Gbcast, failure of Leader, TakeOver, Basic Gbcast by the new leader

(Quorum size = 2, view 1={A,B,C})

Member   Leader        Members      Application Layer          A  B          A  B  C       A  B  C  | | | | | | | | X----->| | | | | | | Request(M)  | X------------>|->| | | | | Propose(1.1: M) !! Leader fails during send, Propose doesn't reach C !! | *<------------X—-X  | | | | Promise(1.1)   | | *  | | *  | | !! A (THE LEADER) HAS FAILED !! | | | | | | !! NEW LEADER: B !! | ?------------>|->| | | Inquire("B is taking over because A has failed")  | |<------------X--X          | | PromiseLists(1.1: M)  | X------------>|->| | | Propose(1.1: M); Propose(1.2: "remove A")  | |<------------X--X--------->| | Promise(1.1); Promise(1.2)   | X------------>|->|--------->| | Commit(1.1); Commit(1.2); | |<------------X--X-------->M;V->M;V  Committed(1.1); Committed(1.2); Delivers(M). Delivers view2={B,C}

Message flow: Basic Gbcast, Add members {D,E,F}, failure of the Leader

As an example of a more complex case, here the leader fails in the middle of a commit that increases the size of the view

(Quorum size = 2, view 1={A,B,C})

Member   Leader        Members                Application Layer          A  B          A  B  C  D  E  F       A  B  C  D  E  F  | | | | | | | | | | | | | | X----->| | | | | | | | | | | | | Request("add D, E, F")  | X------------>|->| | | | | | | | | | | Propose(1.1) !! Leader fails during send, Propose doesn't reach C !! | *<------------X—-X  | | | | | | | | | | Promise(1.1)   | | *  | | | | | *  | | | | | !! A (THE LEADER) HAS FAILED !! | | | | | | | | | | | | !! NEW LEADER: B !! | ?------------>|->| | | | | | | | | Inquire("B is taking over because A has failed")  | |<------------X--X  | | | | | | | | PromiseLists(1.1: "add D, E, F"); | ?-------------|--|->|->|->| | | | | | Iterated Inquire("B is taking over because A has failed")  | |<------------|--|--X--X--X          | | | | | PromiseLists(1.1: "add D, E, F"); | X------------>|->|->|->|->| | | | | | Propose(1.1: "add D, E, F"); Propose(2.1: "remove A")  | |<------------X--X--X--X--X          | | | | | Promise(1.1); Promise(2.1); | X------------>|->|->|->|->| | | | | | Commit(1.1); Commit(2.1); | |<------------X--X->X->X->X -------->V->V->V->V->V  Committed(1.1); Committed(2.1); Delivers                                                                   view2={A,B,C,D,E,F}. Delivers view3={B,C,D,E,F}

In this example we see the inquiry iteration "in action": B learns of the protocol that adds {D,E,F} in a first phase of the inquiry, hence it repeats the inquiry, this time contacting D, E and F. There is no need to repeat the inquiry at C since this would simply return the same information previously obtained.

In this example, the final commit actually causes two views to be delivered in succession at members B and C. Even though the two proposals were sent concurrently, the commit for view2 requires a promise from a quorum of view1, whereas the commit for view3 requires a quorum response from the members of view2. Although the sending of initial views isn't explicitly shown in the diagram, the joining members don't participate in the 1.1 protocol because they don't join the group until view2. Notice that at members B and C a pipelining effect arises: events associated with view2 are already being proposed even as events in view1 are still being committed.

Správnost

To show that Gbcast satisfies non-triviality we start by tracing backwards from an arbitrary delivery action to the point at which a client requested the corresponding event; clearly, only messages that were legitimately sent will be delivered. However, nontriviality for this protocol goes further: we must also show that messages from a given member are delivered only while that member is still a live participant in some view. Accordingly, we look at the case in which the leader initiates some multicast but then fails before it is delivered. Here, the new leader either discovers the pending proposal, and will order it before the view-change event, or the new leader fails to discover the pending proposal, in which case all members of the new view will shun any late-arriving incoming message from the old leader. Thus either a multicast message is delivered while the view in which it was sent is still pending, or it will not be delivered at all.

To establish consistency we begin by analysis of the case in which there is just a single leader that never fails or loses connectivity with a quorum. Since the leader sequences the events and includes each member starting with the first view that contains that member, all members deliver the identical messages starting from the view in which they were added to the system.

When a new leader takes over, the inquiry is required to reach a quorum of members for the most recent committed view. This quorum necessarily will include at least one process that received any proposal that the old leader could have committed. Thus the new leader will learn of any potentially committed proposal and include it as a preflix to its own new proposals. It follows that if any process delivers any event, then if the system makes progress, every surviving member will eventually deliver that same event and in the same order.

We can show that a joining member will receive its initial view by analysis of the two relevant cases. If the leader doesn't fail, it sends the initial view on an eventually reliable channel. If the leader does fail and some member lacks its initial view, the new leader sends that view after receipt of the "promise-list" response to its inquiry-phase message.

A logical partitioning of the group is impossible because of the shunning rule. In order to commit any new view, the old leader must obtain promises from a quorum of the current view. A new leader, taking over, will learn of any view that could have become committed. To commit its own proposed next view, it will thus be required to interact with a quorum of that intermediary view, if any. In a scenario that could lead to partitioning, the leader, A, might have timed out on B and gone on to create a sequence of new views and events that excluded B. But in this case a majority of the old or of the intermediary view members will have learned that A believes B to have failed, and will shun B when it inquires. In either case, B is prevented from obtaining a quorum and hence cannot make progress. A symmetric argument shows that if B succeeds in defining a new view that excludes A, A would be unable to obtain a quorum for any other new view that it might attempt to propose.

Liveness

The Gbcast protocol will make progress provided that at all times in the execution, if view proti drží v čase t, then less than a quorum of members of proti fail (or are suspected as failing) within some subset of the members of the view. To maximize progress, it is important that excluded but still live members rejoin the group, so that erroneous failure detections don't cause the view to shrink in a persistent manner. However, the protocol will not recover and make progress if at any time, every process suspects more than a quorum of members of the current view of having failed.

This property is similar to but "stronger" than <>W, the "weakest failure detector" for achieving consensus, as defined by Chandra and Toueg. To see this, consider a run in which a mutually suspecting quorum arises "too quickly" for processes that have been wrongly excluded from the view to rejoin it. Gbcast will not make progress and, indeed, the group will need to shut down and restart.

Arguably, such runs would be unlikely in the kinds of data centers where Gbcast is typically used, but clearly they can be constructed in an adversarial manner.

Discussion: Failure sensing

The Gbcast protocol presumes that the probability of incorrect failure suspicions will be low; the scheme breaks down if failure suspicions occur frequently and operational processes are often suspected as faulty. By analogy, consider the TCP protocol, in which the failure to receive an acknowledgement will eventually cause a connection to break. TCP is used nearly universally, a tremendous disruption to the Web would result if TCP connections frequently were to break when neither endpoint has failed. Thus timeouts are set conservatively. A similar assumption is required for systems that use Gbcast.

In contrast, there are other failure detection schemes, such as the one explored by Chandra and Toueg, that can yield high rates of incorrect failure suspicions. Some protocols, including Paxos, are able to tolerate incorrect failure suspicions without any costly consequence. Whether one approach is inherently better than the other is beyond the scope of this discussion. We simply underscore that the approaches differ, and that Gbcast would be ineffective if timeouts are set overly aggressively.

One extreme scenario is worthy of further mention: network partitioning events. Modern data centers and networks often experience events in which a single machine and all the processes on it becomes transiently partitioned from a larger pool of machines that remain connected to one another. Such cases are treated as failures in Gbcast, but if the surviving, connected members include a sufficiently large number of processes, the majority portion of the system will simply reconfigure itself to exclude the disconnected member. It can reconnect and rejoin the group later when the partition heals.

A more extreme kind of partitioning is sometimes seen in data centers: in this situation, a network switch might fail, causing a collection of machines (perhaps, a whole rack or even an entire container) to become disconnected from the Internet and from the remainder of the data center. In such cases one could imagine a group in which all members begin to suspect all other members; Gbcast will not progress in this case and the management infrastructure would need to relaunch the entire application. On the other hand, in most large data centers, the operating systems of the machines experiencing such a failure would also shut down, restarting only when connectivity is restored. Thus in practice, the restart of the system is unavoidable. This said, there are protocols, such as Paxos, that could ride out such an outage if the machines themselves were to remain operational and later regained adequate connectivity.

The Transis system explored extensions to the Gbcast protocol that permit multiple partitions to form, to make independent progress, and then to remerge. This topic, however, is beyond the scope of the present discussion.

Discussion: Dueling leaders

In the Paxos protocol, a situation can arise in which two or more leaders "duel" by proposing different commands for the same slot. This can also occur in Gbcast.

In the normal sequence of events, one leader takes over because the prior leader has failed, learns of any proposals the prior leader made during the inquiry phase, and then repeats those same proposals, extended with new ones. Thus no duel over the content of slots arises because the same proposals are repeated in the same slots.

The closest situation to a duel is seen if the old leader has become partitioned from the majority and the new leader, taking over, is unable to contact some set of members (but does obtain the required quorum during the INQUIRE phase). Here the new leader may be unaware of some proposals that the old leader made, or might still issue, if those reach only the members the new leader didn't contact.

The shunning mechanism resolves such duels. When the new leader obtained a quorum during the INQUIRE phase, it also blocked the old leader from ever again achieving a quorum for any new PROPOSE it might initiate: a majority of members are now shunning the old leader. Thus if any proposal is missed by the new leader it necessarily is a proposal that didn't reach a quorum of members, and won't reach a quorum in the future. Moreover, members aware of such a proposal will be shunned by the new leader, since (when it gave up waiting for them to respond to its INQUIRE) it considers them to have failed. Any member learning of new proposals from the new leader will shun them as well.

Shunning of leaders in Gbcast occurs in the pre-determined order of leader ranks: a higher-ranking leader only shuns a lower-ranking leader when it tries to take-over its place. The Paxos ballots mechanism serves precisely the same purpose, but differs in allowing participants to attempt to take-over repeatedly, eaach time assuming a new ballot ("rank"). The result is that, one the one hand, Paxos leader demotion is reversible, and on the other, dueling leaders could theoretically continue forever.

Bi-simulation equivalence to Paxos

Although superficially quite different, upon close study Gbcast is seen to be surprisingly similar to Paxos. Indeed, Paxos can be "transformed" into Gbcast with the following (reversible) sequence of steps. For brevity we describe these steps informally and omit a detailed proof.

Note that this transformation does not address durability. Gbcast treats durable state as a property of the application, not the protocol, whereas Paxos logs events to a set of durable command logs, and hence can still recover its state even after the whole service is shut down and restarted. The equivalent behavior with Gbcast involves having the application log all received messages, but that case will not be considered here.

1. Začněte s basic Paxos protocol. Add a process incarnation number to distinguish a rejoining process from one that has been continuously a member of the view. Impose an age-based ordering on the members of the group, designate the oldest member (breaking ties lexicographic) as the leader. Non-leaders issue requests through the leader.
2. Both protocols permit batching of requests: Basic Paxos has a concurrency parameter, alpha: a leader can concurrently run a maximum of alpha instances of the protocol. Gbcast permits the leader to propose multiple events in a single protocol instance, which could be message deliveries or view events.
3. Paxos does not normally require reliable, ordered communication. Modify the protocol to run over the reliable one-to-one channel abstraction (a one-to-many message would be sent by Paxos over a set of one-to-one channels). We can now assume that any message sent will either be received and delivered in order, or that a timeout will occur at the sender side.
4. The Paxos slot number will become the Gbcast sequence number. The Paxos ballot number is, in effect, transformed into the proposing leader-number used to discriminate between conflicting proposals during the inquire step.
5. Define a category of view-modifying commands that operate by adding or removing processes from the group membership. Introduce a failure detection mechanism as used in Gbcast, asking the leader to remove any timed-out members. A member removed from the group that reestablishes connectivity to the group should rejoin with a new incarnation number. Report views by upcalls to the application.
6. Basic Paxos can propose a multicast to just a quorum of group members, hence a typical member may have gaps in its command list. This is why, in Paxos, a learner must read a quorum of members and merge their command lists. In our modified protocol, any multicast is proposed to all non-failed members, while failed members are dropped from the view. Thus unlike Paxos, our modified protocol has the property that any single live member has the full committed event list. In effect, the protocol has a write quorum equal to the current membership view size, and a read quorum of 1. This can be convenient when building applications that maintain the actual state of a database or object and for which it is inconvenient to represent state as a series of updates in command lists that must be merged to learn the actual sequence of events.

The same quorum mechanisms that define Paxos, including the inquiry used when a new Paxos leader takes over, are now seen to correspond precisely to the steps of Gbcast. The ballot mechanism, generally viewed as the hallmark of Paxos protocols, reduces to a counter that tracks the order of succession of leaders. This simplification is fundamentally due to the guarantee that once a leader is suspected, it will be removed from the view and would need to rejoin before participating in the protocol.

It follows that Gbcast and Paxos can be transformed, each to the other, without changing assumptions and with the identical correctness properties. Obviously, the protocols don't look very similar, but they have a deep connection. Indeed, one can make a stronger claim: any sequence of delivery events exhibited by Gbcast can also arise in some run of Paxos, and vice versa: any sequence of learned events from Paxos can also arise in some run of Gbcast.

The type of proof outlined above is formally called a bi-simulation: one shows that any (input-sequence, output-behavior) pair that one protocol can exhibit is also possible with the other protocol. Notice that in carrying out a bisimulation, features that one protocol supports but the other lacks can be ignored if they are not considered to be part of the "behavior" being studied. For example, the Gbcast reporting of new views (events that Paxos lacks) are not treated as output events here.

Summary of differences between Paxos and Gbcast

• Gbcast has no durable state: the protocol does not maintain a log of events on disk, and durability is treated as an application-specific property. In contrast, Paxos guarantees durability: after recovering from a complete shutdown of the system, a Paxos application will still be able to learn the full log of received messages.
• In the propose phase, Gbcast must wait for responses from all participants (or for the maximal timeout and then suspect the remaining ones), instead of making progress with the fastest quorum. In Gbcast, the cost of a failure suspicion is high and the protocol may cease to make progress if too many failures are suspected, forcing a management layer to restart the entire application group. Thus, in practice, Gbcast requires conservative timeout settings relative to Paxos.
• With Gbcast, if an error does occur (e.g. an operational process is suspected and shunned), that process must drop out (it can rejoin under a different name). With Paxos, if f>0, should a process be unable to participate in a protocol instance, it can continue to participate in subsequent protocol instances without error.
• Operational members of a view will never have gaps in their command lists with Gbcast (every member has a complete state). Operational members can have gaps in their command lists when using Paxos (learners merge a quorum of lists in Paxos to "fill" these gaps).
• With Paxos, to propose multiple commands we use alpha>1, but in this case commands can be committed in a different order from the order in which they were initiated (one case in which this problematic scenario is seen involves dueling leaders; leader A proposes commands a1 and a2, and leader B proposes commands b1 and b2; both then fail and leader C, taking over, ends up committing b2, and then a1: an outcome that might not be desired by the applications that initiated the requests ^[11]). With Gbcast, the leader can initiate multiple commands by issuing a single propose that describes a series of actions. The group will be committed all at once, hence the order of initiation will be respected.
• With Gbcast, a command is delivered in the view in which it was initiated. Reconfigurable Paxos can commit a command in a slot associated with a membership view prior to the active membership view at the time when the commit occurs. Thus, in Paxos, if an application is in some way view sensitive, commands must carry a view identifier, so that recipients can determine whether or not the command is still executable.
• Gbcast does not require that the protocol be halted when changing configurations: the rate of new proposals can be constant even across membership changes. For many implementations of reconfigurable Paxos, this would not be the case.
• With both Gbcast and Paxos, reconfiguration is only possible if a quorum of the prior view is accessible and can acknowledge the new view. However, in Paxos, the requirement also extends to learning the outcomes of commands proposed for slots associated with the old view. In practice, this can cause the Paxos reconfiguration computation to extend over a longer period than for Gbcast, in which any state is stored within the application, not a long-lived command list: Paxos cannot discard the state associated with an old view until the new view is active and any replicas have learned the old state.
• Gbcast does not require a garbage collection protocol because, as each message or view is committed and reported to the application it can be discarded. Paxos maintains state using a quorum scheme in the command logs at its acceptors, and requires a garbage collection protocol to free these command slots once the outcome is committed and all learners (replicas) have learned the outcome.

Liveness comparison

Both Paxos and Gbcast are subject to the FLP impossibility result.^[9] Thus neither protocol can be guaranteed live under all possible conditions. At best we can talk about the conditions under which liveness is guaranteed, expressed as predicates on the failure detection mechanism: if the condition for liveness holds, then the protocol will be live. The liveness conditions of Basic Paxos and Gbcast are similar but not identical.

In Gbcast, progress will nikdy resume if a circle of mutual suspicions arises, as noted above: once a quorum of mutually shunning processes arises, the shunning mechanism makes it impossible for any leader to obtain a quorum of promises.

With an (unmodified) Paxos protocol, this problem will not arise: once the excessive level of mutual suspicions ends, progress resumes. Thus Paxos makes progress with any failure-detection mechanism satisfying the <>W condition, even if periods arise during which more than a quorum of mutual suspicions occur.

For example, if we start with a group containing {A.B,C} and cause an extended network partition, Paxos would resume when the network partition resolves but Gbcast will shut down permanently and some form of management infrastructure may need to restart the system. If it is necessary to preserve group state across the failure, such an infrastructure would identify the last member to fail and restart the group using some form of checkpoint stored by that last member.

In Paxos deployments, it is common to require human operator intervention to reconfigure Paxos. In such settings, Gbcast may be able to make progress during period when Paxos cannot. Suppose that a group has membership that slowly drops to less than a quorum of the original group size. Gbcast can continue to operate with even a single member. Paxos would cease to make progress during periods when less than a quorum of its view are active.

Need for state transfer

Systems such as Isis that implement Gbcast typically provide a state transfer mechanism: at the instant the new view showing some joining member is delivered, some existing member makes a checkpoint of its copy of the group state. This is then copied to the new member, which loads the checkpoint as the initial group state as of the instant it joined. (Various out-of-band copying schemes can be used to pre-load some state prior to the join for cases where the state is too large to transfer at the last moment this way). State transfer is needed because in Gbcast, once a member is dropped from a group, it will no longer receive updates. Gbcast is typically used by applications that maintain their state in memory and apply updates one by one as received, hence once a gap arises, a replica is no longer useful.

Notice that this is in contrast to Paxos. In that protocol, gaps can arise as a consequence of the basic quorum update scheme, which doesn't guarantee that every member will see every update and can run over unreliable message passing layers that might never deliver some messages. The Paxos learner algorithm reads multiple histories and combines them to fill such gaps. Thus Paxos will normally ride out transient failures, continuing to operate without actually dropping the failed member from the group. The failed member misses updates, yet state transfer is not needed unless a group is being reconfigured.

Which dynamically reconfigurable state machine replication protocol came first?

The Gbcast protocol was published early in a period when several state machine protocols capable of managing their own membership were introduced: Gbcast, View-Stamped Replication (Oki and Liskov ^[12]), Basic Paxos (Lamport ^[5]), the partial synchrony protocol of Dwork, Lynch and Stockmeyer,^[13] etc. Among these, Gbcast was the first to be published, in papers that appeared in 1985 and 1987; the others were published starting in 1988. One could thus argue that Gbcast was really the first Paxos protocol. Such a statement, however, treats "Paxos" as a fairly broad term covering a family of protocols that all implement state machine replication, all support dynamic reconfiguration of their membership, and have identical correctness properties but vary in their liveness conditions. Under this definition, Gbcast is a Paxos protocol.

If equivalence is formalized using bisimulation, in which any run that one protocol can exhibit is also exhibited by the other, and in which the assumptions made and the conditions for progress are identical, the comparison becomes more complex. Under this definition, Gbcast is not a Paxos protocol: although each can exhibit the same runs as the other (viewed purely in terms of requests from the application and notifications to the application), they have similar, but not identical, liveness conditions. However, this sort of stringent definition poses a different problem: if one adopts it, some versions of Paxos are not Paxos protocols. For example, "Cheap Paxos" and "Vertical Paxos" are not bisimulation-equivalent to Basic Paxos.^[14]

Thus the question has no answer unless one makes it more specific, and has a different answer depending upon the definition of equivalence one uses.

Viz také

• Paxos (computer science)
• Virtuální synchronizace
• Atomové vysílání
• Konsenzus (počítačová věda)
• Spolehlivé vícesměrové vysílání

Reference