Паксос је скуп протокола за решавање консензуса у мрежи непоузданих процесора. Консензус представља договор међу групом учесника. Проблем настаје када учесници или њихова комуникација могу доживети неуспехе.

Протоколи консензуса су основа за приступ репликације машине стања за дистрибуирано рачунарство, као што је предложио Лесли Лампорт и испитао Фред Шнајдер. Репликација машине стања је техника за претварање алгоритма у дистрибуирану имплементацију отпорну на грешке.

Паксос протокол је први пут поднет 1989. године и назван је по измишљеном систему законодавног консензуса који се користи на острву Паксос у Грчкој, где је Лампорт написао да парламент мора да функционише „иако су законодавци непрестано лутали и излазили из парламентарне коморе“. Leslie Lamport's history of the paper Касније је објављен као чланак у часопису 1998.

Паксос скуп протокола укључује компромисе између броја процесора, броја кашњења порука пре учења договорене вредности, нивоа активности појединачних учесника, броја послатих порука и типова грешака. Иако ниједан детерминистички протокол толерантног консензуса не може гарантовати напредак у асинхроној мрежи, Паксос гарантује доследност и тешко је изазвати услове који би га могли спречити да напредује.

Паксос се обично користи тамо где је потребна издржљивост (на пример, за реплицирање датотеке или базе података ), у којој количина трајног стања може бити велика. Протокол покушава да напредује чак и током периода када одређени број реплика не реагује. Такође постоји механизам за испуштање трајно неуспеле реплике или за додавање нове реплике.

Историја Године 1988, Линч, Дворк и Стокмајер су демонстрирали решивост консензуса у широкој породици „делимично синхроних“ система. Паксос има велике сличности са протоколом који се користи за договор у „репликацији са печатом погледа“, који су први пут објавили Оки и Лисков 1988. године, у контексту дистрибуираних трансакција. Без обзира на овај претходни рад, Паксос је понудио посебно елегантан формализам и укључио један од најранијих доказа безбедности за дистрибуирани консензус протокол отпоран на грешке.

Реконфигурабилне машине стања имају јаке везе са претходним радом на поузданим групним протоколима који подржавају динамичко чланство у групи, на пример Бирманов рад из 1985. и 1987. на виртуелно синхроном протоколу групног емитовања. Међутим, групно емитовање није уобичајено у подршци издржљивости и решавању грешака при партиционисању. Већина поузданих групних протокола немају ова својства, која су потребна за имплементацију модела репликације машине стања. Ова тачка је разрађена у раду Лампорта, Малкхија и Зхоуа.

Паксос протоколи припадају теоријској класи решења проблема формализованих као једногласно слагање са падом система. Дерецо, C++ софтверска библиотека за репликацију машина стања у облаку, нуди Паксос протокол који је интегрисан са самостално управљаним виртуелно синхроним чланством. Овај протокол се ефикасно пресликава на савремени хардвер удаљеног ДМА (РДМА) центра података (али користи ТЦП ако РДМА није доступан).

Претпоставке Да би се поједноставила презентација Паксоса, следеће претпоставке и дефиниције су представљене.

Процесори

Процесори раде произвољном брзином. Процесори могу доживети кварове. Процесори са стабилном меморијом могу поново да се придруже протоколу након кварова (пратећи модел неуспеха приликом опоравка од пада). Процесори се не договарају, не лажу или на други начин покушавају да поткопају протокол. (То јест, византијски неуспеси се не дешавају.)

Мрежа

Процесори могу слати поруке било ком другом процесору. Поруке се шаљу асинхроно и слање поруке може трајати произвољно дуго. Поруке се могу изгубити, променити редослед или дуплирати. Поруке се испоручују без оштећења. (То јест, византијски неуспеси се не дешавају.)

Број процесора Генерално, консензус алгоритам може напредовати користећи процесора, упркос истовременом квару било ког од процесора: другим речима, број исправних процеса мора бити стриктно већи од броја неисправних процеса. Међутим, коришћењем реконфигурације, може се користити протокол који преживи било који број укупних кварова све док не више од Ф истовремено не успе. За Паксос протоколе, ове реконфигурације се могу руковати као засебне конфигурације .

Својства сигурности и животности Да би гарантовао безбедност, Паксос дефинише три својства и обезбеђује да се прва два увек поштују, без обзира на образац кварова:

Ваљаност (или нетривијалност ) Само предложене вредности се могу изабрати и научити. Споразум (или доследност, или безбедност ) Ниједна два различита ученика не могу научити различите вредности (или не може бити више од једне одређене вредности) Раскид (или животност) Ако је предложена вредност Ц, онда ће на крају ученик Л научити неку вредност (ако довољан број процесора остане без грешака).

Имајте на уму да Пакос не гарантује да ће се прекинути, па стога нема својство животности. Ово је подржано резултатом немогућности Фишера Линча Патерсона (ФЛП) који каже да протокол конзистентности може имати само два од следећег: безбедност, животност и отпорних на грешке . Како је поента Паксоса да обезбеди толеранцију грешака и гарантује безбедност, не може да гарантује и животност.

Типичан развој У већини имплементација Паксоса, сваки процес који учествује има три улоге; Предлагач, прималац и ученик. Ово значајно смањује сложеност поруке, без жртвовања исправности.

Спајањем улога, протокол се „колапсира“ у ефикасну примену стила клијент-мастер-реплика, који је типичан за базе података. Предност Паксос протокола (укључујући имплементације са спојеним улогама) је гаранција његових безбедносних својстава .

Основни Паксос Овај протокол је најосновнији у породици Паксос. Свака „инстанца“ (или „извршење“) основног Паксос протокола одлучује о једној излазној вредности. Протокол се одвија у неколико рунди. Успешна рунда има 2 фазе: фазу 1 (која је подељена на делове а и б) и фазу 2 (која је подељена на делове а и б). Претпостављамо асинхрони модел, тако да нпр. процесор може бити у једној фази, док други процесор може бити у другој.

Фаза 1

Фаза 1а: Припрема

Предлагач креира поруку, коју зовемо "Припрема", означену бројем н, који представља само број који јединствено идентификује ову почетну поруку предлагача (која се шаље примаоцима). Број н мора бити већи од било ког броја који је овај предлагач користио у било којој од претходних порука. Затим шаље поруку Припрема која садржи најмање н кворум прималаца. Имајте на уму да порука Припрема садржи само број н (то јест, не мора да садржи нпр. предложену вредност, често означену са в). Предлагач одлучује ко је у Кворуму. Предлагач не би требало да покрене Паксос ако не може да комуницира са најмање Кворумом прималаца.

Фаза 1б: Обећање

Било који од Прималаца чека поруку Припреми од било ког Предлагача . Ако прималац прими поруку припреме, мора да погледа идентификациони број н управо примљене поруке припреме . Постоје два случаја.

Ако је н већи од сваког претходног броја који је прималац примио од било ког предлагача, онда он мора да врати поруку (коју називамо „обећање“) предлагачу, да игнорише све будуће предлоге који имају мањи број. него н . Ако је прималац прихватио предлог у неком тренутку у прошлости, он мора укључити претходни број предлога, рецимо м, и одговарајућу прихваћену вредност, рецимо в, у свом одговору предлагачу.

У супротном (то јест, н је мање или једнако било ком претходном предлогу који је прималац примио од било ког предлагача), прималац може да игнорише примљени предлог. У овом случају не мора да одговари да би Паксос радио. Међутим, ради оптимизације, слање одговора о одбијању би рекло предлагачу да може зауставити свој покушај да створи консензус са предлогом н .

Фаза 2

Фаза 2а: Прихватање

Ако предлагач прими обећања од кворума прималаца, он треба да постави вредност в свом предлогу. Ако је било који прималац претходно прихватио било који предлог, онда ће своје вредности послати предлагачу, који сада мора да постави вредност свог предлога, в, на вредност повезану са највећим бројем предлога који су пријавили примаоци , назовимо то з. Ако ниједан од прималаца није прихватио предлог до ове тачке, онда предлагач може изабрати вредност коју је првобитно желео да предложи, рецимо к .

Предлагач шаље поруку прихватања, (н, в), кворуму прималаца са изабраном вредношћу за његов предлог, в, и бројем предлога н (који је исти као број садржан у поруци припрема која је претходно послата примаоцима). Дакле, порука прихватања је или (н, в=з) или, у случају да ниједан од прималаца претходно није прихватио вредност, (н, в=к) .

Фаза 2б: Прихваћено

Ако Прималац прими поруку о прихватању (н, в) од предлагача, мора је прихватити ако и само ако већ није обећао (у фази 1б) да ће разматрати само предлоге који имају идентификатор већи од н .

Ако прималац већ није обећао (у Фази 1б) да ће разматрати само предлоге који имају идентификатор већи од н, требало би да региструје вредност в (управо примљене поруке о прихватању ) као прихваћену вредност (протокола) и пошаље Прихваћена порука предлагачу и сваком ученику. Ученици ће сазнати одређену вредност само након примања прихваћених порука од већине оних који их прихватају, што значи, не након што добију само прву поруку о прихватању.

У супротном, може да игнорише поруку или захтев Прихвати.

Имајте на уму да се консензус постиже када већина прималаца прихвати исти идентификациони број (уместо исте вредности). Пошто је сваки идентификатор јединствен за предлагача и само једна вредност може бити предложена по идентификатору, сви примаоци који прихватају исти идентификатор на тај начин прихватају исту вредност. Паксос протокол гарантује да је консензус трајан и да је изабрана вредност непроменљива.

Када рунде не успеју

Рунде не успевају када више предлагача пошаље конфликтне поруке припреме или када предлагач не прими кворум одговора ( обећање или прихваћено ). У овим случајевима, мора се започети други круг са већим бројем предлога.

Паксос се може користити за одабир вође Обратите пажњу да би предлагач у Паксосу могао да предложи „Ја сам вођа“ (или, на пример, „Предлагач К је лидер“). Због договора и гаранција ваљаности Паксоса, ако их кворум прихвати, онда је познато да је предлагач лидер у свим осталим чворовима. Ово задовољава потребе избора лидера I. Gupta, R. van Renesse, and K. P. Birman, 2000, A Probabilistically Correct Leader Election Protocol for Large Groups, Technical Report, Cornell University јер постоји један чвор који верује да је лидер и један чвор за који се зна да је лидер у сваком тренутку.

Графички приказ тока порука у основном Паксосу Следећи дијаграми представљају неколико случајева/ситуација примене основног Паксос протокола. Неки случајеви показују како се основни Паксос протокол носи са отказом одређених (редундантних) компоненти дистрибуираног система.

Имајте на уму да су вредности враћене у поруци обећања нулте вредности када се први пут направи предлог (пошто ниједан прималац није прихватио вредност раније у овој рунди).

Основни Паксос без грешака На дијаграму испод, постоји 1 клијент, 1 предлагач, 3 примаоца (тј. величина кворума је 3) и 2 ученика (представљено са 2 вертикалне линије). Овај дијаграм представља случај прве рунде, која је успешна. без|оквир

Случајеви грешке у основном Паксосу Најједноставнији случајеви грешке су неуспех примаоца (када довољан број примаоца остаје жив) и неуспех сувишног ученика. У овим случајевима, протокол не захтева никакав „опоравак“ (тј. и даље успева): нису потребне додатне рунде или поруке, као што је приказано испод (у следећа два дијаграма/случаја).

Основни Паксос када прималац закаже На следећем дијаграму, један од примаоца закаже, тако да величина кворума постаје 2. У овом случају, основни Паксос протокол и даље успева.Клијент Предлагач Прималац Ученик

X-------->| | | | | | Захтев | X--------->|->|->| | | Припрема(1) | | | | ! | | !! Неуспех !!