Обходит ли мой алгоритм выбора лидера результат ФЛП?
Исходя из результата FLP, любая проблема консенсуса не может быть решена в асинхронной сетевой системе, и выбор уникального лидера является своего рода проблемой консенсуса. Следовательно, в теории, выборы лидера являются неразрешимой проблемой в асинхронных сетевых системах.
Однако после того, как я узнал концепцию "надежной широковещательной передачи", согласно которой каждый исправный узел берет на себя ответственность за широковещательную рассылку любого значения, которое они получают от других узлов, можно добиться, чтобы "каждый исправный узел получал один и тот же набор сообщений (игнорируя приказ)". Итак, если каждый узел использует надежную широковещательную рассылку для отправки своего идентификатора узла другим узлам, означает ли это, что, наконец, каждый исправный узел получит тот же набор идентификаторов узлов и, следовательно, сможет выбрать одного и того же лидера (просто узел с наибольшим id - лидер)?
Если так, то почему говорят, что выборы лидера неразрешимы? Или я что-то путаю?
1 ответ
Надежная широковещательная рассылка использует (идеальный) детектор отказов, чтобы узнать, какой процесс в кластере отказал. Такого детектора просто не существует в асинхронной сети, поскольку вы в принципе не можете отличить медленный процесс от неисправного в такой сети.
Таким образом, вы не можете полагаться на надежную трансляцию для решения желаемой проблемы.
Ваш алгоритм никогда не завершится после сбоя одного процесса. Следовательно, он вообще не потерпит никаких ошибок, и при этом вы вообще не обойдете FLP.