Выборы лидера Паксоса могут не закончиться

Question

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

Но здесь возникает вопрос, поскольку люди предлагают использовать Паксос для избрания выдающегося автора предложения, что снова требует лидера, чтобы гарантировать прогресс.

Я понимаю, что данный сценарий может быть специфичным для реализации, например, если выделенные множества, заданные для выбранных процессов, упорядочены, я имею в виду набор P1 < P2.

Но я хочу понять в реальных реализациях, как это обрабатывается?

Answer 1

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

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

Если мы установим большее кратное X как верхнюю границу случайного таймаута, мы имеем меньшую вероятность расширенной дуэли. Но у нас также есть более продолжительное среднее время, прежде чем появится лидер. Так что это компромисс.

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

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