Противоречие в простой бумаге Лампорта «Паксос»

Вы что-то пропустили на шаге 7. Когда C обрабатывает accept 100:b, он устанавливает свое состояние в C(100:b,100). Принимая значение, узел также обещает не принимать более ранние значения.

Обновление. Я думал об этом весь месяц, потому что знал, что приведенный выше ответ был не совсем правильным.

Более того, я просмотрел несколько проприетарных реализаций paxos с открытым исходным кодом, и все они содержали ошибку, отправленную OP!

Итак, вот правильный ответ, если смотреть полностью из Paxos Made Simple:

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

Другими словами, предлагающий может отправлять только Accept сообщения принимающим, которые он получил Promises от для этого номера бюллетеня.

Итак, противоречие ли в статье Лэмпорта? Прямо сейчас я говорю да.

Если вы посмотрите на доказательства paxos Лампорта, он рассматривает accept как promise, как и предполагает мой первоначальный ответ. Но это не указано в Paxos Made Simple. Фактически, похоже, Лэмпорт приложил большие усилия, чтобы указать, что accept не является promise.

Проблема в том, что вы объединяете более слабые части обоих вариантов; как это сделал OP и несколько реализаций. Тогда вы столкнетесь с этой катастрофической ошибкой.

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

Однако в вашем контрпримере есть ошибка. Во-первых, обозначение определяется так:

X(n:v,m) для обозначения статуса принимающей стороны X: предложение n:v - это предложение с наибольшим номером, принятое X

Но затем на шаге 7 узел C имеет состояние C(100:b,-), а затем на шаге 9 он изменяется на состояние C(1:a,-). Это недопустимый переход: после принятия 1:a он должен оставаться в состоянии C(100:b,-), поскольку 100:b по-прежнему является предложением с наибольшим номером, принятым C.

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

NECROBUMP. Даже с более слабой частью обоих вариантов несоответствия нет. Давайте посмотрим на шаг 9 в примере в вопросе:

«Состояние - A (-: -, 100) B (100: b, 100) C (1: a, -). Выбранное предложение отвергнуто, Paxos терпит неудачу»

Однако на данный момент все, что у нас есть, - это неопределенное значение, поскольку не существует принятого большинством значения (в конечном итоге мы должны выбрать «b», поскольку b был принят большинством на шаге 6.)

Для продолжения протокола нам нужны новые бюллетени, и в конечном итоге будут приняты новые бюллетени. Этот бюллетень должен иметь значение "b",

ДОКАЗАТЕЛЬСТВО: C ответит (100, 'b') на любые запросы на подготовку, поскольку принятый им бюллетень с наивысшим номером равен (100, 'b'), даже если он последним принял бюллетень (1, 'а'). B также ответит (100, 'b'). Следовательно, больше невозможно получить мажоритарный бюллетень с любым значением, кроме «b».

Язык Лампорта таков, что акцептант ответит: «Предложение с наибольшим числом меньше n, которое он принял, если таковое имеется».

В принятом ответе «самый высокий номер» путается с «последним принятым», поскольку пример показывает, что акцептор может принимать значения в порядке убывания нумерации. Чтобы полностью согласоваться с протоколом Лампорта, C необходимо помнить, что он ответил на (100, 'b'), даже если «последнее» принятое им принятие - (1, 'a').

(При этом я не удивлюсь, если многие реализации будут делать это неправильно и, следовательно, уязвимы для этой проблемы.)

В документе действительно есть двусмысленность, поэтому для реализации алгоритма следует использовать спецификацию TLA +, а не документ.

Принимая значение, акцептор должен еще раз обновить свое состояние, а именно последний обещанный бюллетень. Это ясно из спецификации Paxos TLA +, проверьте Фаза 2b, на которой акцептор обновляет maxBal, и сравните с фазой 1b, где он делает то же самое.

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

C не может принять предложение, поскольку он не прошел Фазу 1. IOW, чтобы значение было принято акцептором, акцептор должен пройти через обе фазы протокола.

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

Вышеупомянутое условие не требуется. Предположим, что наибольшее количество баллов, которые обещал акцептор, - X. Предположим, входящее сообщение о принятии имеет номер бюллетеня Y. Если Y ‹X, мы знаем, что Y должен быть отклонен. Если Y> X, это означает, что принимающая сторона не получила запрос на подготовку для Y. Это означает, что мы получили недопустимое сообщение paxos. В этом случае сообщение о принятии для Y следует отбросить.

Единственное исключение из этого - когда Y == 0. В этом случае выдача подготовки с номером бюллетеня 0 не имеет смысла, поскольку номера бюллетеней ниже 0 недействительны. Таким образом, этап 1 может быть пропущен для бюллетеня 0, и предлагающий может напрямую перейти к этапу 2. В этом случае, т.е. когда Y == 0, акцептор может принять значение только в том случае, если он не принял значение. Это то же самое, что вы предлагаете выше, но это требуется только в оптимизированной версии Paxos, где этап 1 можно пропустить для Y == 0.

IOWs, единственный раз, когда акцептор принимает значение, - это когда Y == X. Единственное исключение - когда Y == 0. В этом случае акцептор может принять значение, только если он не принял значение.

Я согласен с большей частью ответа Бена Брауна.

Для C нормально принять (1, a), это не меняет выбранное значение. Допустим, C принял (1, a), и мы посмотрим на историю принятия с точки зрения учащегося.

(100, b) принято B и C
(1, a) принято C

(100, б) выбрано, так как оно принимается большинством акцепторов.

На этом этапе протокол не нужно продолжать, если учащийся получил полную историю принятия, если только учащиеся не потерпели неудачу или сообщения учащимся не потеряны. Здесь я не согласен с ответом Бена Брауна.

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

обновление: я также согласен с Дэйвом Тернером в том, что на самом деле нет причин принимать предложение с меньшим номером. Номер предложения похож на логические часы, старые сообщения можно игнорировать.