Теорема невозможности FLP

Доказательство 1985 года за авторством Fischer, Lynch и Paterson, показывающее, что в асинхронной распределённой системе не существует детерминированного алгоритма, решающего задачу консенсуса, если хотя бы один процесс может аварийно завершиться. Полное название: "Impossibility of Distributed Consensus with One Faulty Process".

Что она утверждает на самом деле

Дано:

• Набор процессов, взаимодействующих через передачу сообщений
• Асинхронная связь (нет верхней границы времени доставки сообщений)
• Не более одного процесса может отказать (навсегда перестать отвечать)

Тогда: не существует детерминированного протокола, гарантирующего одновременно согласие (agreement), валидность (validity) и завершаемость (termination).

Ключевая идея заключается в неразличимости (indistinguishability). В асинхронной системе упавший процесс выглядит точно так же, как очень медленный. Любой протокол, ожидающий медленный процесс, рискует ждать бесконечно (нарушая завершаемость). Любой протокол, который перестаёт его ждать, рискует принять решение, отличное от того, к которому медленный процесс уже пришёл (нарушая согласие).

Что она НЕ утверждает

FLP не означает, что консенсус невозможен на практике. Это значит, что нельзя получить протокол, который всегда завершается, всегда корректен и устойчив к любому моменту возникновения сбоев. Реальные системы обходят это ограничение:

• Используя таймауты (добавляя допущение о частичной синхронности) - именно так устроены Raft и Paxos. Они корректны, если сеть в конечном счёте доставляет сообщения, и зависают (но не принимают ошибочных решений), если доставка нарушена.
• Используя рандомизацию - рандомизированные протоколы могут достигать консенсуса с вероятностью 1, обходя детерминированную невозможность.
• Принимая, что система может время от времени останавливаться до ручного вмешательства человека.

Почему это важно

FLP - причина, по которой в распределённых базах данных есть таймауты выборов лидера, почему в Raft есть таймер выборов и почему кластерам Kubernetes для работы нужен минимальный кворум. Любая production-система distributed-consensus проектируется с оглядкой на эту невозможность: выбирая, какое именно свойство ослабить, а не делая вид, что ограничения не существует.

В контексте мультиагентных LLM-систем (log-distributed-llms) теорема FLP означает, что невозможно построить мультиагентную систему написания кода, которая гарантированно выдаёт корректный и согласованный результат за ограниченное время при наличии сбоев агентов. Приходится явно определять в архитектуре, с каким типом отказов система готова мириться.