paxos - может кто-нибудь объяснить Принять сообщение на примере

Во многих распределенных протоколах и алгоритмах без блокировки / ожидания один субъект завершает работу, которую другой субъект, возможно, не завершил. Претенденты на Paxos будут доводить до конца работу других предлагающих, когда это возможно. (Дело не только в том, чтобы переманивать других предлагающих.) Это действительно важно, если исходный предлагающий или некоторые из принимающих становятся недоступными в ходе выполнения алгоритма.

Например, первоначальный предлагающий (Пол) отправляет свои Prepares и Accepts, но умирает перед отправкой accept одному из принимающих (ст.). Большинство акцепторов приняли значение (A), поэтому значение выбрано, но вся система может быть в неведении по этому поводу. Появляется еще один предлагающий, Пегги. Она отправляет собственное предложение и узнает от Адама, что значение А было кем-то принято. Обратите внимание, это могло быть или не быть большинством. На всякий случай она отправляет A обратно, и теперь Арт узнает ценность.

Paul            Alice Adam Art            Peggy
 |-propose(1)--->|---->|--->|
 |<----ack(_,_)--|-----|----|
 |-accept(A,1)-->|---->|    X               +
 X               |<----|<---|<---propose(2)-|
                 X     |------ack(A,1)----->|
                            |-ack(_,_)----->|
                 |<----|<---|<--accept(A,2)-|
                 |-----|----|-ack---------->|

Вы можете видеть, что здесь произошло как минимум две вещи: на этапе подготовки Пегги узнала принятое значение; на этапе принятия она передала выбранное значение остальным приемникам.

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

(Обратите внимание: если бы Пегги не отправила значение A, она бы изменила выбранный ответ, что нарушает инвариант консенсуса.)

Давайте возьмем другой пример, когда подготовка-подтверждение возвращает несколько значений: (A, 1) и (B, 2). Мы можем сделать некоторые выводы из этого сценария.

1. Наличие (B, 2) означает, что большинство акцепторов подтвердили сообщение prepare (2), таким образом
2. маловероятно, что был выбран A (но не невозможно), потому что большинство принимающих отклонят сообщение accept (A, 1).
3. Присутствие (B, 2) также означает, что возможно, что B был выбран большинством акцепторов. Предлагающий не будет знать наверняка, пока не получит подтверждения.

Обновление: ответы на несколько вопросов из комментариев.

Какую роль играет во всем этом клиент?

Это зависит от приложения. Поддерживаемое мной приложение Paxos управляется двумя типами внешних событий: временем и клиентскими запросами на запись. Клиентские запросы записываются в базу данных; сервер использует Paxos как для репликации, так и для согласования записи; а затем результат отправляется обратно клиенту. Клиент в приложении my вообще не знает о Paxos и не участвует в протоколе.

В других приложениях клиент мог взять на себя роль предлагающего.

Почему Пегги не использует собственное значение после фазы подготовки?

Во-первых, обратите внимание, что Пегги ждала ответа только от простого большинства принимающих [ceil( N/2 )]. Это означает, что результат ceil( N/2 ) - 1 акцепторов неизвестен Пегги. Это число на единицу меньше простого большинства.

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

Почему Пегги использует значение, связанное с наибольшим значением, возвращаемым на этапе подготовки?

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