Перегляд вихідного коду сторінки Алгоритм Паксос

Паксос ({{lang-en|Paxos}})&nbsp;— це набір протоколів, призначених для консенсусу в мережі ненадійних процесорів. Консенсус&nbsp;— процес отримання узгодженого результату групою учасників. Вирішити цю проблему складно, якщо в учасників або в засобах їх комунікації виникають помилки.<ref name="agree"><cite class="citation journal">Pease, Marshall; Shostak, Robert; Lamport, Leslie (April 1980). [http://research.microsoft.com/users/lamport/pubs/pubs.html#reaching «Reaching Agreement in the Presence of Faults»] {{Webarchive|url=https://web.archive.org/web/20070816121810/http://research.microsoft.com/users/lamport/pubs/pubs.html#reaching |date=16 серпня 2007 }}. ''[[Journal of the Association for Computing Machinery]]''. '''27''' (2)<span class="reference-accessdate">. Retrieved <span class="nowrap">2007-02-02</span></span>.</cite></ref>

Протоколи рішення задачі консенсусу є базовим елементом [[Тиражований автомат (автоматний підхід)|тиражованого автомата (автоматного підходу)]] у розподілених обчисленнях, що запропонував [[Леслі Лампорт]]<ref name="clocks"><cite class="citation journal">Lamport, Leslie (July 1978). [http://research.microsoft.com/users/lamport/pubs/pubs.html#time-clocks «Time, Clocks and the Ordering of Events in a Distributed System»] {{Webarchive|url=https://web.archive.org/web/20070816121810/http://research.microsoft.com/users/lamport/pubs/pubs.html#time-clocks |date=16 серпня 2007 }}. ''[[Communications of the ACM]]''. '''21''' (7): 558—565. [[Digital object identifier|doi]]:[[doi:10.1145/359545.359563|10.1145/359545.359563]]<span class="reference-accessdate">. Retrieved <span class="nowrap">2007-02-02</span></span>.</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref> і дослідив далі Ф. Шнайдер.

Протокол Паксос був вперше опублікований у 1989 році та був названий на честь вигаданої законодавчої системи, що застосовувалася на острові [[Паксос]] у Греції.<ref name="Lamport">{{Cite web |url=http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#lamport-paxos |title=Leslie Lamport's history of the paper |accessdate=21 листопада 2019 |archive-date=5 серпня 2011 |archive-url=https://web.archive.org/web/20110805112502/http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#lamport-paxos }}</ref> Пізніше був опублікований в науковій літературі в 1998 році.<ref name="paxos"><cite class="citation journal">Lamport, Leslie (May 1998). [http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos «The Part-Time Parliament»] {{Webarchive|url=https://web.archive.org/web/20070816121810/http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos |date=16 серпня 2007 }}. ''ACM Transactions on Computer Systems''. '''16''' (2): 133—169. [[Digital object identifier|doi]]:[[doi:10.1145/279227.279229|10.1145/279227.279229]]<span class="reference-accessdate">. Retrieved <span class="nowrap">2007-02-02</span></span>.</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref>

Сімейство протоколів Паксос включає спектр компромісів між кількістю процесорів, кількістю затримок повідомлень, рівня активності окремих учасників та кількістю відправлених повідомлень. Результат відмовостійкого узгодження не визначений, однак умови, при яких консенсус неможливий, дуже рідкісні.

Паксос зазвичай використовується, для копіювання файлу чи [[База даних|бази даних]]. Протокол намагається досягти прогресу навіть у періоди, коли деяка обмежена кількість вузлів не відповідає. Існує також механізм видалення або додавання нового вузла.

== Історія ==
У 1988&nbsp;р. [[Ненсі Лінч|Лінч]], Дрюк і Стокмейер продемонстрували<ref name="LDS88"><cite class="citation journal">Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (April 1988). [http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf «Consensus in the Presence of Partial Synchrony»] {{Webarchive|url=https://web.archive.org/web/20190618210307/https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf |date=18 червня 2019 }} <span class="cs1-format">(PDF)</span>. ''Journal of the ACM''. '''35''' (2): 288—323. [[CiteSeerX]]&nbsp;<span class="cs1-lock-free" title="Freely accessible">[//citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3423 10.1.1.13.3423]</span>. [[Digital object identifier|doi]]:[[doi:10.1145/42282.42283|10.1145/42282.42283]].</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref> розв'язність консенсусу в широкому сімействі «частково синхронних» систем. Паксос має сильну схожість з протоколом, який використовується для узгодження у «прогляді реплікації».<ref name="vr"><cite class="citation conference">Oki, Brian; Liskov, Barbara (1988). [http://portal.acm.org/citation.cfm?id=62549 «Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems»]. ''PODC '88: Proceedings of the seventh annual [[ACM Symposium on Principles of Distributed Computing]]''. pp.&nbsp;8–17. [[Digital object identifier|doi]]:[[doi:10.1145/62546.62549|10.1145/62546.62549]].</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref> Паксос запропонував особливо елегантний формалізм і включив одне з найбільш ранніх доказів безпеки для відмовостійкого протоколу розподіленого консенсусу.

Реконфігуровані машини мають міцні зв'язки з попередньою роботою над протоколами багатоадресної групи, які підтримують членство динамічної групи, наприклад роботи Бірмана 1985 та 1987 року практичного синхронного gbcast<ref name="BJ87"><cite class="citation journal">Birman, Kenneth; Joseph, Thomas (February 1987). «Reliable Communication in the Presence of Failures». ''ACM Transactions on Computer Systems'': 47–76.</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref> протоколу.

Протоколи Паксос є членами теоретичного класу рішень проблем, формалізованих як єдине узгодження з відмовами. Нижні межі цієї проблеми були доведені Кейдаром та Шраером. Derecho&nbsp;— це бібліотека програмного забезпечення [[C++|C ++]] для реплікації хмарних машин, що пропонує протокол Паксос, який інтегрований у систему. Цей протокол відповідає межам оптимальності Кейдара та Шраера і ефективно відображає сучасне обладнання віддаленого DMA (RDMA) центру обробки даних (але використовує [[TCP]], якщо RDMA недоступний).

== Припущення ==
Наступні припущення та визначення робляться явними. Методи розширення застосування не висвітлюються в цій статті.

=== Процесори ===

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

=== Мережа ===

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

=== Кількість процесорів ===
Загалом алгоритм узгодження може досягти прогресу, за умови використання <math>n=2F+1</math> процесорів, незважаючи на одночасний вихід з ладу будь-яких <math>F</math> процесорів: іншими словами, кількість справних процесів повинна бути строго більшою, ніж кількість несправних процесів. Однак, використовуючи реконфігурацію, може бути використаний протокол, який переживає будь-яку загальну кількість збоїв до тих пір, поки їх не більше ніж F одночасно.

== Ролі ==
Паксос описує дії процесорів за їх ролями в протоколі: клієнт, приймач, заявник, учень та провідник. У типових втіленнях один процесор може грати одну або більше ролей одночасно. Це не впливає на правильність протоколу&nbsp;— зазвичай поєднуються ролі, для поліпшення затримок та/або кількості повідомлень у протоколі.

; Клієнт: Клієнт надсилає ''запит'' до розподіленої системи та чекає ''відповіді'' . Наприклад, запит на запис у [[файл]] на розподіленому файловому сервері.
; Приймач (виборців): Приймачі виконують функцію відмовостійкої «пам'яті» протоколу. Приймачі збирають в групи, які називаються кворумами. Будь-яке повідомлення, надіслане Приймачу, має бути надіслане в кворум приймачів. Будь-яке повідомлення, отримане від Приймача, ігнорується, якщо копія не отримана від кожного Приймача в кворумі.
; Заявник: Заявник просуває запит клієнта, намагаючись переконати Приймачів погодитися з ним. Виконує функцію координатора для зрушення протоколу вперед, коли виникають конфлікти.
; Учень: Учні виступають чинником реплікації протоколу. Після того, як Приймачі погодили запит Клієнта, Учень може вжити потрібні заходи (тобто: виконати запит та надіслати відповідь клієнту). Для покращення доступності обробки, можна додати додаткових учнів.
; Провідник: Паксос вимагає від зазначеного Заявника (його називають провідником), досягнення прогресу. Багато процесів можуть вважати, що вони ведуть, але протокол гарантує прогрес лише в тому випадку, якщо в кінцевому підсумку обраний один з них. Якщо два процеси вважають, що вони провідники, вони можуть зупиняти протокол, постійно пропонуючи суперечливі оновлення.

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

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

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

== Властивості безпеки та живості ==
Щоб гарантувати ''безпеку'', алгоритм Паксос визначає три властивості та забезпечує постійне дотримання перших двох, незалежно від схеми відмов:

; Вагомість (або нетривіальність): Вибирати та вивчати можна лише запропоновані значення.
; Домовленість (або узгодженість чи безпека): Немає двох окремих учнів можуть засвоїти різні значення (або не може бути більше одного визначеного значення)
; Припинення (або живість): Якщо було запропоновано значення C, то зрештою, учень L дізнається про деяке значення (якщо залишилось достатньо уцілілих процесорів).

Зауважте, що Паксос не гарантує завершення і тому не має властивості живості.

== Типове розгортання ==
У більшості випадків кожен процес, що бере участь виконує три ролі; Заявника, Приймача та Учня.<ref name="live">Chandra, Tushar; Griesemer, Robert; Redstone, Joshua (2007). [http://research.google.com/pubs/pub33002.html ''Paxos Made Live&nbsp;— An Engineering Perspective''] {{Webarchive|url=https://web.archive.org/web/20160721041244/http://research.google.com/pubs/pub33002.html|date=21 липня 2016}}. ''PODC '07: 26th ACM Symposium on Principles of Distributed Computing''. pp.&nbsp;398–407. [[Digital object identifier|doi]]:[[doi:10.1145/1281100.1281103|10.1145/1281100.1281103]]. ISBN 9781595936165</ref> Це значно знижує складність повідомлення, не жервуючи правильністю.

Об'єднуючи ролі, протокол «згортається» в ефективне розгортання стилю клієнт-майстер-репліка, характерне для спільноти баз даних. Перевага протоколів Паксос (включно з утіленням з об'єднаними ролями) це гарантія його властивостей безпеки.

== Базовий Паксос ==
Це найбазовіший протокол із сім'ї Паксос. Кожен «примірник» базового протоколу Паксос визначає одне вихідне значення. Протокол триває декілька раундів. Вдалий раунд має 2 фази: фазу 1 (яка має дві частини ''a'' і ''b'') і 2 фазу (яка теж має дві частини ''a'' і ''b''). Дивіться нижче опис фаз. Пам'ятайте, що ми припускаємо асинхронну модель, тому, наприклад, процесор може перебувати в одній фазі, а інший процесор&nbsp;— в іншій.

=== Фаза 1 ===

==== Фаза 1а: ''Підготовка'' ====

: Заявник створює повідомлення, яке ми називаємо «Підготовка» та ототожнює з числом ''n'' . Зауважте, що ''n''&nbsp;— це не значення, а лише число, яке однозначно ідентифікує це початкове повідомлення, запропоноване заявником (яке повинно бути надіслане приймачем). Число ''n'' повинно бути більше, ніж будь-яке число, використовуване в будь-якому з попередніх фазах ''Підготовки'' повідомлення цього Заявника. Потім він надсилає повідомлення ''Підготовка,'' що містить ''n,'' до кворуму приймачів . Зауважте, що повідомлення цієї фази містить лише число ''n'' (тобто воно не повинно містити, наприклад, запропоноване значення, яке часто позначається ''v''). Заявник вирішує, хто в кворумі {{Як|date=October 2018}} <sup class="noprint Inline-Template" style="white-space:nowrap;">]</sup> . Заявник не повинен ініціювати Paxos, якщо він не може спілкуватися хоча б з кворумом приймачів.

==== Фаза 1b: ''Зобов'язання'' ====

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

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

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

=== Фаза 2 ===

==== Фаза 2а: ''Погодження'' ====

: Якщо Заявник отримує більшість «обіцянь» від кворуму Приймачів, йому необхідно встановити значення ''v'' своїй пропозиції. Якщо будь-який Приймач раніше прийняв будь-яку пропозицію, то вони надішлють свої значення Заявнику, який тепер повинен встановити значення своєї пропозиції, ''v'', на значення, пов'язане з найвищим числом пропозицій (назвемо його ''z''), про яке повідомили Приймача. Якщо жоден з Приймачів не прийняв пропозицію до цього моменту, то Замовник може вибрати значення, яке він спочатку хотів запропонувати, скажімо ''x''<ref name="paxos-simple">Lamport, Leslie (2001). [http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#paxos-simple Paxos Made Simple] {{Webarchive|url=https://web.archive.org/web/20110805112502/http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#paxos-simple |date=5 серпня 2011 }} ''ACM SIGACT News (Distributed Computing Column) 32'', 4 (Whole Number 121, December 2001) 51-58.</ref> .

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

==== Фаза 2b: ''Прийняття'' ====

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

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

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

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

=== Коли раунди провалюються ===

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

=== Paxos можна використовувати для вибору лідера ===

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

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

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

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

<pre>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
   |         |          |  |  |       |  |
</pre><pre>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
   |         |          |  |  |       |  |

</pre> Тут V&nbsp;— останній із (Va, Vb, Vc).

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

==== Базовий Паксос, коли Приймач виходить з ладу ====
 На наступній схемі один з Приймачів відмовляється, тому розмір Кворуму стає 2. У цьому випадку протокол Базовий Паксос все ще є успішним. <pre>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
   |         |          |  |          |  |
</pre>

 

==== Базовий Паксос, коли Учень виходить з ладу ====
 У наступному випадку один із учнів виходить з ладу, але протокол Базовий Паксос все-таки є успішним. <pre>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
   |         |          |  |  |       |
</pre>

==== Базовий Паксос, коли Заявник виходить з ладу ====
 У цьому випадку Заявник виходить з ладу після заявлених значень, але до досягнення згоди. Зокрема, воно не в середині повідомлення Accept, тому значення має лише один Приймач кворуму. Тим часом обирається новий Провідник. Зверніть увагу, що в цьому випадку є два раунди (раунди проходять вертикально, зверху вниз). <pre>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
   |         |          |  |  |       |  |
</pre>

==== Базовий Паксос, коли конфліктують декілька пропозицій ====
 Найскладніший випадок, коли кілька Заявників вважають себе лідерами. Наприклад, поточний лідер може на деякий час вийти з ладу та пізніше відновитись, але інші Заявники вже обрали нового лідера. При цьому прийнятий лідер цього ще не дізнався і намагається розпочати новий раунд у конфлікті з нинішнім лідером. На діаграмі нижче показано 4 невдалих раунди, але їх може бути більше (як це запропоновано внизу діаграми). <pre>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 ...
</pre>

== Мульти-Паксос ==
Типове розгортання Паксос вимагає безперервного потоку узгоджених значень, що діють як команди для розподіленої машини. Якщо кожна команда є результатом одного екземпляра протоколу [[Алгоритм Паксос|Базовий Паксос]], вийде значна кількість накладних витрат.

Якщо лідер стабільний, фаза 1 стає непотрібною. Таким чином, можна пропустити фазу 1 для майбутніх екземплярів протоколу з тим же лідером.

Для цього [[Круглі числа|кругле число]] <tt>I</tt> включається разом із кожним значенням, яке збільшується в кожному раунді одним і тим же Провідником. Мульти-Паксос зменшує затримку безвідмовного повідомлення (пропозицію до навчання) з 4 затримок до 2 затримок.

=== Графічне зображення потоку повідомлень в Базовий Паксос ===

==== Мульти-Паксос без відмов ====
 На наступній діаграмі показаний лише один екземпляр базового протоколу Паксос з початковим лідером. Зауважте, що Мульти-Паксос складається з декількох примірників базового протоколу Паксос. <pre>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
   |         |          |  |  |       |  |
</pre> де V = останній з (Va, Vb, Vc). 

==== Мульти-Паксос, коли фаза 1 може бути пропущена ====
 У цьому випадку екземпляри послідовності базового протоколу Паксос використовують того ж самого лідера, тому фаза 1, яка складається з більш коротших фаз Підготувати та Обіцяти, пропускається. Зауважте, що лідер повинен бути стабільним, тобто не повинен виходити з ладу або змінюватися. <pre>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
   |         |          |  |  |       |  |
</pre>

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

 Наведена нижче схема представляє перший "екземпляр" базового протоколу Паксос, коли ролі Заявника, Приймача та Учня згортаються в роль "Сервер". <pre>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
   |         |  |  |
</pre>

==== Мульти-Паксос, коли ролі згортаються, а лідер стійкий ====
 У наступних випадках базового протоколу Паксос з тим самим лідером, що і в попередніх екземплярах базового протоколу Паксос, фаза 1 може бути пропущена. <pre>Client      Servers
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N,I+1,W)
   |         X<>X<>X  Accepted(N,I+1)
   |<--------X  |  |  Response
   |         |  |  |
</pre>

== Оптимізація ==
Для зменшення кількості повідомлень та покращення продуктивності протоколу можна здійснити ряд оптимізацій. Нижче наведено декілька таких оптимізацій.

: 

: 

== Дешевий Паксос ==
Дешевий Паксос розширює [[Алгоритм Паксос|Базовий Паксос,]] щоб переносити збої F з основними процесорами F + 1 та F допоміжними процесорами шляхом динамічної корекції після кожного збою.

Це зниження потреби в процесорі відбувається за рахунок життєздатності; якщо занадто багато основних процесорів виходять з ладу за короткий час, система повинна зупинитися, поки допоміжні процесори не зможуть переконфігурувати систему. У стабільні періоди допоміжні процесори не беруть участі в протоколі.

=== Потік повідомлень: Дешевий Мульти-Паксос ===
 Приклад, що включає три основних приймача, один допоміжний приймач і розмір кворуму в три, показує вихід з ладу одного основного процесора та наступну конфігурацію: <pre>{  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)
|            |  |        |       |
</pre>

== Швидкий Паксос ==
Швидкий узагальнює [[Алгоритм Паксос|базовий Паксос,]] щоб зменшити затримки повідомлення в кінці. У базовому Паксос, затримка повідомлення від запита клієнта до навчання становить 3 затримки за повідомлення. Швидкий Paxos дозволяє затримати 2 повідомлення, але вимагає, щоб (1) система складалася з ''3'' приймачів ''+ 1 +,'' щоб допустити до ''f'' помилок, і (2) Клієнт надсилає свій запит у кілька напрямків .

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

Якщо лідер виявить збій, то він вирішує його, відправивши повідомлення на новий раунд. Ця координована методика відновлення вимагає чотирьох затримок повідомлень від клієнта до учня.

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

=== Потік повідомлень: Швидкий Паксос, безконфліктний ===
<pre>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)
   |         |          |  |  |  |       |  |
</pre>

=== Потік повідомлень: Швидкий Паксос, суперечливі пропозиції ===
 <small>Конфлікт пропозицій з координованим відновленням.</small> <small>Примітка: протокол не вказує, як обробляти скинутий запит клієнта.</small> <pre>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)
 |  |      |        |  |  |  |      |  |
</pre> <small>Суперечність пропозицій з неузгодженим відновленням.</small> <pre>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)
 |  |      |        |  |  |  |      |  |
</pre>

=== Потік повідомлень: Швидкий Паксос з некоординованим відновленням, згорнуті ролі ===
<pre>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)
 |  |         |  |  |  |
</pre>

== Узагальнений Паксос ==
Узагальнений консенсус досліджує взаємозв'язок операцій [[Реплікація (бази даних)|реплікованої]] машини та протоколу узгодження, який його реалізує<ref name="general"><cite class="citation journal">Lamport, Leslie (2005). [http://research.microsoft.com/users/lamport/pubs/pubs.html#generalized «Generalized Consensus and Paxos»] {{Webarchive|url=https://web.archive.org/web/20070816121810/http://research.microsoft.com/users/lamport/pubs/pubs.html#generalized|date=16 серпня 2007}}.</cite> <span class="cs1-hidden-error error citation-comment">Cite journal requires <code class="cs1-code">&#x7C;journal=</code> ([[Довідка:CS1 errors#missing periodical|help]])</span><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref> . Основне відкриття передбачає оптимізацію Паксос, коли суперечливі пропозиції можуть бути застосовані в будь-якому порядку, тобто коли запропоновані операції є [[Комутативність|комутаційними операціями]] для машини. У таких випадках конфліктуючі операції можуть бути прийняті як уникнення затримок, необхідних для вирішення конфліктів.

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

=== Потік повідомлень: Узагальнений Паксос (приклад) ===
<pre>
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>
 |  |         |      |  |  |         |  |
</pre>

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

У загальному випадку такі тури неминучі і випливають з того, що під час раунду можна прийняти кілька команд. Це робить протокол дорожчим, ніж Паксос, коли конфлікти часті. Сподіваємось, можливі два вдосконалення узагальненого Паксос для покращення часу відновлення.<ref name="fggc"><cite class="citation conference">Pierre, Sutra; Marc, Shapiro (2011). [http://pagesperso-systeme.lip6.fr/Marc.Shapiro/papers/FGGC-SRDS-2011.pdf «Fast Genuine Generalized Consensus»] {{Webarchive|url=https://web.archive.org/web/20141212012629/http://pagesperso-systeme.lip6.fr/Marc.Shapiro/papers/FGGC-SRDS-2011.pdf |date=12 грудня 2014 }} <span class="cs1-format">(PDF)</span>. ''SRDS'11: 30th IEEE Symposium on Reliable Distributed Systems''.</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref>

* По-перше, якщо координатор є частиною кожного кворуму Приймачів, то він відновлюється в раунді N + 1 при зіткнення на раунді N. Координатор пропускає фазу 1 і пропонує на фазі 2 останню послідовність, яку він прийняв під час раунду N. Це зменшує витрати на відновлення одної поїздки в обидва кінці.
* По-друге, якщо обидва раунди N і N + 1 використовують унікальний і однаковий центрований кворум, коли Приймач виявляє зіткнення в N раунді. Він спонтанно пропонує в раунді N + 1 послідовність, що суфіксує обидві послідовності (і), прийняту в раунді N координатором та (ii) найбільший безконфліктний префікс, який він прийняв у раунді N. За такої зміни вартість відновлення&nbsp;— це затримка одного повідомлення, яка, очевидно, є оптимальною. Це випливає з того, що будь-який процес у цьому кворумі є кворумом читання для фази підготовки наступних раундів.<ref>{{Cite book|title=Vertical Paxos and Primary-backup Replication|last=Lamport|first=Leslie|last2=Malkhi|first2=Dahlia|last3=Zhou|first3=Lidong|date=2009|series=PODC '09|publisher=ACM|location=New York, NY, USA|pages=312–313|doi=10.1145/1582716.1582783|isbn=9781605583969|journal=Proceedings of the 28th ACM Symposium on Principles of Distributed Computing}}</ref>

== Візантійський Паксос ==
Паксос також може бути поширений на підтримку довільних відмов учасників, включаючи брехню, вигадку повідомлень, змову з іншими учасниками, вибіркове неучасть тощо. Такі типи невдач називаються [[Задача візантійських генералів|задачами візантійських генералів]].<ref name="byzgen"><cite class="citation journal">Lamport, Leslie; Shostak, Robert; Pease, Marshall (July 1982). [http://research.microsoft.com/users/lamport/pubs/pubs.html#byz «The Byzantine Generals Problem»] {{Webarchive|url=https://web.archive.org/web/20070816121810/http://research.microsoft.com/users/lamport/pubs/pubs.html#byz |date=16 серпня 2007 }}. ''ACM Transactions on Programming Languages and Systems''. '''4''' (3): 382—401. [[CiteSeerX]]&nbsp;<span class="cs1-lock-free" title="Freely accessible">[//citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.2312 10.1.1.64.2312]</span>. [[Digital object identifier|doi]]:[[doi:10.1145/357172.357176|10.1145/357172.357176]]<span class="reference-accessdate">. Retrieved <span class="nowrap">2007-02-02</span></span>.</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref>

Задача візантійських генералів<ref>{{Cite journal|last=Castro|first=Miguel|last2=Liskov|first2=Barbara|date=February 1999|title=Practical Byzantine Fault Tolerance|url=http://pmg.csail.mit.edu/papers/osdi99.pdf|journal=Proceedings of the Third Symposium on Operating Systems Design and Implementation|pages=173–186|access-date=5 березня 2018|archive-date=4 березня 2018|archive-url=https://web.archive.org/web/20180304201549/http://www.pmg.csail.mit.edu/papers/osdi99.pdf}}</ref> представлена Кастро та [[Барбара Лісков|Ліськовим,]] додає додаткове повідомлення (Перевірити), яка поширує знання та перевіряє дій інших процесорів:

=== Потік повідомлень: Задача візантійських генералів Мульти-Паксос, стаціонарний стан ===
<pre>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)
   |         |          |  |  |       |  |
</pre> Швидкий візантійський Паксос<ref>{{Cite journal|last=Martin|first=Jean-Philippe|last2=Alvisi|first2=Lorenzo|date=July 2006|title=Fast Byzantine Consensus|url=https://www.cs.utexas.edu/~lorenzo/papers/fab.pdf|journal=IEEE Transactions on Dependable and Secure Computing|volume=3|issue=3|pages=202–215|doi=10.1109/TDSC.2006.35|access-date=5 березня 2018|archive-date=18 січня 2021|archive-url=https://web.archive.org/web/20210118012605/https://www.cs.utexas.edu/~lorenzo/papers/fab.pdf}}</ref> представлений Мартіном та Алвісі, усуває цю додаткову затримку, оскільки клієнт відправляє команди безпосередньо Приймачам.

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

=== Потік повідомлень: Швидкий візантійський Мульти-Паксон, стаціонарний стан ===
<pre>Client    Acceptor     Learner
   |      |  |  |       |  |
   X----->|->|->|       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  |       |  |
</pre> Сценарій відмови однаковий для обох протоколів. Кожен Учень чекає отримання F + 1 однакових повідомлень від різних Приймачів. Якщо цього не відбудеться, самі Приймачі також будуть про це знати, і правильні Приймачі повторно транслюватимуть узгоджене значення:

=== Потік повідомлень: Швидкий візантійський Мульти-Паксон, невдача ===
<pre>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)
   |      |  |  !       |  |
</pre>

== Адаптація Паксос до мереж RDMA ==
З появою дуже швидких надійних мереж центрів обробки даних, які підтримують віддалений DMA (RDMA), виникла значна зацікавленість в оптимізації Паксос для використання апаратного розвантаження, в якому [[Мережева плата|мережева карта]] інтерфейсу та мережеві маршрутизатори забезпечують надійність та контроль перевантаженості мережевого рівня, звільняючи хост-процесор для інших завдань. Бібліотека [http://GitHub.com/Derecho-Project Derecho C ++ Paxos] {{Webarchive|url=https://web.archive.org/web/20220114085615/https://github.com/derecho-project/ |date=14 січня 2022 }}&nbsp;— це реалізація Паксос з відкритим кодом, яка досліджує цей варіант<ref name="Derecho"><cite class="citation journal">Jha, Sagar; Behrens, Jonathan; Gkountouvas, Theo; Milano, Matthew; Song, Weijia; Tremel, Edward; van Renesse, Robbert; Zink, Sydney; Birman, Ken (April 2019). «Derecho: Fast State Machine Replication for Cloud Services». ''[[ACM Transactions on Computer Systems]]''. '''36''' (2). [[Digital object identifier|doi]]:[[doi:10.1145/3302258|10.1145/3302258]].</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref> .

Derecho пропонує як класичний Paxos, що має довговічність даних у послідовності повного відключення / перезавантаження, так і вертикальний Paxos (атомний передавач) для реплікації в пам'яті та синхронізації стану та машини. Протоколи Paxos, застосовані Derecho, потребували адаптації для максимізації асинхронного потоку даних та усунення інших джерел затримки на критичному шляху лідера. Таким чином, це дозволяє Derecho підтримувати повну двонаправлену швидкість передачі даних RDMA. На відміну від цього, хоча традиційні протоколи Paxos можуть бути переміщені до мережі RDMA шляхом простого відображення операцій надсилання повідомлень у нативній операції RDMA, але це залишає затримки в зворотному напрямку на критичному шляху. У високошвидкісних мережах RDMA навіть невеликі затримки можуть бути досить великими, щоб запобігти використанню повної потенційної пропускної здатності.

== Використання Паксос ==

* Google використовує алгоритм Паксос у своїй [[Розподілений менеджер блокувань|службі розподіленого блокування]] Chubby, щоб підтримувати послідовність реплік у разі відмови. Chubby використовується [[Bigtable|Bigtable,]] який зараз випускається в Google Analytics та інших продуктах.
* [[Spanner (бази даних)|Google Spanner]] та Megastore використовують алгоритм Паксос.
* [http://openreplica.org Служба реплікації OpenReplica] {{Webarchive|url=https://web.archive.org/web/20180809051426/http://openreplica.org/ |date=9 серпня 2018 }} використовує Паксос для підтримання копій для системи відкритого доступу, яка дозволяє користувачам створювати об'єкти, стійкі до відмов. Це забезпечує високу ефективність за рахунок одночасних раундів та гнучкість завдяки динамічним змінам членства.
* IBM нібито використовує алгоритм Паксос в своєму продукті IBM SAN Volume Controller для реалізації [[Віртуальна машина|віртуальної машини]] загального призначення, стійкої до відмов, що використовується для запуску конфігураційних та керуючих компонентів служб віртуалізації зберігання, пропонованих кластером. ([https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf Оригінальний дослідницький документ MIT & IBM] {{Webarchive|url=https://web.archive.org/web/20200521052036/https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf |date=21 травня 2020 }})
* Microsoft використовує Paxos в [http://research.microsoft.com/pubs/64604/osr2007.pdf службі керування кластерами автопілотів] {{Webarchive|url=https://web.archive.org/web/20160507172918/http://research.microsoft.com/pubs/64604/osr2007.pdf |date=7 травня 2016 }} від компанії Bing та в кластеризації відключення Windows Server.
* WANdisco впровадив Paxos в рамках своєї технології активної реплікації DConE.<ref name="WANdisco">Aahlad et al.(2011). [https://www.wandisco.com/get?f=documentation%2Fwhitepapers%2FWANdisco_DConE_White_Paper.pdf «The Distributed Coordination Engine (DConE)»] {{Webarchive|url=https://web.archive.org/web/20160415093538/https://www.wandisco.com/get?f=documentation%2Fwhitepapers%2FWANdisco_DConE_White_Paper.pdf |date=15 квітня 2016 }}. WANdisco white paper.</ref>
* [[XtreemFS]] використовує алгоритм узгодження оренди на основі Paxos для стійкої до відмов та послідовної реплікації файлових даних та метаданих.<ref name="flease">Kolbeck, Björn; Högqvist, Mikael; Stender, Jan; Hupfeld, Felix (2011). [http://www.xtreemfs.org/publications/flease_paper_ipdps.pdf «Flease&nbsp;— Lease Coordination without a Lock Server»] {{Webarchive|url=https://web.archive.org/web/20210905154531/http://www.xtreemfs.org/publications/flease_paper_ipdps.pdf |date=5 вересня 2021 }}. 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2011).</ref>
* Heroku використовує [https://github.com/ha/doozerd Doozerd,] {{Webarchive|url=https://web.archive.org/web/20191016010439/https://github.com/ha/doozerd |date=16 жовтня 2019 }} який реалізує Paxos для послідовного розподіленого сховища даних.
* [[Ceph (програмне забезпечення)|Ceph]] використовує Paxos як частину процесів монітора, щоб узгодити, які екранні екрани знаходяться в кластері.
* Розподілена база даних Slustrix Clustrix використовує Paxos для [http://docs.clustrix.com/display/CLXDOC/Consistency,+Fault+Tolerance,+and+Availability розподіленої роздільної здатності транзакцій] {{Webarchive|url=https://web.archive.org/web/20191206163009/http://docs.clustrix.com/display/CLXDOC/Consistency,%2BFault%2BTolerance,%2Band%2BAvailability |date=6 грудня 2019 }} .
* [[Neo4j|База]] даних [[Neo4j|графіків]] HA [[Neo4j]] реалізує Paxos, замінюючи Apache ZooKeeper з версії 1.9
* База даних [[Apache Cassandra]] NoSQL використовує лише Paxos для функції [https://www.datastax.com/dev/blog/lightweight-transactions-in-cassandra-2-0 легкої ваги] {{Webarchive|url=https://web.archive.org/web/20190420134950/https://www.datastax.com/dev/blog/lightweight-transactions-in-cassandra-2-0 |date=20 квітня 2019 }}
* Amazon Elastic Container Services використовує Paxos для підтримки [https://www.allthingsdistributed.com/2015/07/under-the-hood-of-the-amazon-ec2-container-service.html послідовного перегляду стану кластерів] {{Webarchive|url=https://web.archive.org/web/20200604183208/https://www.allthingsdistributed.com/2015/07/under-the-hood-of-the-amazon-ec2-container-service.html |date=4 червня 2020 }}

== Примітки ==
{{reflist}}

[[Категорія:Розподілені алгоритми]]
[[Категорія:Розподілені обчислення]]
[[Категорія:Сторінки з неперевіреними перекладами]]