Пређи на садржај

Паксос (информатика)

С Википедије, слободне енциклопедије

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

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

Паксос протокол је први пут поднет 1989. године и назван је по измишљеном систему законодавног консензуса који се користи на острву Паксос у Грчкој, где је Лампорт написао да парламент мора да функционише „иако су законодавци непрестано лутали и излазили из парламентарне коморе“. [3] Касније је објављен као чланак у часопису 1998.

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

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

Историја[уреди | уреди извор]

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

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

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

Претпоставке[уреди | уреди извор]

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

Процесори[уреди | уреди извор]

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

Мрежа[уреди | уреди извор]

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

Број процесора[уреди | уреди извор]

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

Својства сигурности и животности[уреди | уреди извор]

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

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

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

Типичан развој[уреди | уреди извор]

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


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

Основни Паксос[уреди | уреди извор]

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

Фаза 1[уреди | уреди извор]

Фаза 1а: Припрема[уреди | уреди извор]

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

Фаза 1б: Обећање[уреди | уреди извор]

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

Фаза 2[уреди | уреди извор]

Фаза 2а: Прихватање[уреди | уреди извор]

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

Фаза 2б: Прихваћено[уреди | уреди извор]

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

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

Када рунде не успеју[уреди | уреди извор]

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

Паксос се може користити за одабир вође[уреди | уреди извор]

Обратите пажњу да би предлагач у Паксосу могао да предложи „Ја сам вођа“ (или, на пример, „Предлагач К је лидер“). [11] Због договора и гаранција ваљаности Паксоса, ако их кворум прихвати, онда је познато да је предлагач лидер у свим осталим чворовима. Ово задовољава потребе избора лидера [12] јер постоји један чвор који верује да је лидер и један чвор за који се зна да је лидер у сваком тренутку.

Графички приказ тока порука у основном Паксосу[уреди | уреди извор]

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

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

Основни Паксос без грешака[уреди | уреди извор]

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

Случајеви грешке у основном Паксосу[уреди | уреди извор]

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

Основни Паксос када прималац закаже[уреди | уреди извор]

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

Клијент  Предлагач     Прималац      Ученик
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Припрема(1)
   |         |          |  |  !       |  |  !! Неуспех !!
   |         |<---------X--X          |  |  Обећање(1,{Va, Vb, null})
   |         X--------->|->|          |  |  Прихвати!(1,V)
   |         |<---------X--X--------->|->|  Прихваћено(1,V)
   |<---------------------------------X--X  Одговор
   |         |          |  |          |  |


Основни Паксос када сувишни ученик закаже[уреди | уреди извор]

У следећем случају, један од (сувишних) ученика не успева, али основни Паксос протокол и даље успева. 

Клијент  Предлагач     Прималац      Ученик
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Припрема(1)
   |         |<---------X--X--X       |  |  Обећање(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Прихвати!(1,V)
   |         |<---------X--X--X------>|->|  Прихваћено(1,V)
   |         |          |  |  |       |  !  !! Неуспех !!
   |<---------------------------------X     Одговор
   |         |          |  |  |       |

Основни Паксос када предлагач не успе[уреди | уреди извор]

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



Клијент Предлагач      Прималац      Ученик
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Захтев
   |      X------------>|->|->|       |  |  Припрема(1)
   |      |<------------X--X--X       |  |  Обећање(1,{Va, Vb, Vc})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Лидер не успева током преноса !!
   |      X------------>|  |  |       |  |  Прихвати!(1,V)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! Нови лидер !!
   |         X--------->|->|->|       |  |  Припрема(2)
   |         |<---------X--X--X       |  |  Обећање(2,{V, null, null})
   |         X--------->|->|->|       |  |  Прихвати!(2,V)
   |         |<---------X--X--X------>|->|  Прихваћено(2,V)
   |<---------------------------------X--X  Одговор
   |         |          |  |  |       |  |

Основни Паксос када се сукоби више предлагача[уреди | уреди извор]

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

Клијент Предлагач   Прималац         Ученик
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Захтев
   |      X------------>|->|->|       |  |  Припрема(1)
   |      |<------------X--X--X       |  |  Обећање(1,{null,null,null})
   |      !             |  |  |       |  |  !! Лидер заказује
   |         |          |  |  |       |  |  !! Нови лидер (зна да је последњи број био 1)
   |         X--------->|->|->|       |  |  Припрема(2)
   |         |<---------X--X--X       |  |  Обећање(2,{null,null,null})
   |      |  |          |  |  |       |  |  !! Стари лидер се опоравља
   |      |  |          |  |  |       |  |  !! Стари лидер покушава са 2, одбијено
   |      X------------>|->|->|       |  |  Припрема(2)
   |      |<------------X--X--X       |  |  Одбијање(2)
   |      |  |          |  |  |       |  |  !! Стари лидер покушава са 3
   |      X------------>|->|->|       |  |  Припрема(3)
   |      |<------------X--X--X       |  |  Обећање(3,{null,null,null})
   |      |  |          |  |  |       |  |  !! Нови лидер предлаже, одбијено
   |      |  X--------->|->|->|       |  |  Прихбати!(2,Va)
   |      |  |<---------X--X--X       |  |  Одбијање(3)
   |      |  |          |  |  |       |  |  !! Нови лидер покушава са 4
   |      |  X--------->|->|->|       |  |  Припрема(4)
   |      |  |<---------X--X--X       |  |  Обећање(4,{null,null,null})
   |      |  |          |  |  |       |  |  !! Стари лидер предлаже, одбијено
   |      X------------>|->|->|       |  |  Прихвати!(3,Vb)
   |      |<------------X--X--X       |  |  Одбијено(4)
   |      |  |          |  |  |       |  |  ... и тако даље ...

Основни Паксос где прималац прихвата две различите вредности[уреди | уреди извор]

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

Предлагач   Прималац     Ученик
 |  |       |  |  |       |  |
 X--------->|->|->|       |  |  Припрема(1)
 |<---------X--X--X       |  |  Обећање(1,{null,null,null})
 x--------->|  |  |       |  |  Прихвати!(1,V1)
 |  |       X------------>|->|  Прихваћено(1,V1)
 !  |       |  |  |       |  |  !! Неуспех !!
    |       |  |  |       |  |
    X--------->|->|       |  |  Припрема(2)
    |<---------X--X       |  |  Обећање(2,{null,null})
    X------>|->|->|       |  |  Прихвати!(2,V2)
    |<------X--X--X------>|->|  Прихваћено(2,V2)
    |       |  |  |       |  |

Основни Паксос у ком вишеструка идентификација већине није довољна[уреди | уреди извор]

У следећем случају, један предлагач постиже прихватање вредности V1 једног примаоца пре него што закаже. Нови предлагач припрема примаоце који никада нису прихватили V1, дозвољавајући му да предложи V2. Овај предлагач може да натера једног примаоца да прихвати V2 пре него што не успе. Нови предлагач проналази већину која укључује примаоца који је прихватио V1 и мора га предложити. Предлагач успева да натера два примаоца да га прихвате пре него што закаже. У овом тренутку, три примаоца су прихватила V1, али не за исти идентификатор. Коначно, нови предлагач припрема већину која није видела највећи прихваћени идентификатор. Вредност повезана са највећим идентификатором у тој већини је V2, тако да га мора предложити. Овај Предлагач онда тера све примаоце да прихвате V2, постижући консензус.

  Предлагач         Прималац           Ученик
 |  |  |  |       |  |  |  |  |       |  |
 X--------------->|->|->|->|->|       |  |  Припрема(1)
 |<---------------X--X--X--X--X       |  |  Обећање(1,{null,null,null,null,null})
 x--------------->|  |  |  |  |       |  |  Прихвати!(1,V1)
 |  |  |  |       X------------------>|->|  Прихваћено(1,V1)
 !  |  |  |       |  |  |  |  |       |  |  !! Неуспех !!
    |  |  |       |  |  |  |  |       |  |
    X--------------->|->|->|->|       |  |  Припрема(2)
    |<---------------X--X--X--X       |  |  Обећање(2,{null,null,null,null})
    X--------------->|  |  |  |       |  |  Прихвати!(2,V2)
    |  |  |       |  X--------------->|->|  Прихваћено(2,V2)
    !  |  |       |  |  |  |  |       |  |  !! Неуспех !!
       |  |       |  |  |  |  |       |  | 
       X--------->|---->|->|->|       |  |  Припрема(3)
       |<---------X-----X--X--X       |  |  Обећање(3,{V1,null,null,null})
       X--------------->|->|  |       |  |  Прихвати!(3,V1)
       |  |       |  |  X--X--------->|->|  Прихваћено(3,V1)
       !  |       |  |  |  |  |       |  |  !! Неуспех !!
          |       |  |  |  |  |       |  |
          X------>|->|------->|       |  |  Припрема(4)
          |<------X--X--|--|--X       |  |  Обећање(4,{V1(1),V2(2),null})
          X------>|->|->|->|->|       |  |  Прихвати!(4,V2)
          |       X--X--X--X--X------>|->|  Прихваћено(4,V2)

Основни Паксос где нови предлагачи не могу да промене постојећи консензус[уреди | уреди извор]

У следећем случају, један предлагач постиже прихватање вредности V1 од два примаоца пре него што он закаже. Нови предлагач може започети још један круг, али сада је немогуће да тај предлагач припреми већину која не укључује најмање једног примаоца који је прихватио V1. Као такав, иако предлагач не види постојећи консензус, једина опција предлагача је да предложи већ договорену вредност. Нови предлагачи могу стално да повећавају идентификатор да би поново покренули процес, али консензус се никада не може променити.

Предлагач    Прималац     Ученик
 |  |       |  |  |       |  |
 X--------->|->|->|       |  |  Припрема(1)
 |<---------X--X--X       |  |  Обећање(1,{null,null,null})
 x--------->|->|  |       |  |  Прихвати!(1,V1)
 |  |       X--X--------->|->|  Прихваћено(1,V1)
 !  |       |  |  |       |  |  !! Неуспех !!
    |       |  |  |       |  |
    X--------->|->|       |  |  Припрема(2)
    |<---------X--X       |  |  Обећање(2,{V1,null})
    X------>|->|->|       |  |  Прихвати!(2,V1)
    |<------X--X--X------>|->|  Прихваћено(2,V1)
    |       |  |  |       |  |

Вишеструки Паксос[уреди | уреди извор]

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

Ако је вођа релативно стабилан, фаза 1 постаје непотребна. Стога, могуће је прескочити фазу 1 за будуће случајеве протокола са истим вођом.

Графички приказ тока порука у Вишеструком Паксосу[уреди | уреди извор]

Вишеструки Паксос без кварова[уреди | уреди извор]

У следећем дијаграму је приказана само једна инстанца (или „извршење“) основног Паксос протокола, са почетним вођом (предлагачем). Вишеструки Паксос састоји од неколико инстанци основног Паксос протокола.

Клијент  Предлагач   Прималац        Ученик
   |         |          |  |  |       |  | --- Први захтев ---
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Припрема(N)
   |         |<---------X--X--X       |  |  Обећање(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Прихвати!(N,I,V)
   |         |<---------X--X--X------>|->|  Примљено(N,I,V)
   |<---------------------------------X--X  Одговор
   |         |          |  |  |       |  |

Мулти-Пакос када се фаза 1 може прескочити[уреди | уреди извор]

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

Клијент Предлагач    Прималац     Ученик
   |         |          |  |  |       |  |  --- Престојећи захтеви ---
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Прихвати!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Прихваћено(N,I+1,W)
   |<---------------------------------X--X  Одговор
   |         |          |  |  |       |  |

Вишеструки Паксос када су улоге скупљене[уреди | уреди извор]

Уобичајена примена Вишеструког Пакоса се састоји у уклањању улоге предлагача, примаоца и ученика на „сервере“. Дакле, на крају постоје само „Клијенти“ и „Сервери“.

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

Клијент      Сервери
   |         |  |  | --- Први захтев ---
   X-------->|  |  |  Захтев
   |         X->|->|  Припремни(N)
   |         |<-X--X  Обећање(N, I, {Va, Vb})
   |         X->|->|  Прихвати!(N, I, Vn)
   |         X<>X<>X  Прихваћено(N, I)
   |<--------X  |  |  Одговор
   |         |  |  |

Вишеструки Паксос када су улоге срушене и лидер је стабилан[уреди | уреди извор]

У следећим инстанцама основног Паксос протокола, са истим вођом као у претходним инстанцама основног Пакос протокола, фаза 1 се може прескочити.

Клијент      Сервери
   X-------->|  |  |  Захтев
   |         X->|->|  Прихвати!(N,I+1,W)
   |         X<>X<>X  Прихваћено(N,I+1)
   |<--------X  |  |  Одговор
   |         |  |  |

Оптимизације[уреди | уреди извор]

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

„Можемо да сачувамо поруке по цену додатног кашњења поруке тако што имамо једног истакнутог ученика који обавештава друге ученике када сазна да је вредност изабрана. Примаоци тада шаљу прихваћене поруке само истакнутом ученику. У већини апликација, улоге лидера и истакнутог ученика обавља исти процесор."
„Лидер може послати своју Припреми и прихвати! поруку само кворуму прималаца. Све док сви примаоци у том кворуму раде и могу да комуницирају са вођом и ученицима, нема потребе да они који прихватају који нису у кворуму било шта раде."
„Примаоцима није важно која ће вредност бити изабрана. Они једноставно одговарају на Припреми и прихвати! поруке како би се осигурало да се, упркос неуспесима, може изабрати само једна вредност. Међутим, ако прималац сазна која је вредност изабрана, може да сачува вредност у стабилном складишту и да избрише све друге информације које је тамо сачувао. Ако прималац касније добије Припреми или Прихвати! поруку, уместо да изврши своју акцију фаза1б или фаза2б, може једноставно обавестити вођу о изабраној вредности." [13]
„Уместо слања вредности в, лидер може да пошаље хеш од в неким примаоцима у својим порукама Прихвати!. Ученик ће научити да је в изабран ако прими прихваћене поруке или за в или свој хеш од кворума прихватача, и најмање једна од тих порука садржи в, а не свој хеш. Међутим, лидер би могао да прими поруке обећања које му говоре хеш вредности в коју мора да користи у својој акцији Фазе 2а, а да му не каже стварну вредност в. Ако се то догоди, вођа не може да изврши своју акцију Фазе 2а док не комуницира са неким процесом који зна в."
„Предлагач може да пошаље свој предлог само лидеру, а не свим координаторима. Међутим, ово захтева да се резултат алгоритма за избор лидера емитује предлагачима, што би могло бити скупо. Дакле, можда би било боље да предлагач пошаље свој предлог свим координаторима. (У том случају само координатори сами треба да знају ко је вођа.)[14]
„Уместо да сваки прималац шаље прихваћене поруке сваком ученику, они који прихватају могу да пошаљу своје прихваћене поруке вођи, а он може да обавести ученике када је вредност изабрана. Међутим, ово додаје додатно кашњење поруке.
„Коначно, приметите да је фаза 1 непотребна за прву рунду. Вођа прве рунде може започети рунду слањем поруке Прихвати! са било којом предложеном вредношћу.“

Јефтини Паксос[уреди | уреди извор]

Јефтини Пакос проширује Стандардни Паксос тако да толерише Ф кварова са Ф+1 главним процесорима и Ф помоћним процесорима динамичким реконфигурисањем након сваког квара.

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

"Са само два процесора п и к, један процесор не може да разликује квар другог процесора од отказа комуникационог медијума. Потребан је трећи процесор. Међутим, тај трећи процесор не мора да учествује у избору редоследа команди. Мора да предузме акцију само у случају да п или к не успе, након чега ништа не ради док п или к настављају да сами управљају системом. Трећи процесор може бити мали/спор/јефтин или процесор који је првенствено посвећен другим задацима. ."[15]

Ток порука: Јефтини Вишеструки Паксос[уреди | уреди извор]

Пример који укључује три главна примаоца, једног помоћног примаоца и величину кворума од три, који показује отказ једног главног процесора и накнадну реконфигурацију: 

             {  Примаоци }
Предлагач     Main       Aux    Ученик
|            |  |  |     |       |  -- Фаза2 --
X----------->|->|->|     |       |  Прихвати!(N,I,V)
|            |  |  !     |       |  --- Неуспех! ---
|<-----------X--X--------------->|  Прихваћено(N,I,V)
|            |  |        |       |  -- Неуспех детектован (само 2 су прихваћена) --
X----------->|->|------->|       |  Прихвати!(N,I,V)  (ретрансмитуј, include Aux)
|<-----------X--X--------X------>|  Прихваћено(N,I,V)
|            |  |        |       |  -- Реконфигуриши : Кворум = 2 --
X----------->|->|        |       |  Прихвати!(N,I+1,W) (Aux не учествује)
|<-----------X--X--------------->|  Прихваћено(N,I+1,W)
|            |  |        |       |

Брзи Паксос[уреди | уреди извор]

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

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

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

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

Ток порука: Брз Пакос, неконфликтан[уреди | уреди извор]

Клијент    Лидер         Прималац      Ученик
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Било који(N,I,Опоравак)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Прихвати!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Прихваћено(N,I,W)
   |<------------------------------------X--X  Одговор(W)
   |         |          |  |  |  |       |  |

Ток порука: Брзи Паксоси, конфликтни предлози[уреди | уреди извор]

Сукобни предлози са координисаним опоравком. Напомена: протокол не наводи како се поступа са одбаченим захтевом клијента.

Клијент  Лидер      Прималац       Ученик
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Конкурентни конфликтне понуде
 |  |      |        |  |  |  |      |  |  !!   добијене другачијим редоследом 
 |  |      |        |  |  |  |      |  |  !!   од стране прималаца
 |  X--------------?|-?|-?|-?|      |  |  Прихвати!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Прихвати!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Примоаци се не слажу око вредности
 |  |      |<-------X--X->|->|----->|->|  Прихваћено(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Прихваћено(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Детектована колизија и опоравак
 |  |      X------->|->|->|->|      |  |  Прихвати!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Прихваћено(N+1,I,W)
 |<---------------------------------X--X  Одговор(W)
 |  |      |        |  |  |  |      |  |

Сукобни предлози са некоординираним опоравком.

Клијент   Лидер     Прималац       Ученик



|  |      |        |  |  |  |      |  |
|  |      X------->|->|->|->|      |  |  Било који(N,I,Опоравак)
|  |      |        |  |  |  |      |  |
|  |      |        |  |  |  |      |  |  !! Конкурентне конфликтне понуде
|  |      |        |  |  |  |      |  |  !!   добијене другачијим редоследом
|  |      |        |  |  |  |      |  |  !!   од стране Прималаца
|  X--------------?|-?|-?|-?|      |  |  Прихвати!(N,I,V)
X-----------------?|-?|-?|-?|      |  |  Прихвати!(N,I,W)
|  |      |        |  |  |  |      |  |
|  |      |        |  |  |  |      |  |  !! Примаоци се не слажу око вредности
|  |      |<-------X--X->|->|----->|->|  Прихваћено(N,I,V)
|  |      |<-------|<-|<-X--X----->|->|  Прихваћено(N,I,W)
|  |      |        |  |  |  |      |  |
|  |      |        |  |  |  |      |  |  !! Детектована колизија и опоравак
|  |      |<-------X--X--X--X----->|->|  Прихваћено(N+1,I,W)
|<---------------------------------X--X  Одговор(W)
|  |      |        |  |  |  |      |  |

Ток порука: Брз Пакос са некоординисаним опоравком, срушене улоге[уреди | уреди извор]

Клијент        Сервери
 |  |         |  |  |  |
 |  |         X->|->|->|  Било који(N,I,Опоравак)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Конкурентне конфликтне понуде
 |  |         |  |  |  |  !!   добијене различитим редоследом
 |  |         |  |  |  |  !!   од стране Сервера
 |  X--------?|-?|-?|-?|  Прихвати!(N,I,V)
 X-----------?|-?|-?|-?|  Прихвати!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Сервери се не слажу око вредности
 |  |         X<>X->|->|  Прихваћено(N,I,V)
 |  |         |<-|<-X<>X  Прихваћено(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Детектована колизија и опоравак
 |  |         X<>X<>X<>X  Прихваћено(N+1,I,W)
 |<-----------X--X--X--X  Одговор(W)
 |  |         |  |  |  |

Генерализовани Паксос[уреди | уреди извор]

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

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

Пример[уреди | уреди извор]

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

Табела комутативности
Прочитај(А) Напиши(А) Прочитај(Б) Напиши (Б)
Прочитај(А) Не
Напиши(А) Не Не
Прочитај (Б) Не
напиши (Б) Не Не

Где у овој табели означава операције које нису комутативне.

Могући редослед операција :|

1:Прочитај(А),2:Прочитај(Б),3:Напиши(Б),4:Прочитај(Б)5:Прочитај(А),6:Напиши(А)

Пошто 5:Прочитај(А) мења и са 3:Напиши(Б) и 4:Read(B), једна могућа пермутација еквивалентна претходном редоследу је следећа:

1:Прочитај(А),2:Прочитај(Б),5:Прочитај(А)3:Напиши(Б),4:Прочитај(Б),6:Напиши(А)

У пракси, премештање се дешава само када се операције предлажу истовремено.

Ток поруке: Генерализовани Паксос (пример)[уреди | уреди извор]

Клијент    Лидер     Примлац       Ученик
 |  |         |      |  |  |         |  |  !! Нови лидер започиње рунду
 |  |         X----->|->|->|         |  |  Припрема(N)
 |  |         |<-----X- X- X         |  |  Обећање(N,null)
 |  |         X----->|->|->|         |  |  Фаза2(N,null)
 |  |         |      |  |  |         |  | 
 |  |         |      |  |  |         |  |  !! Конкурентни предлози
 |  X------- ?|-----?|-?|-?|         |  |  Предложи(Прочитај A)
 X-----------?|-----?|-?|-?|         |  |  Предложи(Прочитај B)
 |  |         X------X-------------->|->|  Прихваћено(N,<Прочитај A,Прочитај B>)
 |  |         |<--------X--X-------->|->|  Прихваћено(N,<Прочитај B,Прочитај A>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Нема конфликта, оба прихваћена
 |  |         |      |  |  |         |  |  Стабилно = <Прочитај A, Прочитај B>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! КОнкурентни предлози
 X-----------?|-----?|-?|-?|         |  |  Предложи(<Напиши B,Напиши A>)
 |  X--------?|-----?|-?|-?|         |  |  Предложи(Прочитај B)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Прихваћено(N,<Напиши B,Прочитај A> . <Прочитај B>)
 |  |         |<--------X--X-------->|->|  Прихваћено(N,<Прочитај B> . <Напиши B,Прочитај A>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Конфликт детектован, лидер бира редослед
 |  |         |      |  |  |         |  |  
 |  |         |      |  |  |         |  |  V = <Прочитај A, Напиши B, Прочитај B>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Фаза2(N+1,V)
 |  |         |<-----X- X- X-------->|->|  Прихваћено(N+1,V)
 |  |         |      |  |  |         |  |  Стабилно = <Прочитај A, Прочитај B> .
 |  |         |      |  |  |         |  |           <Прочитај A, Напиши B, Прочитај B>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  | !! Више конфликтних предлога
 X-----------?|-----?|-?|-?|         |  |  Предложи(Напиши A)
 |  X--------?|-----?|-?|-?|         |  |  Предложи(Прочитај A)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Прихваћено(N+1,<Напиши A> . <Прочитај A>)
 |  |         |<--------X- X-------->|->|  Прихваћено(N+1,<Прочитај A> . <Напиши A>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Лидер бира распоред:
 |  |         |      |  |  |         |  |  W = <Напиши A, Прочитај A>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Фаза2(N+2,W)
 |  |         |<-----X- X- X-------->|->|  Прихваћено(N+2,W)
 |  |         |      |  |  |         |  |  Стабилно = <Прочитај A, Прочитај B> .
 |  |         |      |  |  |         |  |           <Прочитај A, Напиши B, Прочитај B> .
 |  |         |      |  |  |         |  |           <Напиши A, Прочитај A>
 |  |         |      |  |  |         |  |

Перформансе[уреди | уреди извор]

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

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

  • Прво, ако је координатор део сваког кворума прималаца (круг Н се назива центрираним), онда да би се опоравио у кругу Н+1 од колизије у кругу Н, координатор прескаче фазу 1 и у фази 2 предлаже секвенцу коју је последњи прихватио током рунде Н. Ово смањује трошкове опоравка на једно повратно путовање.
  • Друго, ако оба круга Н и Н+1 користе јединствен и идентичан центрирани кворум, када прималац открије колизију у кругу Н, он спонтано предлаже у кругу Н+1 секвенцу са суфиксом оба (и) секвенцу прихваћену у кругу Н од стране координатора и највећи неконфликтни префикс који је прихватио у рунди Н. На пример, ако су координатор и прималац прихватили респективно у рунди Н <НапишиБ, ПрочитајБ> и <ПрочитајБ, ПрочитајА>, прималац ће спонтано прихватити < НапишиБ, ПрочитајБ, ПрочитајА> у рунди Н+1. Са овом варијацијом, цена опоравка је кашњење једне поруке, што је очигледно оптимално. Приметите овде да употреба јединственог кворума на рунди не штети животности. Ово долази из чињенице да сваки процес у овом кворуму је кворум за читање за фазу припреме наредних рунди. [16]

Византијски Паксос[уреди | уреди извор]

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

Византијски Паксос [17] који су представили Кастро и Лисков додаје додатну поруку (Потврду) која служи за дистрибуцију знања и проверу акција других процесора:

Ток порука: Византијски Мулти-Паксос, стабилно стање[уреди | уреди извор]



Клијент   Предагач     Прималац    Ученик
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Прихвати!(N,I,V)
   |         |          X<>X<>X       |  |  Верификуј(N,I,V) - BROADCAST
   |         |<---------X--X--X------>|->|  Прихваћено(N,V)
   |<---------------------------------X--X  Одговор(V)
   |         |          |  |  |       |  |

Брзи византијски Паксос [18] који су увели Мартин и Алвиси уклања ово додатно кашњење, пошто клијент шаље команде директно примаоцима.

Имајте на уму да се прихваћена порука у Брзом Византијском Паксосу шаље свим примаоцима и свим ученицима, док Брзи Пакос шаље прихваћене поруке само ученицима.

Ток порука: Брзи византијски Вишеструки Паксос, стабилно стање[уреди | уреди извор]




Клијент   Прималац    Ученик
   |      |  |  |       |  |
   X----->|->|->|       |  |  Пријвати!(N,I,V)
   |      X<>X<>X------>|->|  Прихваћено(N,I,V) - BROADCAST
   |<-------------------X--X  Одговор(V)
   |      |  |  |       |  |


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

Ток порука: Брзи византијски вишеструки Паксос, неуспех[уреди | уреди извор]

Клијент   Прималац    Ученик
   |      |  |  !       |  |  !! Један Прималац греши
   X----->|->|->!       |  |  Прихвати!(N,I,V)
   |      X<>X<>X------>|->|  Прихваћено(N,I,{V,W}) - BROADCAST
   |      |  |  !       |  |  !! Ученик добија 2 команде
   |      |  |  !       |  |  !! Правилан Прималац примећује грешку
   |      X<>X<>X------>|->|  Пеихваћено(N,I,V) - BROADCAST
   |<-------------------X--X  Одоговор(V)
   |      |  |  !       |  |

Прилагођавање Паксоса за РДМА мреже[уреди | уреди извор]

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

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

Референце[уреди | уреди извор]

  1. ^ Lamport, Leslie (1978). „Time, clocks, and the ordering of events in a distributed system”. Communications of the ACM. 21 (7): 558—565. S2CID 215822405. doi:10.1145/359545.359563. 
  2. ^ Schneider, Fred B. (1990). „Implementing fault-tolerant services using the state machine approach: A tutorial”. ACM Computing Surveys. 22 (4): 299—319. CiteSeerX 10.1.1.69.1536 Слободан приступ. S2CID 678818. doi:10.1145/98163.98167. 
  3. ^ Leslie Lamport's history of the paper
  4. ^ Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (1988). „Consensus in the presence of partial synchrony”. Journal of the ACM. 35 (2): 288—323. CiteSeerX 10.1.1.13.3423 Слободан приступ. doi:10.1145/42282.42283. 
  5. ^ Oki, Brian M.; Liskov, Barbara H. (1988). „Viewstamped replication: A general primary copy”. Proceedings of the seventh annual ACM Symposium on Principles of distributed computing - PODC '88. стр. 8—17. ISBN 0-89791-277-2. doi:10.1145/62546.62549. 
  6. ^ Birman, Kenneth P.; Joseph, Thomas A. (1987). „Reliable communication in the presence of failures”. ACM Transactions on Computer Systems. 5: 47—76. S2CID 11224827. doi:10.1145/7351.7478. hdl:1813/6534. 
  7. ^ Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (2010). „Reconfiguring a state machine”. ACM Sigact News. 41: 63—73. CiteSeerX 10.1.1.212.2168 Слободан приступ. S2CID 15189602. doi:10.1145/1753171.1753191. 
  8. ^ Jha, Sagar; Behrens, Jonathan; Gkountouvas, Theo; Milano, Mae; Song, Weijia; Tremel, Edward; Renesse, Robbert Van; Zink, Sydney; Birman, Kenneth P. (2018). „Derecho: Fast State Machine Replication for Cloud Services”. ACM Transactions on Computer Systems. 36 (2): 1—49. S2CID 218482757. doi:10.1145/3302258. 
  9. ^ Van Renesse, Robbert; Altinbuken, Deniz (2015-02-17). „Paxos Made Moderately Complex”. ACM Computing Surveys. 47 (3): 42:1—42:36. ISSN 0360-0300. doi:10.1145/2673577. 
  10. ^ Chandra, Tushar D.; Griesemer, Robert; Redstone, Joshua (2007). „Paxos made live: An engineering perspective”. Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. стр. 398—407. ISBN 978-1-59593-616-5. S2CID 207164635. doi:10.1145/1281100.1281103. 
  11. ^ „Leader Election, Why Should I Care?”. Elastic Blog. 13. 9. 2013. Приступљено 27. 2. 2021. 
  12. ^ I. Gupta, R. van Renesse, and K. P. Birman, 2000, A Probabilistically Correct Leader Election Protocol for Large Groups, Technical Report, Cornell University
  13. ^ Lamport, Leslie; Massa, Mike (2004). "Cheap Paxos". Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004).
  14. ^ Lamport, Leslie (2005). "Fast Paxos".
  15. ^ Lamport, Leslie; Massa, Mike (2004). "Cheap Paxos". Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004).
  16. ^ Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (2009). „Vertical paxos and primary-backup replication”. Proceedings of the 28th ACM symposium on Principles of distributed computing. PODC '09. New York, NY, USA: ACM. стр. 312—313. CiteSeerX 10.1.1.150.1791 Слободан приступ. ISBN 9781605583969. doi:10.1145/1582716.1582783. 
  17. ^ Castro, Miguel; Liskov, Barbara (фебруар 1999). „Practical Byzantine Fault Tolerance” (PDF). Proceedings of the Third Symposium on Operating Systems Design and Implementation: 173—186. Приступљено 5. 3. 2018. 
  18. ^ Martin, Jean-Philippe; Alvisi, Lorenzo (јул 2006). „Fast Byzantine Consensus” (PDF). IEEE Transactions on Dependable and Secure Computing. 3 (3): 202—215. doi:10.1109/TDSC.2006.35. Приступљено 5. 3. 2018. 
Преузето из „https://sr.wikipedia.org/w/index.php?title=Паксос_(информатика)&oldid=27865047”