Каково правильное поведение для агента Paxos в этом сценарии?

Question

Я заглядываю в Паксос, и меня смущает, как должен вести себя алгоритм в этом надуманном примере. Я надеюсь, что диаграмма ниже объясняет сценарий.

Несколько баллов:

• Каждый агент выступает в роли автора / получателя / обучающегося
• Готовить сообщения имеют форму (instance, proposal_num)
• Предлагаемые сообщения имеют форму (instance, proposal_num, proposal_val)
• Сервер1 и Сервер2 оба решают начать процесс предложения одновременно
• В начале сообщения M1, M2 и M3 появляются одновременно

Здесь кажется, что, хотя протокол «правильный», то есть выбрано только одно значение S2, Server1 и Server2 считают, что оно было выбрано из-за разных номеров предложений.

Алгоритм Paxos завершается только тогда, когда сообщение Decide(...) отправляется учащимся? Должно быть, я неправильно понял Paxos Made Simple , но я подумал, что выбор был сделан в тот момент, когда заявители получили кворум для своих Propose(...) сообщений.

Если выбор сделан только после того, как агенту отправлено сообщение Decide(...), то должен ли Server2 прекратить отправку Decide(1, 5, S2) при восстановлении, поскольку он видел более позднюю Prepare(1, 7)?

Answer 1

Просто переопределим термины (давайте также отбросим 1, потому что мы рассматриваем только одну итерацию Paxos):

1) Предложение (n) == предложение (n), сообщение от автора с текущей идентификационной информацией n

2) AcceptPrepare (n, v) == ack (n, v), сообщение отправлено заявителю n. v пусто, если этот узел еще не принял никакого значения, o.w. v равно значению, которое он принял

3) CreateDecide (n, v) == принять! (X, v), запрашивая узлы принять это значение от предложителя с идентификатором x. узлы будут отклонять сообщение, если они получили сообщение prepare (n), где n> x

Как только достигнут кворум для prepare (n) - то есть большинство подтвердили сообщение - тогда заявитель с идентификатором n отправляет команду accept! (N, v). Если подготовитель (n + x), x> 0, был отправлен отправителем с идентификатором n + x - и это подтверждено большинством - между сообщениями ack (n, v) и accept! ( n, v), тогда большинство пообещало не принимать значения, предложенные с отметкой времени 0 (AKA узлы отклонят принятие! ​​(n, v))

Выбор будет сделан, как только большинство получит сообщение о принятии! (N, v), которое они не обещали игнорировать.

Таким образом, когда сервер2 возвращается в оперативный режим и отправляет команду accept! (5, S2), он будет игнорироваться, потому что 5 <7. </p>

Answer 2

Чтобы дать контрапункт принятому ответу, самому алгоритму на самом деле никогда не нужно завершать в каком-то ужасно четко определенном смысле. Имеет больше смысла говорить о том, что каждый узел индивидуально прекращает свое участие в алгоритме, который определяется реализацией. Тогда, возможно, вы могли бы сказать, что сам алгоритм завершился, когда выпали все участвующие узлы, если бы это было полезно узнать.

Алгоритм фактически сходится , как только большинство получателей отправляют свои сообщения AcceptPropose для одного и того же голосования (в том смысле, что после того, как это произошло, нет никакой возможности определить, какое значение может в конечном итоге) быть решенным), но это не такое положение вещей, которое можно наблюдать на практике: например, если бы сеть начала отбрасывать сообщения непосредственно перед отправкой этого набора сообщений AcceptPropose, ни один узел не смог бы узнать, что алгоритм сходились, пока связь не была восстановлена.

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

Каждый узел может прекратить свое участие в алгоритме, как только он узнает значение, к которому сходится алгоритм, хотя он может предпочесть продолжать участвовать дольше, в зависимости от ограничений реализации.

Вам нужно немного подумать о отказоустойчивости, чтобы убедить себя, что завершение по решению сохраняет жизнеспособность: если бы все узлы, которые знают, какое значение было решено, должны были умереть, прежде чем они могли бы поделиться им, будет ли прогресс еще возможен? Ответ, к счастью, да: пока большинство узлов остается живым, если любой из них знает определенное значение, он может поделиться им с другими, а если нет, то есть большинство участвующих узлов, которые просто нужно выбрать большее число бюллетеней и запустить еще один тур.

---

В принятом ответе следует остерегаться одной фразы:

Выбор будет сделан, как только большинство получит сообщение о принятии! (N, v), которое они не обещали игнорировать.

Во-первых, в протоколе нет ничего о , обещающем игнорировать AcceptPropose сообщений. Обещания относятся к сообщениям Propose, которые следует игнорировать / отклонять. Большинство AcceptPropose сообщений могут всегда использоваться для изучения выбранного значения, независимо от номера бюллетеня.

Во-вторых, выбор фактически делается, как только большинство отправляет AcceptPropose сообщений. Вы не можете наблюдать это напрямую, поэтому вам нужно подождать, пока хотя бы один узел получит AcceptPropose сообщений от большинства, прежде чем узнает, что выбор сделан. Как только это произойдет, вы можете поделиться выбранным значением с помощью большего количества AcceptPropose сообщений или с помощью рассылки / сплетен из Decided сообщений, в зависимости от того, что больше соответствует вашим ограничениям реализации.