В асинхронной системе, где возможен отказ хотя бы одного узла, можно ли гарантировать завершение консенсуса при любом расписании доставки сообщений?
Нет, если система полностью асинхронна, протокол детерминирован, а возможен хотя бы один отказ узла. Это утверждает результат FLP: нельзя одновременно гарантировать безопасность консенсуса и его завершение в каждой допустимой последовательности задержек и отказов. При этом отдельные запуски протокола могут успешно завершаться.
Результат FLP был сформулирован для точного описания фундаментального ограничения распределённых вычислений. Он показал, что проблема консенсуса связана не только с выбором алгоритма, числом реплик или форматом сообщений.
Исходная трудность — невозможность надёжно отличить очень медленный узел от отказавшего. Если сообщение не пришло, система не знает, нужно ли ждать его или продолжать без него. Любое решение может оказаться преждевременным при другом допустимом расписании доставки.
Рассмотрим несколько узлов, которые должны выбрать одно значение. Сообщения могут задерживаться на неопределённый срок, но не теряются, а один узел может прекратить работу.
Протокол должен сохранять безопасность: два узла не должны принять разные решения. Одновременно от него хотят живучести: решение должно быть принято за конечное время. В полностью асинхронной системе нельзя гарантировать второе для всех возможных расписаний, не нарушив первое.
Если протокол ждёт каждый узел, отказ блокирует прогресс. Если он принимает решение без него, такая же наблюдаемая ситуация может быть лишь задержкой сообщения, после которой другой узел получит противоположную информацию.
Идея доказательства FLP строится на существовании неопределённых конфигураций. В такой конфигурации ещё возможны как минимум два разных решения в зависимости от того, какое сообщение будет обработано следующим.
Для детерминированного протокола можно подобрать порядок доставки сообщений так, чтобы после каждого шага система оставалась в неопределённой конфигурации. Планировщик задерживает сообщения, которые могли бы однозначно склонить систему к одному решению, и тем самым допускает бесконечное отсутствие решения, не нарушая условий асинхронной модели.
Это не означает, что консенсус бесполезен или никогда не завершается. Ограничение относится к гарантии завершения при любом расписании. На практике протоколы используют дополнительные предположения:
Практический вывод: тайм-аут не доказывает отказ узла, а является эвристикой или частью модели частичной синхронности. Поэтому корректный протокол сначала сохраняет безопасность при ошибочном подозрении, а затем использует тайм-ауты для восстановления живучести.
Сервис конфигурации должен согласовать новую версию между пятью узлами. В одном варианте он ждёт подтверждения каждого узла: при сетевой задержке или отказе одного участника обновление блокируется, зато решение без полного набора участников не принимается.
Второй вариант принимает решение после большинства и использует тайм-аут лидера. Его преимущество — работа при отказе меньшинства и восстановление управления после потери лидера. Недостаток — тайм-аут может ошибочно запустить перевыборы при временной задержке, поэтому протокол должен гарантировать, что старый лидер не сможет безопасно конкурировать с новым, а сама система допускает прогресс только при доступном большинстве.
Третий вариант пытается решить проблему увеличением числа повторных попыток. Это не устраняет ограничение FLP: при неограниченных задержках повторения также могут продолжаться бесконечно. На практике выбирают кворумный консенсус с тайм-аутами и моделью частичной синхронности; результатом становится сохранение безопасности всегда и завершение при восстановлении связи и выполнении временных предположений.
Нет. Теорема относится к строгой асинхронной модели и гарантии завершения при любом допустимом сценарии. Реальные протоколы обычно рассчитывают на частичную синхронность, используют тайм-ауты, кворумы и выбор лидера. Поэтому они могут гарантировать безопасность без временных предположений и обеспечивать живучесть, когда сеть и узлы ведут себя достаточно хорошо.
Невозможно гарантировать терминацию, то есть принятие решения за конечное число шагов в каждом сценарии. Требования согласованности и корректности решения могут оставаться достижимыми: протокол способен никогда не выбрать значение, но не должен выбрать два разных значения или выбрать недопустимое значение.
Да, но ценой усиления модели системы. Надёжный детектор, который всегда точно сообщает об отказе и никогда не ошибается, предоставляет информацию, недоступную в полностью асинхронной сети. Практические детекторы обычно не идеальны: они могут принять задержавший узел за отказавший, поэтому протокол должен допускать ложные подозрения без нарушения безопасности; для живучести нужны дополнительные условия, например eventual-полнота и eventual-точность или эквивалентное предположение о стабилизации сети.