Изменения
Нет описания правки
Описан много где разными словами<ref>https://habr.com/ru/post/346180/</ref><ref>https://lamport.azurewebsites.net/pubs/paxos-simple.pdf</ref><ref>https://en.wikipedia.org/wiki/Paxos_(computer_science)#Basic_Paxos</ref><ref>https://habr.com/ru/post/222825/</ref>.
Обычно используется для хранения самых-самых важных данных.
Тут довольно много деталей опущено, так что реализовать это на практике довольно сложно<ref>https://doi.org/10.1145/1281100.1281103</ref>.
== Алгоритм ==
У принимающего есть две независимых компоненты состояния: кому он что-нибудь ''пообещал'' (только лидер и номер голосования) и какое предложение он ''принял'' (от какого лидера, номер голосования, какое значение).
'''Фаза 1a (подготовка)''': лидер посылает сообщение $(1a, k)$ кворуму принимающих всем принимающим (или вообще всем, а и ждёт ответа от кворума?на второй фазе). Пока никаких предложений нет.
'''Фаза 1b (обещание)''': каждый принимающий начинает выбирать предложение с максимальным номером:
# Если пришло предложение больше, чем все предыдущие, то принимающий ''обещает'' лидеру не принимать предложения с меньшим номером, отвечает $(1b, k, ack, 0, 0)$.
Но если какое-то предложение с меньшим номером $k'$ уже было ''принято'' со значением $v'$ (это происходит на фазе 2), то отвечает $(1b, k, ack, k', v')$, чтобы лидер был в курсе.
# Если пришло предложение меньше, чем имеющийся максимум $k''``$, ничего не делаем. Ну, можем ответить $(1b, k', nack)$ для оптимизации.
Если лидер видит хотя бы один nack, то он понимает, что его обогнали, и начинает фазу 1 заново, подняв своё $k$ до присланного $k'+1$ (это просто оптимизация, чтобы не тормозить с перевыбором лидера).
Таким образом, если у нас несколько лидеров, они будут друг другу активно мешать.
== Модификации ==
Переконфигурация — отдельная задача.
=== Multi paxos ===
Если нам нужно прийти к нескольким консенсусам, то можно вместо запуска нескольких копий Paxos выполнить выбор лидера и первую фазу один раз для всех копий сразу.
Тогда в них будут одинаковые голосования, но они всё ещё будут работать.
Зато сильно сокращается задержка.
=== Fast Paxos ===
=== Dynamic Paxos ===
Можно добавить отдельную операцию "изменение конфигурации" в RSM.
=== Cheap Paxos ===
Если мы хотим пережить много отказов и нам нужно много процессов, то базовый Paxos посылает сообщение всем и ждёт кворума.
Работает быстро, но шлёт много сообщений.
Можно сначала слать только какому-то конкретному элементу кворума, а остальных игнорировать.
И подключать остальных только если кворум долго не отвечает.
В обычном режиме будет меньше сообщений, но при сбоях увеличивается задержка (потому что нужно обнаружить сбой и подключить лежащие в стороне процессы).
