Существует ли недетерминированный алгоритм выбора лидера?

Question

Мне было интересно, существует ли алгоритм выбора недетерминированных лидеров (в одно направленном кольце), который обеспечивает завершение. Я не могу думать ни о одном, и не могу найти тот, который не является детерминированным. Некоторые из которых я нашел:

• Выберите узел с наивысшим идентификатором процесса, который будет лидером (детерминированным) и завершается.

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

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

Спасибо за все!

Answer 1

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

Однако существуют алгоритмы с пределом вероятности нуля для не-завершения для достаточной продолжительной работы алгоритма. Кроме того, ожидаемое время выполнения довольно короткое (AFIR, в порядке ln (k) для k инициаторов).

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

EDIT 1-3:

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

Если вы хотите иметь другой результат для не-анонимных членов, вы можете, например, использовать алгоритм две фазы:

1. Выполнение классического лидера выборов => а узлы А с самым высоким ID выигрывает
2. Пусть рулон кубик, чтобы определить фактический лидер.

Элемент случайности также может быть распределен:

1. Любых узлов знает множество идентичностей (S) (если нет, то использовать алгоритм затопления сказать)
2. Всех узлов выбрать случайно идентификатор ouf S и отправить его на любой другой узел
3. Идентификатор, который называется чаще всего, выигрывает. Если имеется более одного такого идентификатора, выберите один из них детерминированным способом, например, медиана.

Прекращение и неопределенный результат предоставляются для обоих алоритов. Тем не менее, первый имеет более низкую среднюю сложность сообщения (пжурналап против n², в худшем случае сложность такой же) и более справедливой (то есть вероятность того, что ID выигрывает в equaly распределяется , что не соответствует второму алгоритму). Я уверен, что по крайней мере последний недостаток можно устранить с помощью более сложного алгоритма, но вопрос здесь заключался в общем существовании такого алгоритма.

Answer 2

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

Это на самом деле довольно легко. Относитесь к каждому клиенту в виде карточки в колоде карт, затем используйте алгоритм mental poker(который является распределенным алгоритмом для случайного и случайного перетасовки колоды карт), чтобы перетасовать его. Затем просто возьмите первую карту в качестве лидера.