В paxos, что произойдет, если заявитель не работает после того, как его предложение будет отклонено?

Question

На этом рисунке предложение X отклонено.

В конце временной шкалы S1 и S2 принимают X, в то время как S3, S4 и S5 принимают Y. Предполагающий X теперь должен повторно отправить предложение со значением Y.

Но что произойдет, если предложивший X выйдет из строя в это время? Как S1 и S2 в конечном итоге узнают значение Y?

Заранее спасибо!

Answer 1

Сложно ответить на этот вопрос из фрагмента диаграммы, которым вы поделились, поскольку неясно, что именно это означает. Было бы полезно, если бы вы могли сослаться на источник этой диаграммы, чтобы мы могли видеть больше контекста вашего вопроса. Остальная часть этого ответа основана на предположении о его значении.

В Paxos есть три различные роли, обычно известные как proposer , acceptor и ученик , и я думаю, что понимание помогает разделить вещи на эти три роли. Диаграмма, которой вы поделились, выглядит так, как будто она иллюстрирует набор из пяти акцепторов и сообщений, которые они отправили в рамках базового алгоритма Synod c (он же Paxos для одного экземпляра). В целом, между наборами учеников и акцепторов в системе нет взаимосвязи: может быть один ученик или тысячи, и я думаю, что это помогает отделить эти понятия. Так как S1 и S2 являются акцепторами, а не учащимися, не имеет смысла спрашивать, изучают ли они ценность. Однако уместно спросить о том, как поступить с учеником, который не усвоил ценность.

В практических системах обычно есть и другая роль лидера , которая берет на себя ответственность за продвижение системы вперед с использованием тайм-аутов, повторных попыток и детекторов ошибок и так далее, чтобы гарантировать, что все учащиеся в конечном итоге узнают выбранное значение или попытку d ie, но это выходит за рамки базового алгоритма c, который, как представляется, иллюстрируется Вот. Другими словами, этот алгоритм гарантирует безопасность («ничего плохого не происходит»), но не гарантирует жизнеспособность («что-то хорошее происходит»). Здесь допустимо, если некоторые из учеников никогда не изучают выбранную ценность.

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

Answer 2

На этом рисунке предложение X отклонено.

Мое представление о диаграмме таково, что это «запрос на принятие», который отклоняется. Страница 5 параграфа Paxos Made Simple описывает этот тип сообщения.

Предполагается, что заявитель X повторно отправит предложение со значением Y.

На диаграмме это не указано. Только если Y был замечен в ответ на синие начальные сообщения предложения, синий предлагающий должен был выбрать Y. Тем не менее синий предлагающий выбрал X в качестве значения в своем «запросе на принятие». Если он правильно следует за Паксосом, он не мог «увидеть Y» в ответ на свое первоначальное сообщение с предложением. Если бы он видел это, то, должно быть, он выбрал его, и поэтому он не отправил бы X.

Чтобы действительно знать, что происходит, вам нужно знать, какие ответы видел каждый заявитель. На диаграмме не видно, какие значения, если таковые имеются, были возвращены в ответ на первые три синих сообщения о предложении. На диаграмме мы не видим, был ли X ранее принят на каком-либо узле или нет. Мы не знаем, был ли синий предлагающий «свободен в выборе», его собственный X или ему пришлось использовать X, который уже был принят в одном или нескольких узлах.

Но что произойдет, если получатель X получит в это время?

Если синий проповедник умирает, то это не проблема. Зеленый предложитель успешно зафиксировал значение Y в большинстве узлов.

Как S1 и S2 в конечном итоге узнают значение Y?

Более интересный сценарий что произойдет, если зеленый заявитель умрет. Зеленый заявитель, возможно, отправил сообщения о принятии запроса, содержащие Y, и сразу же умер. Поскольку три из сообщений являются успешными, значение Y было исправлено, но первоначальный запросчик может не быть активным, чтобы увидеть сообщения ответа на прием. Для дальнейшего прогресса новый заявитель должен отправить новое сообщение с предложением. Поскольку три узла ответят Y, новый заявитель выберет Y в качестве значения своего сообщения запроса на принятие. Это будет отправлено всем узлам, и если все сообщения пройдут, и никакие другие прерывания не будут предложены, то S1 и S2 станут согласованными.

Суть алгоритма - сотрудничество. Если заявитель умирает, следующий заявитель будет сотрудничать и выберет максимальное предложенное ранее значение, если оно существует.