Может ли акцептор в Paxos принять другое значение после того, как он уже принял?

Question

В алгоритме Multi-Paxos рассмотрите этот поток сообщений с точки зрения акцептора:

receive: Prepare (N)

reply: Promise (N, null)

получить: Принять! (N, V1)

ответить: Принять (N, V1)

получить: Принять! (N + 1, V2)

ответить:?

Какой должна быть реакция акцептора в этом случае согласно протоколу?Должен ли он ответить с помощью Accepted (N + 1, V2) или игнорировать второе Accept!?

Я полагаю, что этот случай может произойти в Multi-Paxos, когда второй заявитель выходит в сеть и считает, что он есть (ивсегда был) лидером, поэтому он посылает свой Принять без подготовки.Или если его Prepare просто не дошел до акцептора.Если этот случай может не произойти, вы можете объяснить, почему?

Answer 1

Я не согласен с обоими другими ответами.

1. Multi-Paxos не говорит, что Лидер является единственным предложителем; это приведет к тому, что система будет иметь единственную точку отказа .Даже во время сетевых разделов система не сможет прогрессировать.Multi-Paxos - это оптимизация, позволяющая одному узлу ( Leader ) пропустить некоторые фазы подготовки.Другие узлы, считая, что лидер мертв, могут попытаться продолжить экземпляр от ее имени, но все равно должны использовать полный протокол Basic-Paxos.

2. Отсутствие сообщения о принятии нарушает алгоритм Paxos, Акцептор должен принимать все значения, если он не обещал не принять его. (Игнорирование разрешено, но не рекомендуется; это просто потому, что разрешены пропущенные сообщения.)

3. Существует также элегантное решение для этого.Проблема с номером раунда лидера (N + 1 в вопросе).

Вот некоторые предположения:

• У вас есть такая схемаидентификаторы не пересекаются во всех узлах (в любом случае требуется Paxos).
• У вас есть способ определить, какой узел является экземпляром Leader per Paxos (требуется Multi-Paxos).Лидер может переключаться с одного экземпляра Paxos на другой.Помимо: Парламент с частичной занятостью предполагает, что это сделано Лидером, выигравшим предыдущий инстанс Paxos (Раздел 3.1), и указывает, что она может оставаться Лидером, пока она жива или является самой богатой(Раздел 3.3.1).У меня есть явное значение ELECT_NEW_LEADER: , которое предлагается через Paxos.
• Лидер пропускает только фазу подготовки при начальном раунде на экземпляр;и использует полный Базовый Паксос в последующих раундах.

С этими допущениями решение очень просто.Лидер просто выбирает действительно низкий круглый идентификатор для начальной фазы принятия.Этот идентификатор (который я назову INITIAL_ROUND_ID) может быть любым, если он ниже, чем круглые идентификаторы всех узлов.В зависимости от выбранной вами схемы выбора идентификатора будет работать либо -1, 0, либо Integer.MIN_VALUE.

Это работает, потому что другой узел (я назову его Стюартом) должен пройти через полный протокол Paxos дляпредложить что-нибудь и его раунд ID всегда больше, чем INITIAL_ROUND_ID .Есть два случая, чтобы рассмотреть: достигли ли сообщения Принятия Лидера какого-либо из узлов, что сообщение Стюарта подготовило.

Когда фаза Принятия Лидера не достигла ни одного узла, Стюартне получит никакого значения в любом Обещании и может продолжаться так же, как в обычных Basic-Paxos.

И когда фаза принятия Лидера достигнет узла, Стюарт получит обратнозначение в обещании, которое используется для продолжения алгоритма, как в Basic-Paxos.

В любом случае, поскольку идентификатор раунда Стюарта больше, чем INITIAL_ROUND_ID, любые медленные сообщения Accept, которые узел получает от лидеравсегда приводит к Nack.

Специальной логики на Acceptor или Stewart нет.И минимальная специальная логика на Лидере (а именно, выберите действительно низкий INITIAL_ROUND_ID).

---

Обратите внимание, если мы изменим вопрос ОП на один символ, тогда сам ответ ОП будет правильным: Nack.

• получить: подготовить (N)
• ответить: обещание (N, ноль)
• получить: принять! (N, V1)
• ответить: принято(N, V1)
• получить: принять! ( N-1 , V2)
• ответить: Nack (N, V1)

Но в его нынешнем виде его ответ нарушает алгоритм Паксоса;должно быть Принять!

• получить: Подготовить (N)
• ответить: Обещание (N, ноль)
• получить: Принять! (N, V1)
• ответить: Принято (N, V1)
• Получить: Принять! ( N + 1 , V2)
• ответить: Принять! (N + 1, V2)

Answer 2

Возможно, более простой ответ состоит в том, чтобы заметить, что это тот случай, когда команда Prepare (N + 1) была принята большинством, которое не включало рассматриваемый акцептор.

Для уточнения: Однажды лидерзнает, что какое-то большинство имеет Обещанное (N + 1), затем отправляет Accept (N + 1, x) на всем акцепторам, и даже если некоторые другие большинство акцепторов отвечают Accepted (N + 1), после чего достигается консенсус.

Это не такой уж необычный сценарий.

Answer 3

(отвечая на мой вопрос.)

В настоящее время я понимаю, что я не должен принимать значение в N + 1 (то есть вообще не отвечать или не отправлять NACK), что вынуждает лидера начать еще один раунд с подготовкой (если большинство не достигло). консенсуса пока нет). После того, как я получу Подготовку (N + 2), я отвечу Обещанием (N + 2, V1) и продолжу как обычно.

Answer 4

Правильность Multi-Paxos обусловлена ​​требованием, чтобы лидер ( т.е. , proposer) не менялся между последовательными экземплярами Paxos.От Парламент с частичной занятостью Раздел 3.1 (Протокол парламента с несколькими указами):

Логически, парламентский протокол [он же Multi-Paxos] использовал отдельный экземпляр полного протокола Синода [aka Paxos] для каждого номера указа.Тем не менее, один президент [aka proposer / лидер] был выбран для всех этих случаев , и он выполнил первые два шага протокола только один раз. _{[Добавлен акцент на мое.]}

Поэтому Multi-Paxos делает предположение, что случай, который вы описываете, - когда второй заявитель приходит в онлайн и считает, что он есть (и всегдабыл) лидером - никогда не случится.Если такой случай может произойти, то не следует использовать Multi-Paxos.Что касается второй возможности - когда второй заявитель Prepare не достиг акцептора, - тот факт, что второй заявитель уже отправил Accept!, означает, что он ранее отправил Prepare, который был Promised посредствомкворум акцепторов.Поскольку акцепторы уже пообещали первому заявителю в раунде N, то второй заявитель Prepare должен быть отправлен до раунда N.Следовательно, конечный Accept!(N+1,V2) должен иметь счетчик меньше N.

Редактировать: Следует также отметить, что эта версия протокола неустойчивый к Византийский сбой :

[Протокол Парламента Паксона] не допускает произвольных, злонамеренных сбоев и не гарантирует ответ в ограниченном времени. _{- Парламент с частичной занятостью , раздел 4.1}