Вопросы Паксоса: если предложение вниз, что случилось?

Question

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

Существует два предложенных P1 P2, три акцептора A1 A2 A3. Р1 предложит значение и, Р2 предложит значение ст.

1. Р1 (отправить идентификационный номер) завершить стадию подготовки, получают все обещание от A1 A2 A3, то в A1 A2 A3 всех п магазина, как идентификатор.

2. Р2 (отправить идентификатор п + 1), то A1 A2 A3 магазин п + 1, как идентификатор

3. P2 вниз.

4. P1 отправьте запрос на прием с (n, u) на A1 A2 A3, конечно, A1 A2 A3 отклонит запрос, к сожалению, в то же время P2 уже выключен.

Такой примерный случайный случай, что бы мы сделали дальше? еще один новый раунд Paxos?

Answer 1

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

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

В этом случае у вас могут быть 3 экземпляра P2: P2-1, P2-2, P2-3, причем P2-1 является лидером по умолчанию, если P2-1 терпит неудачу, тогда P2-2 может увеличиться.

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

Answer 2

«Paxos Made Simple» Лампорт

"Это легко построить сценарий, в котором два предлагающие каждый держать выпуск последовательность предложений с увеличением числа, ни один из которых никогда не выбраны. Предлагающий р завершает фазу 1 для номера предложения n1. Другой вариант q затем завершает фазу 1 для номера предложения n2> n1. Предполагаемая фаза 2 заявки участника заявки на предложение с номером n1 игнорируется, поскольку акцепторы все обещали не принимать никаких новых предложений с номером меньше, чем n2. Итак, создатель p затем начинает и завершает этап 1 для нового номера предложения n3> n2, в результате чего вторая фаза 2 принимает запросы автора предложения q и т. д. «

Из описания Шаг 4: (A1, A2, A3) ответил бы на запрос приема от P1, отправил идентификатор + 1 в P1, после чего P1 будет уведомлен и увеличит id -> id + 2. P1 отправьте (A1, A2, A3) запрос на повторную обработку с id + 2. Чтобы избежать прямой блокировки между P1 и P2, лучший способ должен быть только одним предложением (ссылка на главу 2.4 «Paxos Made Simple»).

Answer 3

Сделайте новый раунд paxos, это именно то, для чего оно предназначено.

Авторы предложения отправляют свое значение в сообщении «Подготовить», поэтому акцепторы отправят значение P2 в P1 в следующем раунде paxos.