Алгоритм Паксос

• Процесори працюють з довільною швидкістю.
• У процесорів можуть виникнути збої.
• Процесори можуть повторно приєднатися до протоколу після збоїв.
• Процесори не змовляються, не брешуть чи іншим чином намагаються підірвати протокол, тобто, візантійські невдачі не відбуваються.

• Процесори можуть надсилати повідомлення на будь-який інший процесор.
• Повідомлення надсилаються асинхронно та можуть доставляти довільну кількість часу.
• Повідомлення можуть бути втрачені, переупорядковані або продубльовані.
• Повідомлення доставляються без корупції, тобто, візантійські невдачі не відбуваються.

Загалом алгоритм узгодження може досягти прогресу, за умови використання ${\displaystyle n=2F+1}$ процесорів, незважаючи на одночасний вихід з ладу будь-якого ${\displaystyle F}$ процесора: іншими словами, кількість справних процесів повинна бути строго більшою, ніж кількість несправних процесів. Однак, використовуючи реконфігурацію, може бути використаний протокол, який переживає будь-яку кількість загальних збоїв до тих пір, поки не перевищить значення F одночасно.

Кворуми висловлюють властивості безпеки алгоритму, забезпечуючи збереження інформації про результати.

Кворуми визначаються як підмножини безлічі Приймачів таким чином, щоб будь-які дві підмножини (тобто будь-які два кворуму) мали принаймні один спільний елемент. Як правило, кворум є будь-якою більшістю, де беруть участь Приймачі. Наприклад, розглянемо безліч Приймачів {А, B, С, D}, кворум більшості для якого будуть три будь-яких Приймача: {А, B, С}, {А, С, D}, {А, В, D} або {B, З, D}. У більш загальному плані Приймачам і кворуму можуть бути присвоєні довільні позитивні ваги, які визначають як будь-яка підмножина Приймачів з сумарною вагою перевищує половину загальної ваги усіх Приймачів.

Кожна спроба визначає значення v, яке виконується із пропозиціями, які можуть або не можуть бути прийняті Приймальником. Кожна пропозиція має унікальну нумерацію для даного Заявника. Значення, відповідне нумерованій пропозиції, може бути обчислено як частина запуску протоколу Paxos, але це не обов'язково.

Заявник створює повідомлення, яке ми називаємо «Підготовка» та ототожнює з числом n . Зауважте, що n — це не значення, а лише число, яке однозначно ідентифікує це початкове повідомлення, запропоноване заявником (яке повинно бути надіслане приймачем). Число n повинно бути більше, ніж будь-яке число, використовуване в будь-якому з попередніх фазах Підготовки повідомлення цього Заявника. Потім він надсилає повідомлення Підготовка, що містить n, до кворуму приймачів . Зауважте, що повідомлення цієї фази містить лише число n (тобто воно не повинно містити, наприклад, запропоноване значення, яке часто позначається v). Заявник вирішує, хто в кворумі . Заявник не повинен ініціювати Paxos, якщо він не може спілкуватися хоча б з кворумом приймачів.

Будь-який з Приймачів чекає повідомлення з фази 1а від будь-якого із Заявника . Якщо Приймач отримує повідомлення, Приймач повинен переглянути ідентифікаційний номер n щойно отриманого повідомлення. Далі може бути такі випадки.

Число n вище, ніж будь-який попередній номер пропозиції, отриманий Приймачем від будь-якого із Заявників. Тоді Приймач повинен повернути повідомлення, яке ми називаємо «Обіцянкою» та ігнорувати всі майбутні пропозиції, що мають число менше ніж n . Якщо Приймач прийняв пропозицію в якийсь момент минулого, він повинен включити попередній номер пропозиції, скажімо m, і відповідне прийняте значення, скажімо, w, у своїй відповіді на адресу Заявника.

В іншому випадку (якщо n є меншим або рівним будь-якому попередньому номеру пропозиції, отриманому від будь-якого Заявника Приймачу), Приймач може ігнорувати отриману пропозицію.

Якщо Заявник отримує більшість «обіцянь» від кворуму Приймачів, йому необхідно встановити значення v своїй пропозиції. Якщо будь-який Приймач раніше прийняв будь-яку пропозицію, то вони надішлють свої значення Заявнику, який тепер повинен встановити значення своєї пропозиції, v, на значення, пов'язане з найвищим числом пропозицій (назвемо його z), про яке повідомили Приймача. Якщо жоден з Приймачів не прийняв пропозицію до цього моменту, то Замовник може вибрати значення, яке він спочатку хотів запропонувати, скажімо x[9] .

Заявник надсилає повідомлення Accept ((n, v)) до кворуму приймачів із вибраним значенням для своєї пропозиції, v та номером пропозиції n. Отже, повідомлення Accept є або (n, v = z), або, якщо жоден з приймачів раніше не прийняв значення, (n, v = x) .

Якщо Приймач отримує повідомлення про прийняття (n, v) від Заявника, він повинен прийняти його, тільки якщо він не обіцяв (у фазі 1b протоколу Paxos) розглянути лише пропозиції, що мають ідентифікатор, більший ніж n .

Якщо Акцептор вже не пообіцяв (у Фазі 1b) розглядати лише пропозиції, що мають ідентифікатор, більший за n, він повинен зареєструвати значення v (щойно отриманого повідомлення Accept) як прийняте значення (протоколу) та надіслати Прийняте повідомлення Заявнику та кожному Учаснику (яким зазвичай можуть бути самі Заявники).

Крім того, він може ігнорувати повідомлення Прийняття або запит.

Треба відмітити, що Приймач може брати кілька пропозицій. Це може статися, якщо інший Заявник, не знаючи про нове значення, розпочне новий раунд з більш високим ідентифікаційним номером n . У цьому випадку Приймач може пообіцяти і пізніше прийняти нове запропоноване значення, навіть якщо він прийняв інше раніше. Ці пропозиції можуть мати навіть різні значення за наявності певних невдач. Однак протокол Паксос гарантує, що Приймачі в кінцевому рахунку домовляться.

Раунди не вдається, коли кілька заявників надсилають суперечливі підготувальні повідомлення або коли Заявник не отримує кворум відповідей (Обіцяння або Прийняття). У цих випадках слід розпочати ще один раунд із більшим числом пропозицій.

Зауважте, що Приймачі приймають запит та підтверджують лідерство Заявника. Отже, Паксос можна використовувати для вибору лідера в кластері вузлів.

Наступні діаграми представляють випадки застосування протоколу базового Паксос. Деякі випадки показують, як протокол базового Паксос справляється з відмовою надлишкових компонентів розподіленої системи.

Зауважте, що значення, повернені у повідомленні Обіцяння, «стають нульовими» при першому внесенні пропозиції (оскільки жоден Приймач не прийняв значення до цього раунду).

На наведеній нижче схемі є 1 Клієнт, 1 Заявник 3 Приймача (тобто розмір Кворуму — 3) та 2 Учні (представлені двома вертикальними лініями). Ця діаграма представляє випадок першого раунду, який є успішним (тобто жоден процес у мережі не завершується)

/

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Тут V — останній із (Va, Vb, Vc).

Найпростіші випадки помилок — це вихід з ладу Приймача (коли кворум приймачів залишається живим) та відмова зайвого Учня. У цих випадках протокол не треба «відновлювати»: не потрібні додаткові раунди чи повідомлення, які показані у двох наступних діаграмах / випадках.

На наступній схемі один з Приймачів відмовляється, тому розмір Кворуму стає 2. У цьому випадку протокол Базовий Паксос все ще є успішним.

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |          |  |  !       |  |  !! FAIL !!
   |         |<---------X--X          |  |  Promise(1,{Va, Vb, null})
   |         X--------->|->|          |  |  Accept!(1,V)
   |         |<---------X--X--------->|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |          |  |

У наступному випадку один із учнів виходить з ладу, але протокол Базовий Паксос все-таки є успішним.

Client Proposer         Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |         |          |  |  |       |  !  !! FAIL !!
   |<---------------------------------X     Response
   |         |          |  |  |       |

У цьому випадку Заявник виходить з ладу після заявлених значень, але до досягнення згоди. Зокрема, воно не в середині повідомлення Accept, тому значення має лише один Приймач кворуму. Тим часом обирається новий Ведучий. Зверніть увагу, що в цьому випадку є два раунди (раунди проходять вертикально, зверху вниз).

Client  Proposer        Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{Va, Vb, Vc})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Leader fails during broadcast !!
   |      X------------>|  |  |       |  |  Accept!(1,V)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! NEW LEADER !!
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{V, null, null})
   |         X--------->|->|->|       |  |  Accept!(2,V)
   |         |<---------X--X--X------>|->|  Accepted(2,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Найскладніший випадок, коли кілька Заявників вважають себе лідерами. Наприклад, поточний лідер може на деякий час вийти з ладу та пізніше відновитись, але інші Заявники вже обрали нового лідера. При цьому прийнятий лідер цього ще не дізнався і намагається розпочати новий раунд у конфлікті з нинішнім лідером. На діаграмі нижче показано 4 невдалих раунди, але їх може бути більше (як це запропоновано внизу діаграми).

Client   Leader         Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{null,null,null})
   |      !             |  |  |       |  |  !! LEADER FAILS
   |         |          |  |  |       |  |  !! NEW LEADER (knows last number was 1)
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{null,null,null})
   |      |  |          |  |  |       |  |  !! OLD LEADER recovers
   |      |  |          |  |  |       |  |  !! OLD LEADER tries 2, denied
   |      X------------>|->|->|       |  |  Prepare(2)
   |      |<------------X--X--X       |  |  Nack(2)
   |      |  |          |  |  |       |  |  !! OLD LEADER tries 3
   |      X------------>|->|->|       |  |  Prepare(3)
   |      |<------------X--X--X       |  |  Promise(3,{null,null,null})
   |      |  |          |  |  |       |  |  !! NEW LEADER proposes, denied
   |      |  X--------->|->|->|       |  |  Accept!(2,Va)
   |      |  |<---------X--X--X       |  |  Nack(3)
   |      |  |          |  |  |       |  |  !! NEW LEADER tries 4
   |      |  X--------->|->|->|       |  |  Prepare(4)
   |      |  |<---------X--X--X       |  |  Promise(4,{null,null,null})
   |      |  |          |  |  |       |  |  !! OLD LEADER proposes, denied
   |      X------------>|->|->|       |  |  Accept!(3,Vb)
   |      |<------------X--X--X       |  |  Nack(4)
   |      |  |          |  |  |       |  |  ... and so on ...

На наступній діаграмі показаний лише один екземпляр базового протоколу Паксос з початковим лідером. Зауважте, що Мульти-Паксос складається з декількох примірників базового протоколу Паксос.

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

де V = останній з (Va, Vb, Vc).

У цьому випадку екземпляри послідовності базового протоколу Паксос використовують того ж самого лідера, тому фаза 1, яка складається з більш коротших фаз Підготувати та Обіцяти, пропускається. Зауважте, що лідер повинен бути стабільним, тобто не повинен виходити з ладу або змінюватися.

Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Поширене розгортання Мульти-Паксос полягає у згортанні ролі Заявників, Приймачів та Учнів на «Сервери». Отже, зрештою, є лише «Клієнти» та «Сервери».

Наведена нижче схема представляє перший "екземпляр" базового протоколу Паксос, коли ролі Заявника, Приймача та Учня згортаються в роль "Сервер".

Client      Servers
   |         |  |  | --- First Request ---
   X-------->|  |  |  Request
   |         X->|->|  Prepare(N)
   |         |<-X--X  Promise(N, I, {Va, Vb})
   |         X->|->|  Accept!(N, I, Vn)
   |         X<>X<>X  Accepted(N, I)
   |<--------X  |  |  Response
   |         |  |  |

У наступних випадках базового протоколу Паксос з тим самим лідером, що і в попередніх екземплярах базового протоколу Паксос, фаза 1 може бути пропущена.

Client      Servers
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N,I+1,W)
   |         X<>X<>X  Accepted(N,I+1)
   |<--------X  |  |  Response
   |         |  |  |

Приклад, що включає три основних приймача, один допоміжний приймач і розмір кворуму в три, показує вихід з ладу одного основного процесора та наступну конфігурацію:

{  Acceptors   }
Proposer     Main       Aux    Learner
|            |  |  |     |       |  -- Phase 2 --
X----------->|->|->|     |       |  Accept!(N,I,V)
|            |  |  !     |       |  --- FAIL! ---
|<-----------X--X--------------->|  Accepted(N,I,V)
|            |  |        |       |  -- Failure detected (only 2 accepted) --
X----------->|->|------->|       |  Accept!(N,I,V)  (re-transmit, include Aux)
|<-----------X--X--------X------>|  Accepted(N,I,V)
|            |  |        |       |  -- Reconfigure : Quorum = 2 --
X----------->|->|        |       |  Accept!(N,I+1,W) (Aux not participating)
|<-----------X--X--------------->|  Accepted(N,I+1,W)
|            |  |        |       |

Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |

Конфлікт пропозицій з координованим відновленням. Примітка: протокол не вказує, як обробляти скинутий запит клієнта.

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      X------->|->|->|->|      |  |  Accept!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

Суперечність пропозицій з неузгодженим відновленням.

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X<>X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X<>X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |  |         X<>X<>X<>X  Accepted(N+1,I,W)
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |

Client      Leader  Acceptor       Learner
 |  |         |      |  |  |         |  |  !! New Leader Begins Round
 |  |         X----->|->|->|         |  |  Prepare(N)
 |  |         |<-----X- X- X         |  |  Promise(N,null)
 |  |         X----->|->|->|         |  |  Phase2Start(N,null)
 |  |         |      |  |  |         |  | 
 |  |         |      |  |  |         |  |  !! Concurrent commuting proposals
 |  X------- ?|-----?|-?|-?|         |  |  Propose(ReadA)
 X-----------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         X------X-------------->|->|  Accepted(N,<ReadA,ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! No Conflict, both accepted
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Concurrent conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(<WriteB,ReadA>)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N,<WriteB,ReadA> . <ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB> . <WriteB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Conflict detected, leader chooses
 |  |         |      |  |  |         |  |  commutative order:
 |  |         |      |  |  |         |  |  V = <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+1,V)
 |  |         |<-----X- X- X-------->|->|  Accepted(N+1,V)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  | !! More conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(WriteA)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadA)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N+1,<WriteA> . <ReadA>)
 |  |         |<--------X- X-------->|->|  Accepted(N+1,<ReadA> . <WriteA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Leader chooses order:
 |  |         |      |  |  |         |  |  W = <WriteA, ReadA>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+2,W)
 |  |         |<-----X- X- X-------->|->|  Accepted(N+2,W)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB> .
 |  |         |      |  |  |         |  |           <WriteA, ReadA>
 |  |         |      |  |  |         |  |

Вищенаведений потік повідомляє нам, що узагальнений Паксос може використовувати семантику операцій, для уникнення зіткнень, та коли мимовільне впорядкування мережі не вдається. Це дозволяє зробити протокол на практиці швидше, ніж Швидкий Паксос. Однак, коли трапляється зіткнення, узагальненому Паксос потрібні дві додаткові поїздки в обидва кінці, щоб відновитися.

У загальному випадку такі тури неминучі і випливають з того, що під час раунду можна прийняти кілька команд. Це робить протокол дорожчим, ніж Паксос, коли конфлікти часті. Сподіваємось, можливі два вдосконалення узагальненого Паксос для покращення часу відновлення.[11]

• По-перше, якщо координатор є частиною кожного кворуму Приймачів, то він відновлюється в раунді N + 1 при зіткнення на раунді N. Координатор пропускає фазу 1 і пропонує на фазі 2 останню послідовність, яку він прийняв під час раунду N. Це зменшує витрати на відновлення одної поїздки в обидва кінці.
• По-друге, якщо обидва раунди N і N + 1 використовують унікальний і однаковий центрований кворум, коли Приймач виявляє зіткнення в N раунді. Він спонтанно пропонує в раунді N + 1 послідовність, що суфіксує обидві послідовності (і), прийняту в раунді N координатором та (ii) найбільший безконфліктний префікс, який він прийняв у раунді N. За такої зміни вартість відновлення — це затримка одного повідомлення, яка, очевидно, є оптимальною. Це випливає з того, що будь-який процес у цьому кворумі є кворумом читання для фази підготовки наступних раундів.[12]

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |          X<>X<>X       |  |  Verify(N,I,V) - BROADCAST
   |         |<---------X--X--X------>|->|  Accepted(N,V)
   |<---------------------------------X--X  Response(V)
   |         |          |  |  |       |  |

Швидкий візантійський Паксос[15] представлений Мартіном та Алвісі, усуває цю додаткову затримку, оскільки клієнт відправляє команди безпосередньо Приймачам.

Зверніть увагу, що Прийняте повідомлення у швидких візантійських Паксос надсилається всім Приймачам та всім Учням, тоді як Швидкий Паксос надсилає Прийняті повідомлення лише Учням):

Client    Acceptor     Learner
   |      |  |  |       |  |
   X----->|->|->|       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  |       |  |

Сценарій відмови однаковий для обох протоколів. Кожен Учень чекає отримання F + 1 однакових повідомлень від різних Приймачів. Якщо цього не відбудеться, самі Приймачі також будуть про це знати, і правильні Приймачі повторно транслюватимуть узгоджене значення:

Client    Acceptor     Learner
   |      |  |  !       |  |  !! One Acceptor is faulty
   X----->|->|->!       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,{V,W}) - BROADCAST
   |      |  |  !       |  |  !! Learners receive 2 different commands
   |      |  |  !       |  |  !! Correct Acceptors notice error and choose
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  !       |  |